Abstract: This paper uses the semi-tensor product (STP) of matrices and adopts algebraic methods to study the controllability, reachability, and stabilizability of extended finite state machines (EFSMs). First, we construct the bilinear dynamic system model of the EFSM, laying the foundation for further research. Second, combined with this bilinear dynamic system model, we propose theorems for the controllability, reachability, and stabilizability of the bilinear dynamic system model of the EFSM. Finally, we design an algorithm to determine the controllability and stabilizability of the EFSM. The correctness of the main results is verified through examples.

扩展有限状态机可控性、可达性和稳定性的半张量积方法

[1]Adak S, Mukherjee S, Das S, 2021. Reachability problem in non-uniform cellular automata. Inform Sci, 543:72-84.

[2]Boukerrou H, Millerioux G, Minier M, et al., 2022. Construction of dead-beat switched automata: application to cryptography. Proc 10^th Int Conf on Systems and Control, p.23-30.

[3]Chang Z, Ge AD, Sun MC, 2022. Interval type-2 fuzzy logic system based on semi-tensor product. Proc 41^st Chinese Control Conf, p.2507-2512.

[4]Cheng DZ, Qi HS, Li ZQ, 2011. Analysis and Control of Boolean Networks: a Semi-Tensor Product Approach. Springer, London, UK, p.29-37.

[5]Deng H, Yan YY, Chen ZQ, 2022. A matrix-based static approach to analysis of finite state machines. Front Inform Technol Electron Eng, 23(8):1239-1246.

[6]Dou WH, Li HT, Alsaadi FE, 2019. Semitensor product approach to controllability, reachability, and stabilizability of probabilistic finite automata. Math Probl Eng, 2019:>8021750>.

[7]Dridi S, El Yacoubi S, Bagnoli F, 2022. Kalman condition and new algorithm approach for regional controllability of peripherally-linear elementary cellular automata via boundary actions. J Cell Autom, 16(3-4):173-195.

[8]Foster M, Taylor RG, Brucker AD, et al., 2018. Formalising extended finite state machine transition merging. Proc 20^th Int Conf on Formal Engineering Methods, p.373-387.

[9]Glück R, 2023. Compatibility of refining and controlling plant automata with bisimulation quotients. Proc 20^th Int Conf on Relational and Algebraic Methods in Computer Science, p.87-104.

[10]Goorden M, van de Mortel-Fronczak J, Reniers M, et al., 2020. Structuring multilevel discrete-event systems with dependence structure matrices. IEEE Trans Autom Contr, 65(4):1625-1639.

[11]Han XG, Chen ZQ, 2018. A matrix-based approach to verifying stability and synthesizing optimal stabilizing controllers for finite-state automata. J Franklin Inst, 355(17):8642-8663.

[12]Han XG, Chen ZQ, Liu ZX, et al., 2018. The detection and stabilisation of limit cycle for deterministic finite automata. Int J Contr, 91(4):874-886.

[13]Henry L, Jéron T, Markey N, 2022. Control strategies for off-line testing of timed systems. Form Methods Syst Des, 60(2):147-194.

[14]Köcher C, 2021. Reachability problems on reliable and lossy queue automata. Theory Comput Syst, 65(8):1211-1242.

[15]Kong XS, Li HT, Gu EG, 2023. Lyapunov-based sampled-data set stabilisation of Boolean control networks with time delay and state constraint. Int J Contr, 97(5):1027-1036.

[16]Li HT, Zhao GD, Meng M, et al., 2018. A survey on applications of semi-tensor product method in engineering. Sci China Inform Sci, 61(1):010202.

[17]Li WR, Li HT, 2023. Set reachability and set stability of Boolean networks with state-dependent asynchronous updating rule. Asian J Contr, 25:4825-4833.

[18]Lin YD, Lai YK, Bui QT, et al., 2020. ReFSM: reverse engineering from protocol packet traces to test generation by extended finite state machines. J Netw Comput Appl, 171:>102819>.

[19]Lv ZY, Wu YH, Zhao Q, et al., 2022. Design and control of a novel coaxial tilt-rotor UAV. IEEE Trans Ind Electron, 69(4):3810-3821.

[20]Pilch C, Schupp S, Remke A, 2021. Optimizing reachability probabilities for a restricted class of stochastic hybrid automata via flowpipe-construction. Proc 18^th Int Conf on Quantitative Evaluation of Systems, p.435-456.

[21]Sun CL, Li HT, 2023. State-flipped control and Q-learning for finite horizon output tracking of Boolean control networks. Int J Syst Sci, 54(12):2452-2464.

[22]Wang B, Feng JE, 2019. On detectability of probabilistic Boolean networks. Inform Sci, 483:383-395.

[23]Wang SL, Li HT, 2019. Column stacking approach to resolution of systems of fuzzy relational inequalities. J Franklin Inst, 356(6):3314-3332.

[24]Wang XJ, Luo C, Li C, 2022. The feedback stabilization of finite-state fuzzy cognitive maps. Trans Inst Meas Contr, 44(13):2485-2499.

[25]Wang YH, Cheng DZ, Liu XY, 2019. Matrix expression of Shapley values and its application to distributed resource allocation. Sci China Inform Sci, 62(2):>22201>.

[26]Wu YH, Shen TL, 2017. Policy iteration approach to control residual gas fraction in IC engines under the framework of stochastic logical dynamics. IEEE Trans Contr Syst Technol, 25(3):1100-1107.

[27]Yan YY, Chen ZQ, Liu ZX, 2015. Semi-tensor product approach to controllability and stabilizability of finite automata. J Syst Eng Electron, 26(1):134-141.

[28]Yan YY, Yue JM, Chen ZQ, 2022. Observed data-based model construction of finite state machines using exponential representation of LMs. IEEE Trans Circ Syst II Express Briefs, 69(2):434-438.

[29]Yan YY, Cheng DZ, Feng JE, et al., 2023. Survey on applications of algebraic state space theory of logical systems to finite state machines. Sci China Inform Sci, 66(1):>111201>.

[30]Yao LH, Li JM, 2017. Input–output finite-time stabilization of a class of nonlinear hybrid systems based on FSM with MDADT. J Franklin Inst, 354(9):3797-3812.

[31]Zahn F, Kleinert T, Hagenmeyer V, 2022. Assessing the combination of differential flatness and deterministic automata for controllable hybrid systems. Proc 61^st Conf on Decision and Control, p.2612-2619.

[32]Zhang ZP, Chen ZQ, Han XG, et al., 2020. Stabilization of probabilistic finite automata based on semi-tensor product of matrices. J Franklin Inst, 357(9):5173-5186.

[33]Zoubeyr F, Tari A, Ouksel AM, 2010. Backward validation of communicating complex state machines in web services environments. Distrib Parallel Dat, 27(3):255-270.