Please wait a minute...

Frontiers of Computer Science

Front. Comput. Sci.    2017, Vol. 11 Issue (5) : 874-886     DOI: 10.1007/s11704-016-5128-z
Algebraic state space approach to model and control combined automata
Yongyi YAN1,2, Zengqiang CHEN2(), Jumei YUE3
1. College of Information Engineering, Henan University of Science and Technology, Luoyang 471023, China
2. College of Computer and Control Engineering, Nankai University, Tianjin 300071, China
3. College of Agricultural Engineering, Henan University of Science and Technology, Luoyang 471003, China
Download: PDF(363 KB)  
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

A new modeling tool, algebraic state space approach to logical dynamic systems, which is developed recently based on the theory of semi-tensor product of matrices (STP), is applied to the automata field. Using the STP, this paper investigates the modeling and controlling problems of combined automata constructed in the ways of parallel, serial and feedback. By representing the states, input and output symbols in vector forms, the transition and output functions are expressed as algebraic equations of the states and inputs. Based on such algebraic descriptions, the control problems of combined automata, including output control and state control, are considered, and two necessary and sufficient conditions are presented for the controllability, by which two algorithms are established to find out all the control strings that make a combined automaton go to a target state or produce a desired output. The results are quite different from existing methods and provide a new angle and means to understand and analyze the dynamics of combined automata.

Keywords automata      composition      controllability      algebraic state space approach      semi-tensor product     
Corresponding Authors: Zengqiang CHEN   
Just Accepted Date: 11 May 2016   Online First Date: 17 March 2017    Issue Date: 26 September 2017
 Cite this article:   
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.
E-mail this article
E-mail Alert
Articles by authors
Yongyi YAN
Zengqiang CHEN
Jumei YUE
1 PighizziniG, PisoniA. Limited automata and context-free languages. Fundamenta Informaticae, 2015, 136(1): 157–176
2 SchluterN. Restarting automata with auxiliary symbols restricted by look ahead size. International Journal of Computer Mathematics, 2015, 92(5): 908–938
doi: 10.1080/00207160.2014.926005
3 GécsegF. Automata, Languages and Programming. New York: Springer,1974
4 HenzingerT A. The theory of hybrid automata. In: Proceedings of Symposium on Logic in Computer Science. 1996, 278–292
doi: 10.1109/LICS.1996.561342
5 KohaviZ, JhanK. Switching and Finite Automata Theory. New York: Cambridge University Press, 2010
6 HolcombeM, Holcombe L. Algebraic Automata Theory. Cambridge: Cambridge University Press, 2004
7 SokolovaA, Devinke P. Validation of Stochastic Systems. New York: Springer, 2004
8 OlderogR, Swaminathan M. Formal Modeling and Analysis of Timed Systems. New York: Springer, 2010
9 KomendaJ, LahayeS, BoimondL. Synchronous composition of interval weighted automata. In: Proceedings of the International Workshop on Discrete Event Systems. 2010, 318–323
doi: 10.3182/20100830-3-de-4013.00053
10 DogruelM, Ozguner U. Controllability, reachability, stabilizability and state reduction in automata. In: Proceedings of the IEEE International Symposium on Intelligent Control. 1992, 192–197
doi: 10.1109/isic.1992.225090
11 NerodeA, KohnW. Automata, Topologies, Controllability, Observability. New York: Springer, 1993
12 SakarovitchJ. Elements of Automata Theory.Cambridge: Cambridge University Press, 2009
doi: 10.1017/CBO9781139195218
13 CharatonikW, Chorowska A. Parameterized complexity of basic decision problems for tree automata. International Journal of Computer Mathematics, 2013, 90(6): 348–356
doi: 10.1080/00207160.2012.762451
14 CzechL. On dynamics of automata with a stack. International Journal of Computer Mathematics, 2015, 92(3): 486–497
doi: 10.1080/00207160.2014.914508
15 ChengD Z. Semi-tensor product of matrices and its application toMorgen’s problem. Science in China Series F: Information Sciences, 2001, 44(3): 195–212
16 ChengD Z, QiH S, ZhaoY. An Introduction to Semi-tensor Product of Matrices and Its Applications. Singapore: World Scientific Publishing, 2012
doi: 10.1142/8323
17 QiH S. On shift register via semi-tensor product approach. In: Proceedings of the 32nd Chinese Control Conference. 2013, 208–212
18 ChengD Z. Disturbance decoupling of boolean control networks. IEEE Transactions on Automatic Control, 2011, 56(1): 2–10
doi: 10.1109/TAC.2010.2050161
19 LiF, SunJ. Controllability and optimal control of a temporal Boolean network. Neural Networks, 2012, 34(12): 10–17
doi: 10.1016/j.neunet.2012.06.002
20 WangY Z, ZhangC H, LiuZ B. A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems. Automatica, 2012, 48(7): 1227–1236
doi: 10.1016/j.automatica.2012.03.024
21 FengJ E, LvH L, ChengD Z. Multiple fuzzy relation and its application to coupled fuzzy control. Asian Journal of Control, 2013, 15(5): 1313–1324
doi: 10.1002/asjc.656
22 LiH T, WangY Z. Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method. Automatica, 2012, 48(4): 688–693
doi: 10.1016/j.automatica.2012.01.021
23 YanY Y, ChenZ Q, LiuZ X. Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition. Frontiers of Computer Science, 2014, 8(6): 948–957
doi: 10.1007/s11704-014-3425-y
24 XuX R, HongY G. Observability analysis and observer design for finite automata via matrix approach. Control Theory & Applications, 2013, 7(12): 1609–1615
doi: 10.1049/iet-cta.2013.0096
25 XuX R, HongY G. Matrix expression and reachability analysis of finite automata. Journal of Control Theory and Applications, 2012, 10(2): 210–215
doi: 10.1007/s11768-012-1178-4
26 YanY Y, ChenZ Q, LiuZ X. Semi-tensor product approach to controlliability and stabilizability of finite automata. Journal of Systems Engineering and Electronics, 2015, 26(1): 134–141
doi: 10.1109/JSEE.2015.00018
27 ChengD Z, LiZ Q, QiaoY, Qi H S, LiuJ B . Stability of switched polynomial systems. Journal of Systems Science and Complexity, 2008, 21(3): 362–377
doi: 10.1007/s11424-008-9119-5
28 YanY Y, ChenZ Q, YueJ M, Fu Z M. STP approach to model controlled automata with application to reachability analysis of discrete event dynamic systems. Asian Journal of Control, 2016, doi: 10.1002/asjc.1294
doi: 10.1002/asjc.1294
29 ZhangG Q. Automata, Boolean matrices, and ultimate periodicity. Information and Computatioin, 1999, 152(1): 138–154
doi: 10.1006/inco.1998.2787
30 ZhangY Q, XuX R, HongY G. Bi-decomposition analysis and algorithm of automata based on semi-tensor product. In: Proceedings of the 31st Chinese Control Conference. 2012, 2151–2156
[1] FCS-0874-15128-ZQC_suppl_1 Download
Related articles from Frontiers Journals
[1] Li LIN,Jian HU,Jianbiao ZHANG. Packet: a privacy-aware access control policy composition method for services composition in cloud environments[J]. Front. Comput. Sci., 2016, 10(6): 1142-1157.
[2] Lamia SADEG-BELKACEM,Zineb HABBAS,Wassila AGGOUNE-MTALAA. Adaptive genetic algorithms guided by decomposition for PCSPs: application to frequency assignment problems[J]. Front. Comput. Sci., 2016, 10(6): 1012-1025.
[3] Junha LEE,Dae-Kyoo KIM,Suntae KIM,Sooyong PARK. Decomposing class responsibilities using distance-based method similarity[J]. Front. Comput. Sci., 2016, 10(4): 612-630.
[4] Yun SONG,Zhihui LI,Yongming LI,Ren XIN. The optimal information rate for graph access structures of nine participants[J]. Front. Comput. Sci., 2015, 9(5): 778-787.
[5] Laixiang SHAN,Xiaomin DU,Zheng QIN. Efficient approach of translating LTL formulae into Büchi automata[J]. Front. Comput. Sci., 2015, 9(4): 511-523.
[6] Bojun XIE,Yi LIU,Hui ZHANG,Jian YU. Efficient image representation for object recognition via pivots selection[J]. Front. Comput. Sci., 2015, 9(3): 383-391.
[7] Mingqiang GUO,Ying HUANG,Zhong XIE. A balanced decomposition approach to real-time visualization of large vector maps in CyberGIS[J]. Front. Comput. Sci., 2015, 9(3): 442-455.
[8] Fei HE,Xiaoyu SONG,Ming GU,Jiaguang SUN. Generalized interface automata with multicast synchronization[J]. Front. Comput. Sci., 2015, 9(1): 1-14.
[9] 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.
[10] Changpeng ZHU, Yinliang ZHAO, Bo HAN, Qinghua ZENG, Ying MA. Runtime support for type-safe and context-based behavior adaptation[J]. Front. Comput. Sci., 2014, 8(1): 17-32.
[11] Jing LIU, Ziwei LIU, Jifeng HE, Frédéric MALLET, Zuohua DING. Hybrid MARTE statecharts[J]. Front Comput Sci, 2013, 7(1): 95-108.
[12] Xiaoqin FAN, Xianwen FANG, Zhijun DING. Indeterminacy-aware service selection for reliable service composition[J]. Front Comput Sci Chin, 2011, 5(1): 26-36.
[13] Baoliang LU, Xiaolin WANG, Masao UTIYAMA. Incorporating prior knowledge into learning by dividing training data[J]. Front Comput Sci Chin, 2009, 3(1): 109-122.
[14] QIU Daowen, LI Lvzhou. An overview of quantum computation models: quantum automata[J]. Front. Comput. Sci., 2008, 2(2): 193-207.
[15] CHEN Changbo, MORENO MAZA Marc, PAN Wei, XIE Yuzhen. On the verification of polynomial system solvers[J]. Front. Comput. Sci., 2008, 2(1): 55-66.
Full text