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

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

doi:10.1631/FITEE.2000608

Your Location：

Home >

Browse articles >

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

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

- 从控制论观点审视有限状态自动机的状态空间优化
- 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
- 收稿：2020-11-06，
  
  修回：2021-07-19，
  
  录用：2021-01-03，
  
  网络出版：2021-10-23，
  
  纸质出版：2021-12-0
- 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

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.0037 http://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-1033 http://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.005 http://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/s0129054114500282 http://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.998280 http://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.001 http://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/s1064230715030090 http://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.009 http://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.1295319 http://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.002 http://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.2018010107 http://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/s106423071303009x http://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.003 http://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.0165864 http://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.5044089 http://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-349 http://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-2 http://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/s1064226910050153 http://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/s1064226911020136 http://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/s1064230714020154 http://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/s1064230717010129 http://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_00317 http://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-161382 http://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-4 http://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.00018 http://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.1294 http://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-x http://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.2935321 http://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.2125 http://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.2948357 http://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.5616 http://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.2190 http://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.2123 http://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-9 http://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.2501365 http://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.010 http://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 36 th Chinese Control Conf , p. , 2421 - - 2425 . . doi: 10.23919/ChiCC.2017.8027721 http://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-7 http://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-0041 http://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