Algebraic state space approach to model and control combined automata

doi:10.1007/s11704-016-5128-z

Front. Comput. Sci.

2017, Vol. 11

Issue (5) : 874-886 https://doi.org/10.1007/s11704-016-5128-z

RESEARCH ARTICLE

Algebraic state space approach to model and control combined automata

Yongyi YAN^1,², Zengqiang CHEN²(

), Jumei YUE³

¹. College of Information Engineering, Henan University of Science and Technology, Luoyang 471023, China
². College of Computer and Control Engineering, Nankai University, Tianjin 300071, China
³. College of Agricultural Engineering, Henan University of Science and Technology, Luoyang 471003, China

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

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

Corresponding Author(s): 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.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5128-z
https://academic.hep.com.cn/fcs/EN/Y2017/V11/I5/874

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 https://doi.org/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 https://doi.org/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 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
12	SakarovitchJ. Elements of Automata Theory.Cambridge: Cambridge University Press, 2009 https://doi.org/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 https://doi.org/10.1080/00207160.2012.762451
14	CzechL. On dynamics of automata with a stack. International Journal of Computer Mathematics, 2015, 92(3): 486–497 https://doi.org/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 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
19	LiF, SunJ. Controllability and optimal control of a temporal Boolean network. Neural Networks, 2012, 34(12): 10–17 https://doi.org/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 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

[1]

FCS-0874-15128-ZQC_suppl_1

Download

[1]	Yan-Ping SUN, Min-Ling ZHANG. Compositional metric learning for multi-label classification[J]. Front. Comput. Sci., 2021, 15(5): 155320-.
[2]	Shaobo DENG, Sujie GUAN, Min LI, Lei WANG, Yuefei SUI. Decomposition for a new kind of imprecise information system[J]. Front. Comput. Sci., 2018, 12(2): 376-395.
[3]	Ernst-Erich DOBERKAT. Using coalgebras and the Giry monad for interpreting game logics— a tutorial[J]. Front. Comput. Sci., 2017, 11(6): 948-970.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	Fei HE,Xiaoyu SONG,Ming GU,Jiaguang SUN. Generalized interface automata with multicast synchronization[J]. Front. Comput. Sci., 2015, 9(1): 1-14.
[12]	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.
[13]	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.
[14]	Jing LIU, Ziwei LIU, Jifeng HE, Frédéric MALLET, Zuohua DING. Hybrid MARTE statecharts[J]. Front Comput Sci, 2013, 7(1): 95-108.
[15]	Xiaoqin FAN, Xianwen FANG, Zhijun DING. Indeterminacy-aware service selection for reliable service composition[J]. Front Comput Sci Chin, 2011, 5(1): 26-36.

Viewed

Full text

Abstract

Cited

Shared

Discussed