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
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.
. [J]. Frontiers of Computer Science, 2017, 11(5): 874-886.
Yongyi YAN, Zengqiang CHEN, Jumei YUE. Algebraic state space approach to model and control combined automata. Front. Comput. Sci., 2017, 11(5): 874-886.
SchluterN. Restarting automata with auxiliary symbols restricted by look ahead size. International Journal of Computer Mathematics, 2015, 92(5): 908–938 https://doi.org/10.1080/00207160.2014.926005
3
GécsegF. Automata, Languages and Programming. New York: Springer,1974
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 https://doi.org/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 https://doi.org/10.1109/isic.1992.225090
11
NerodeA, KohnW. Automata, Topologies, Controllability, Observability. New York: Springer, 1993
CharatonikW, Chorowska A. Parameterized complexity of basic decision problems for tree automata. International Journal of Computer Mathematics, 2013, 90(6): 348–356 https://doi.org/10.1080/00207160.2012.762451
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 https://doi.org/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 https://doi.org/10.1109/TAC.2010.2050161
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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1002/asjc.1294
29
ZhangG Q. Automata, Boolean matrices, and ultimate periodicity. Information and Computatioin, 1999, 152(1): 138–154 https://doi.org/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
31
HeC. Automata Theory and Its Applications. Beijing: Science Press, 1990
