Algebraic state space approach to model and control combined automata

Abstract

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

References

[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

[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

[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

[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

[11] NerodeA, KohnW. Automata, Topologies, Controllability, Observability. New York: Springer, 1993

[12] SakarovitchJ. Elements of Automata Theory.Cambridge: Cambridge University Press, 2009

[13] CharatonikW, Chorowska A. Parameterized complexity of basic decision problems for tree automata. International Journal of Computer Mathematics, 2013, 90(6): 348–356

[14] CzechL. On dynamics of automata with a stack. International Journal of Computer Mathematics, 2015, 92(3): 486–497

[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

[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

[19] LiF, SunJ. Controllability and optimal control of a temporal Boolean network. Neural Networks, 2012, 34(12): 10–17

[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

[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

[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

[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

[24] XuX R, HongY G. Observability analysis and observer design for finite automata via matrix approach. Control Theory & Applications, 2013, 7(12): 1609–1615

[25] XuX R, HongY G. Matrix expression and reachability analysis of finite automata. Journal of Control Theory and Applications, 2012, 10(2): 210–215

[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

[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

[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

[29] ZhangG Q. Automata, Boolean matrices, and ultimate periodicity. Information and Computatioin, 1999, 152(1): 138–154

[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

[31] HeC. Automata Theory and Its Applications. Beijing: Science Press, 1990

RIGHTS & PERMISSIONS

2016 Higher Education Press and Springer-Verlag Berlin Heidelberg