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

doi:10.1007/s11704-014-3425-y

Front. Comput. Sci.

2014, Vol. 8

Issue (6) : 948-957 https://doi.org/10.1007/s11704-014-3425-y

RESEARCH ARTICLE

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

Yongyi YAN¹,Zengqiang CHEN^1,^2,^*(

),Zhongxin LIU¹

1. College of Computer and Control Engineering, Nankai University, Tianjin 300071, China,
2. College of Science, Civil Aviation University of China, Tianjin 300300, China

Download: PDF(314 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Zengqiang CHEN

Issue Date: 27 November 2014

Cite this article:

Yongyi YAN,Zengqiang CHEN,Zhongxin LIU. Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition[J]. Front. Comput. Sci., 2014, 8(6): 948-957.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-014-3425-y
https://academic.hep.com.cn/fcs/EN/Y2014/V8/I6/948

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 https://doi.org/10.1142/8323
3	Hochma G, Margaliot M, Fornasini E, Valcher M E. Symbolic dynamics of Boolean control networks. Automatica, 2013, 49(8): 2525-2530 https://doi.org/10.1016/j.automatica.2013.05.004
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 https://doi.org/10.1002/rnc.2781
5	Li F, Sun J. Controllability and optimal control of a temporal Boolean network. Neural Networks, 2012, 34: 10-17 https://doi.org/10.1016/j.neunet.2012.06.002
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 https://doi.org/10.1016/j.automatica.2012.01.021
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 https://doi.org/10.1109/TNNLS.2013.2248092
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 https://doi.org/10.1016/j.automatica.2012.03.024
10	Li H, Wang Y. Output feedback stabilization control design for Boolean control networks. Automatica, 2013, 49(12): 3641-3645 https://doi.org/10.1016/j.automatica.2013.09.023
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 https://doi.org/10.1007/s11768-014-0137-7
12	Feng J, Yao J, Cui P. Singular Boolean networks: Semi-tensor product approach. Science China Information Science, 2013, 56: 1-14 https://doi.org/10.1007/s11432-013-5009-0
13	Xu X, Hong Y. Matrix expression and reachability analysis of finite automata. Journal of Control Theory and Applications, 2012, 10(2): 210-215 https://doi.org/10.1007/s11768-012-1178-4
14	Charatonik W, Chorowska A. Parameterized complexity of basic decision problems for tree automata. International Journal of Computer Mathematics, 2013, 90(6): 1150-1170 https://doi.org/10.1080/00207160.2012.762451
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 https://doi.org/10.1080/00207160701326764
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 https://doi.org/10.1016/j.sysconle.2010.09.002
19	Seshu S, Miller R, Metze G. Transition matrices of sequential machines. IRE Transactions on Circuit Theory, 1959, 6(1): 5-12 https://doi.org/10.1109/TCT.1959.1086510
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 https://doi.org/10.1016/S0005-1098(98)00193-9
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 https://doi.org/10.1109/WCICA.2012.6358333
25	Li F, Lu X. Complete synchronization of temporal Boolean networks. Neural Networks, 2013, 44(2013): 72-77 https://doi.org/10.1016/j.neunet.2013.03.009
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 https://doi.org/10.1007/s11704-012-1301-1

[1]	Xiaofang QI, Zhenliang JIANG. Precise slicing of interprocedural concurrent programs[J]. Front. Comput. Sci., 2017, 11(6): 971-986.
[2]	Yongyi YAN, Zengqiang CHEN, Jumei YUE. Algebraic state space approach to model and control combined automata[J]. Front. Comput. Sci., 2017, 11(5): 874-886.

Viewed

Full text

Abstract

Cited

Shared

Discussed