Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

Abstract

This paper investigates the transition function and the reachability conditions of finite automata by using a semitensor product of matrices, which is a new powerful matrix analysis tool. The states and input symbols are first expressed in vector forms, then the transition function is described in an algebraic form. Using this algebraic representation, a sufficient and necessary condition of the reachability of any two states is proposed, based on which an algorithm is developed for discovering all the paths from one state to another. Furthermore, a mechanism is established to recognize the language acceptable by a finite automaton. Finally, illustrative examples show that the results/algorithms presented in this paper are suitable for both deterministic finite automata (DFA) and nondeterministic finite automata (NFA).

Keywords

finite automata / reachability analysis / transition function expression / matrix approach / semi-tensor product

References

[1] Cheng D. Semi-tensor product of matrices and its application to Morgen’s problem. Science in China Series F: Information Sciences, 2001, 44(3): 195-212

[2] Cheng D, Qi H, Zhao Y. An Introduction to Semi-tensor Product of Matrices and Its Applications. Singapore: World Scientific Publishing Co, 2012

[3] Hochma G, Margaliot M, Fornasini E, Valcher M E. Symbolic dynamics of Boolean control networks. Automatica, 2013, 49(8): 2525-2530

[4] Zhang L, Zhang K. L2 stability, H∞ control of switched homogeneous nonlinear systems and their semi-tensor product of matrices representation. International Journal of Robust and Nonlinear Control, 2013, 23(6): 638-652

[5] Li F, Sun J. Controllability and optimal control of a temporal Boolean network. Neural Networks, 2012, 34: 10-17

[6] Li H, Wang Y. Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method. Automatica, 2012, 48(4): 688-693

[7] Li H T, Wang Y Z, Liu Z B. A semi-tensor product approach to Pseudo-Boolean functions with application to Boolean control networks. Asian Journal of Control, 2013 (in press)

[8] Li R, Yang M, Chu T. Synchronization design of Boolean networks via the semi-tensor product method. IEEE Transactions on Neural Networks and Learning Systems, 2013, 24(6): 996-1001

[9] Wang Y, Zhang C, Liu Z. A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems. Automatica, 2012, 48(7): 1227-1236

[10] Li H, Wang Y. Output feedback stabilization control design for Boolean control networks. Automatica, 2013, 49(12): 3641-3645

[11] Yan Y, Cheng Z, Liu Z. Solving type-2 fuzzy relation equations via semi-tensor product of matrices. Control Theory and Technology, 2014, 12(2): 173-186

[12] Feng J, Yao J, Cui P. Singular Boolean networks: Semi-tensor product approach. Science China Information Science, 2013, 56: 1-14

[13] Xu X, Hong Y. Matrix expression and reachability analysis of finite automata. Journal of Control Theory and Applications, 2012, 10(2): 210-215

[14] Charatonik W, Chorowska A. Parameterized complexity of basic decision problems for tree automata. International Journal of Computer Mathematics, 2013, 90(6): 1150-1170

[15] Eilenberg S. Automata, languages, and machines. New York: Academic Press, INC, 1974

[16] Long H, Fu Y. A general approach for building combinational P automata. International Journal of Computer Mathematics, 2007, 84(12): 1715-1730

[17] Kim K H. Boolean matrix theory and applications. New York: Dekker, 1982

[18] Zhao Y, Qi H, Cheng D. Input-state incidence matrix of Boolean control networks and its applications. Systems & Control Letters, 2010, 59(12): 767-774

[19] Seshu S, Miller R, Metze G. Transition matrices of sequential machines. IRE Transactions on Circuit Theory, 1959, 6(1): 5-12

[20] Abdelwahed S, Wonham W. Blocking detection in discrete event systems. In: Proceeding of the American Control Conference. 2003, 1109-1114

[21] Lygeros J, Tomlin C, Sastry S. Controllers for reachability specifications for hybrid systems. Automatica, 1999, 35(3): 349-370

[22] Casagrande A, Balluchi A, Benvenuti L, Policriti A, Viua T, Sangiovanni-Vincenteui A. Improving reachability analysis of hybrid automata for engine control. In: Proceedings of the Decision and Control. 2004, 2322-2327

[23] Dogruel M, Ozguner U. Controllability, reachability, stabilizability and state reduction in automata. In: Proceedings of the Intelligent Control. 1992, 192-197

[24] Xu X, Hong Y, Lin H. Matrix approach to simulation and bisimulation analysis of finite automata. In: Proceedings of 10th World Congress on Intelligent Control and Automation. 2012, 2716-2721

[25] Li F, Lu X. Complete synchronization of temporal Boolean networks. Neural Networks, 2013, 44(2013): 72-77

[26] Chen W. Theory of finite automata. Chengdu: University of Electronic Scinece Technoldge Press, 2007 (in Chinese)

[27] Liu J, Liu ZW, He J F, Mallet F, Ding Z H. Hybrid MARTE statecharts. Frontiers of Computer Science, 2013, 7(1): 95-108

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg