从控制论观点审视有限状态自动机的状态空间优化

岳菊梅; 闫永义; 陈增强; 邓鹤

doi:10.1631/FITEE.2000608

Your Location：

Home >

Browse articles >

从控制论观点审视有限状态自动机的状态空间优化

常规文章 | Updated：2022-06-14

- 从控制论观点审视有限状态自动机的状态空间优化
  Enhanced Publication
- State space optimization of finite state machines from the viewpoint of control theory
- 信息与电子工程前沿（英文） 2021年22卷第12期页码：1598-1609
- Affiliations：
  
  1.College of Agricultural Equipment Engineering, Henan University of Science and Technology, Luoyang471003, China
  2.College of Information Engineering, Henan University of Science and Technology, Luoyang471003, China
  3.College of Artificial Intelligence, Nankai University, Tianjin300071, China
- Author bio：
  
  E-mail: yjm@mail.nankai.edu.cn
  ‡Corresponding author
- Funds：
  
  National Natural Science Foundation of China(U1804150;62073124;61973175)
- DOI：10.1631/FITEE.2000608
  中图分类号： TP13
- 纸质出版日期：2021-12-0 ，
  
  网络出版日期：2021-10-23，
  
  收稿日期：2020-11-06，
  
  修回日期：2021-07-19，
  
  录用日期：2021-01-03
- Accepted：
Scan QR Code
岳菊梅, 闫永义, 陈增强, 等. 从控制论观点审视有限状态自动机的状态空间优化[J]. 信息与电子工程前沿（英文）, 2021,22(12):1598-1609.

JUMEI YUE, YONGYI YAN, ZENGQIANG CHEN, et al. State space optimization of finite state machines from the viewpoint of control theory. [J]. Frontiers of information technology & electronic engineering, 2021, 22(12): 1598-1609.
岳菊梅, 闫永义, 陈增强, 等. 从控制论观点审视有限状态自动机的状态空间优化[J]. 信息与电子工程前沿（英文）, 2021,22(12):1598-1609. DOI： 10.1631/FITEE.2000608.

JUMEI YUE, YONGYI YAN, ZENGQIANG CHEN, et al. State space optimization of finite state machines from the viewpoint of control theory. [J]. Frontiers of information technology & electronic engineering, 2021, 22(12): 1598-1609. DOI： 10.1631/FITEE.2000608.

摘要

现有大多数关于有限状态自动机（finite state machines，FSM）状态空间的优化方法不便甚至不能给出优化的数学意义。本文将FSM视为逻辑动态系统，借鉴控制论中动态系统平衡点的概念，引入

-等价状态和

-源等价状态概念。基于近年提出的FSM状态转移动力学方程，得到

-等价状态和

-源等价状态的数学描述（该数学描述可类比于控制论中关于动态系统平衡点的充要条件），进而给出该优化问题的数学解释。基于这些数学描述，设计了求解FSM所有

-等价状态和

-源等价状态的两种方法。此外，找到降低FSM状态空间的两种路径。可不借助计算机，仅用纸笔以数学推演方式实现。并且，为使所设计的方法借助计算机能完全以无人值守方式运行，提出一个开放性问题。最后，采用实际语言模型验证了结论的正确性和有效性。

Abstract

Motivated by the inconvenience or even inability to explain the mathematics of the state space optimization of finite state machines (FSMs) in most existing results

we consider the problem by viewing FSMs as logical dynamic systems. Borrowing ideas from the concept of equilibrium points of dynamic systems in control theory

the concepts of t-equivalent states and t-source equivalent states are introduced. Based on the state transition dynamic equations of FSMs proposed in recent years

several mathematical formulations of t-equivalent states and t-source equivalent states are proposed. These can be analogized to the necessary and sufficient conditions of equilibrium points of dynamic systems in control theory and thus give a mathematical explanation of the optimization problem. Using these mathematical formulations

two methods are designed to find all the t-equivalent states and t-source equivalent states of FSMs. Further

two ways of reducing the state space of FSMs are found. These can be implemented without computers but with only pen and paper in a mathematical manner. In addition

an open question is raised which can further improve these methods into unattended ones. Finally

the correctness and effectiveness of the proposed methods are verified by a practical language model.

关键词

有限状态自动机有限值系统逻辑系统逻辑网络矩阵半张量积空间优化

Keywords

Finite state machinesFinite-valued systemsLogical systemsLogical networksSemi-tensor product of matricesSpace optimization

references

WY Chen, . 2007. . The Theory of Finite Automata. , University of Electronic Science and Technology of China Press, , :Chengdu, China(in Chinese)..

DZ Cheng, , HS Qi, , Y Zhao, . 2012. . An Introduction to Semi-tensor Product of Matrices and Its Applications. , World Scientific, , :Singapore..

D Chu, , RE Spinney, . 2018. . A thermodynamically consistent model of finite-state machines. . Interf Focus, , 8((6):):20180037. doi: 10.1098/rsfs.2018.0037http://doi.org/10.1098/rsfs.2018.0037.

M Dahmoune, , EH El Abdalaoui, , D Ziadi, . 2014. . On the transition reduction problem for finite automata. . Fundam Inform, , 132((1):):79--94. . doi: 10.3233/fi-2014-1033http://doi.org/10.3233/fi-2014-1033.

MV de Parga, , P García, , D López, . 2013. . A polynomial double reversal minimization algorithm for deterministic finite automata. . Theor Comput Sci, , 487:17--22. . doi: 10.1016/j.tcs.2013.03.005http://doi.org/10.1016/j.tcs.2013.03.005.

N Gao, , XG Han, , ZQ Chen, , et al., . 2017. . A novel matrix approach to observability analysis of finite automata. . Int J Syst Sci, , 48((16):):3558--3568. ..

P García, , D López, , MV de Parga, . 2014. . Efficient deterministic finite automata split-minimization derived from Brzozowski’s algorithm. . Int J Found Comput Sci, , 25((6):):679--696. . doi: 10.1142/s0129054114500282http://doi.org/10.1142/s0129054114500282.

S Gören, , FJ Ferguson, . 2002. . Chesmin: a heuristic for state reduction in incompletely specified finite state machines. . Proc Design, Automation and Test in Europe Conf and Exhibition, p.. 248--254. . doi: 10.1109/DATE.2002.998280http://doi.org/10.1109/DATE.2002.998280..

S Gören, , FJ Ferguson, . 2007. . On state reduction of incompletely specified finite state machines. . Comput Electr Eng, , 33((1):):58--69. . doi: 10.1016/j.compeleceng.2006.06.001http://doi.org/10.1016/j.compeleceng.2006.06.001.

TN Grzes, , VV Solov’ev, . 2015. . Minimization of power consumption of finite state machines by splitting their internal states. . J Comput Syst Sci Int, , 54((3):):367--374. . doi: 10.1134/s1064230715030090http://doi.org/10.1134/s1064230715030090.

XG Han, , ZQ Chen, . 2018. . A matrix-based approach to verifying stability and synthesizing optimal stabilizing controllers for finite-state automata. . J Franklin Inst, , 355((17):):8642--8663. . doi: 10.1016/j.jfranklin.2018.09.009http://doi.org/10.1016/j.jfranklin.2018.09.009.

XG Han, , ZQ Chen, , ZX Liu, , et al., . 2018. . The detection and stabilisation of limit cycle for deterministic finite automata. . Int J Contr, , 91((4):):874--886. . doi: 10.1080/00207179.2017.1295319http://doi.org/10.1080/00207179.2017.1295319.

YS He, , ZH Yu, , L Jian, , et al., . 2019. . Fault correction of algorithm implementation for intelligentized robotic multipass welding process based on finite state machines. . Robot Comput-Int Manuf, , 59:28--35. . doi: 10.1016/j.rcim.2019.03.002http://doi.org/10.1016/j.rcim.2019.03.002.

SD Kamble, , NV Thakur, , PR Bajaj, . 2018. . Fractal coding based video compression using weighted finite automata. . Int J Amb Comput Intell, , 9((1):):115--133. . doi: 10.4018/IJACI.2018010107http://doi.org/10.4018/IJACI.2018010107.

AS Klimowicz, , VV Solov’ev, . 2013. . Minimization of incompletely specified Mealy finite-state machines by merging two internal states. . J Comput Syst Sci Int, , 52((3):):400--409. . doi: 10.1134/s106423071303009xhttp://doi.org/10.1134/s106423071303009x.

YM Li, , W Pedrycz, . 2007. . Minimization of lattice finite automata and its application to the decomposition of lattice languages. . Fuzzy Sets Syst, , 158((13):):1423--1436. . doi: 10.1016/j.fss.2007.03.003http://doi.org/10.1016/j.fss.2007.03.003.

DS Liu, , ZP Huang, , YM Zhang, , et al., . 2016. . Efficient deterministic finite automata minimization based on backward depth information. . PLoS ONE, , 11((11):):e0165864. doi: 10.1371/journal.pone.0165864http://doi.org/10.1371/journal.pone.0165864.

JQ Lu, , HT Li, , Y Liu, , et al., . 2017. . Survey on semi-tensor product method with its applications in logical networks and other finite-valued systems. . IET Contr Theory Appl, , 11((13):):2040--2047. ..

P Martinek, . 2018. . Some notes to minimization of multiset finite automata. . AIP Conf Proc, , 1978((1):):470019. doi: 10.1063/1.5044089http://doi.org/10.1063/1.5044089.

B Melnikov, . 2010. . Once more on the edge-minimization of nondeterministic finite automata and the connected problems. . Fundam Inform, , 104((3):):267--283. . doi: 10.3233/fi-2010-349http://doi.org/10.3233/fi-2010-349.

MA Perkowski, , L Jóźwiak, , W Zhao, . 2001. . Symbolic two-dimensional minimization of strongly unspecified finite state machines. . J Syst Archit, , 47((1):):15--28. . doi: 10.1016/s1383-7621(00)00038-2http://doi.org/10.1016/s1383-7621(00)00038-2.

VV Solov’ev, . 2010. . Minimization of Moore finite automata by internal state gluing. . J Commun Technol Electron, , 55((5):):584--592. . doi: 10.1134/s1064226910050153http://doi.org/10.1134/s1064226910050153.

VV Solov’ev, . 2011. . Minimization of Mealy finite state machines via internal state merging. . J Commun Technol Electron, , 56((2):):207--213. . doi: 10.1134/s1064226911020136http://doi.org/10.1134/s1064226911020136.

VV Solov’ev, . 2014. . Complex minimization method for finite state machines implemented on programmable logic devices. . J Comput Syst Sci Int, , 53((2):):186--194. . doi: 10.1134/s1064230714020154http://doi.org/10.1134/s1064230714020154.

VV Solov’ev, . 2017. . Minimization of Mealy finite-state machines by using the values of the output variables for state assignment. . J Comput Syst Sci Int, , 56((1):):96--104. . doi: 10.1134/s1064230717010129http://doi.org/10.1134/s1064230717010129.

C Voeten, , M van Zaanen, . 2018. . The influence of context on the learning of metrical stress systems using finite-state machines. . Comput Ling, , 44((2):):329--348. . doi: 10.1162/COLI_a_00317http://doi.org/10.1162/COLI_a_00317.

YB Wang, , YM Li, . 2018. . Minimization of lattice multiset finite automata. . J Intell Fuzzy Syst, , 35((1):):627--637. . doi: 10.3233/jifs-161382http://doi.org/10.3233/jifs-161382.

XR Xu, , YG Hong, . 2012. . Matrix expression and reachability analysis of finite automata. . J Contr Theory Appl, , 10((2):):210--215. . doi: 10.1007/s11768-012-1178-4http://doi.org/10.1007/s11768-012-1178-4.

YY Yan, , ZQ Chen, , ZX Liu, . 2015. . Semi-tensor product approach to controllability and stabilizability of finite automata. . J Syst Eng Electron, , 26((1):):134--141. . doi: 10.1109/jsee.2015.00018http://doi.org/10.1109/jsee.2015.00018.

YY Yan, , ZQ Chen, , JM Yue, , et al., . 2016. . STP approach to model controlled automata with application to reachability analysis of DEDS. . Asian J Contr, , 18((6):):2027--2036. . doi: 10.1002/asjc.1294http://doi.org/10.1002/asjc.1294.

YY Yan, , JM Yue, , ZM Fu, , et al., . 2019a. . Algebraic criteria for finite automata understanding of regular language. . Front Comput Sci, , 13((5):):1148--1150. . doi: 10.1007/s11704-019-6525-xhttp://doi.org/10.1007/s11704-019-6525-x.

YY Yan, , JM Yue, , ZQ Chen, , et al., . 2019b. . Algebraic expression and construction of control sets of graphs using semi-tensor product of matrices. . IEEE Access, , 7:113440--113451. . doi: 10.1109/access.2019.2935321http://doi.org/10.1109/access.2019.2935321.

YY Yan, , JM Yue, , ZQ Chen, . 2019c. . Algebraic method of simplifying Boolean networks using semi-tensor product of matrices. . Asian J Contr, , 21((6):):2569--2577. . doi: 10.1002/asjc.2125http://doi.org/10.1002/asjc.2125.

JM Yue, , YY Yan, . 2019. . Exponentiation representation of Boolean matrices in the framework of semi-tensor product of matrices. . IEEE Access, , 7:153819--153828. . doi: 10.1109/ACCESS.2019.2948357http://doi.org/10.1109/ACCESS.2019.2948357.

JM Yue, , YY Yan, , ZQ Chen, , et al., . 2019a. . Identification of predictors of Boolean networks from observed attractor states. . Math Method Appl Sci, , 42((11):):3848--3864. . doi: 10.1002/mma.5616http://doi.org/10.1002/mma.5616.

JM Yue, , YY Yan, , ZQ Chen, . 2019b. . Language acceptability of finite automata based on theory of semi-tensor product of matrices. . Asian J Contr, , 21((6):):2634--2643. . doi: 10.1002/asjc.2190http://doi.org/10.1002/asjc.2190.

JM Yue, , YY Yan, , ZQ Chen, . 2020a. . Matrix approach to simplification of finite state machines using semi-tensor product of matrices. . Asian J Contr, , 22((5):):2061--2070. . doi: 10.1002/asjc.2123http://doi.org/10.1002/asjc.2123.

JM Yue, , YY Yan, , ZQ Chen, . 2020b. . Three matrix conditions for the reduction of finite automata based on the theory of semi-tensor product of matrices. . Sci China Inform Sci, , 63((2):):129203. doi: 10.1007/s11432-018-9739-9http://doi.org/10.1007/s11432-018-9739-9.

KZ Zhang, , LJ Zhang, . 2016. . Observability of Boolean control networks: a unified approach based on finite automata. . IEEE Trans Autom Contr, , 61((9):):2733--2738. . doi: 10.1109/tac.2015.2501365http://doi.org/10.1109/tac.2015.2501365.

QL Zhang, , JE Feng, , YY Yan, . 2020. . Finite-time pinning stabilization of Markovian jump Boolean networks. . J Franklin Inst, , 357((11):):7020--7036. . doi: 10.1016/j.jfranklin.2020.05.010http://doi.org/10.1016/j.jfranklin.2020.05.010.

ZP Zhang, , ZQ Chen, , XG Han, , et al., . 2017. . Static output feedback stabilization of deterministic finite automata. . Proc 36th Chinese Control Conf, p., 2421--2425. . doi: 10.23919/ChiCC.2017.8027721http://doi.org/10.23919/ChiCC.2017.8027721.

ZP Zhang, , ZQ Chen, , ZX Liu, . 2018a. . Modeling and reachability of probabilistic finite automata based on semi-tensor product of matrices. . Sci China Inform Sci, , 61((12):):129202. doi: 10.1007/s11432-018-9507-7http://doi.org/10.1007/s11432-018-9507-7.

ZP Zhang, , ZQ Chen, , XG Han, , et al., . 2018b. . On the static output feedback stabilization of deterministic finite automata based upon the approach of semi-tensor product of matrix. . Kybernetika, , 54((1):):41--60. . doi: 10.14736/kyb-2018-1-0041http://doi.org/10.14736/kyb-2018-1-0041.

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

A matrix-based static approach to analysis of finite state machines

Semi-tensor product approach to controllability, reachability, and stabilizability of extended finite state machines

Controllability of Boolean control networks with multiple time delays in both states and controls

On observability of Galois nonlinear feedback shift registers over finite fields

New developments in control design techniques of logical control networks