Full Text:   <1577>

Summary:  <153>

CLC number: TP13

On-line Access: 2021-12-23

Received: 2020-11-06

Revision Accepted: 2021-01-03

Crosschecked: 2021-07-19

Cited: 0

Clicked: 2633

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Jumei Yue

https://orcid.org/0000-0003-1474-0088

Yongyi Yan

https://orcid.org/0000-0002-7181-5894

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2021 Vol.22 No.12 P.1598-1609

http://doi.org/10.1631/FITEE.2000608


State space optimization of finite state machines from the viewpoint of control theory


Author(s):  Jumei Yue, Yongyi Yan, Zengqiang Chen, He Deng

Affiliation(s):  College of Agricultural Equipment Engineering, Henan University of Science and Technology, Luoyang 471003, China; more

Corresponding email(s):   yjm@mail.nankai.edu.cn, yyyan@mail.nankai.edu.cn

Key Words:  Finite state machines, Finite-valued systems, Logical systems, Logical networks, Semi-tensor product of matrices, Space optimization


Jumei Yue, Yongyi Yan, Zengqiang Chen, He Deng. 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.

@article{title="State space optimization of finite state machines from the viewpoint of control theory",
author="Jumei Yue, Yongyi Yan, Zengqiang Chen, He Deng",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="22",
number="12",
pages="1598-1609",
year="2021",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2000608"
}

%0 Journal Article
%T State space optimization of finite state machines from the viewpoint of control theory
%A Jumei Yue
%A Yongyi Yan
%A Zengqiang Chen
%A He Deng
%J Frontiers of Information Technology & Electronic Engineering
%V 22
%N 12
%P 1598-1609
%@ 2095-9184
%D 2021
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2000608

TY - JOUR
T1 - State space optimization of finite state machines from the viewpoint of control theory
A1 - Jumei Yue
A1 - Yongyi Yan
A1 - Zengqiang Chen
A1 - He Deng
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 22
IS - 12
SP - 1598
EP - 1609
%@ 2095-9184
Y1 - 2021
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2000608


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.

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

岳菊梅1,闫永义2,陈增强3,邓鹤2
1河南科技大学农业装备工程学院,中国洛阳市,471003
2河南科技大学信息工程学院,中国洛阳市,471003
3南开大学人工智能学院,中国天津市,300071
摘要:现有大多数关于有限状态自动机(finite state machines, FSM)状态空间的优化方法不便甚至不能给出优化的数学意义。本文将FSM视为逻辑动态系统,借鉴控制论中动态系统平衡点的概念,引入t-等价状态和t-源等价状态概念。基于近年提出的FSM状态转移动力学方程,得到t-等价状态和t-源等价状态的数学描述(该数学描述可类比于控制论中关于动态系统平衡点的充要条件),进而给出该优化问题的数学解释。基于这些数学描述,设计了求解FSM所有t-等价状态和t-源等价状态的两种方法。此外,找到降低FSM状态空间的两种路径。可不借助计算机,仅用纸笔以数学推演方式实现。并且,为使所设计的方法借助计算机能完全以无人值守方式运行,提出一个开放性问题。最后,采用实际语言模型验证了结论的正确性和有效性。

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

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

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

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

[3]Chu D, Spinney RE, 2018. A thermodynamically consistent model of finite-state machines. Interf Focus, 8(6):20180037.

[4]Dahmoune M, El Abdalaoui EH, Ziadi D, 2014. On the transition reduction problem for finite automata. Fundam Inform, 132(1):79-94.

[5]de Parga MV, García P, López D, 2013. A polynomial double reversal minimization algorithm for deterministic finite automata. Theor Comput Sci, 487:17-22.

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

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

[8]Gören S, Ferguson FJ, 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.

[9]Gören S, Ferguson FJ, 2007. On state reduction of incompletely specified finite state machines. Comput Electr Eng, 33(1):58-69.

[10]Grzes TN, Solov’ev VV, 2015. Minimization of power consumption of finite state machines by splitting their internal states. J Comput Syst Sci Int, 54(3):367-374.

[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]He YS, Yu ZH, Jian L, 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.

[14]Kamble SD, Thakur NV, Bajaj PR, 2018. Fractal coding based video compression using weighted finite automata. Int J Amb Comput Intell, 9(1):115-133.

[15]Klimowicz AS, Solov’ev VV, 2013. Minimization of incompletely specified Mealy finite-state machines by merging two internal states. J Comput Syst Sci Int, 52(3):400-409.

[16]Li YM, Pedrycz W, 2007. Minimization of lattice finite automata and its application to the decomposition of lattice languages. Fuzzy Sets Syst, 158(13):1423-1436.

[17]Liu DS, Huang ZP, Zhang YM, et al., 2016. Efficient deterministic finite automata minimization based on backward depth information. PLoS ONE, 11(11):e0165864.

[18]Lu JQ, Li HT, Liu Y, 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.

[19]Martinek P, 2018. Some notes to minimization of multiset finite automata. AIP Conf Proc, 1978(1):470019.

[20]Melnikov B, 2010. Once more on the edge-minimization of nondeterministic finite automata and the connected problems. Fundam Inform, 104(3):267-283.

[21]Perkowski MA, Jóźwiak L, Zhao W, 2001. Symbolic two-dimensional minimization of strongly unspecified finite state machines. J Syst Archit, 47(1):15-28.

[22]Solov’ev VV, 2010. Minimization of Moore finite automata by internal state gluing. J Commun Technol Electron, 55(5):584-592.

[23]Solov’ev VV, 2011. Minimization of Mealy finite state machines via internal state merging. J Commun Technol Electron, 56(2):207-213.

[24]Solov’ev VV, 2014. Complex minimization method for finite state machines implemented on programmable logic devices. J Comput Syst Sci Int, 53(2):186-194.

[25]Solov’ev VV, 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.

[26]Voeten C, van Zaanen M, 2018. The influence of context on the learning of metrical stress systems using finite-state machines. Comput Ling, 44(2):329-348.

[27]Wang YB, Li YM, 2018. Minimization of lattice multiset finite automata. J Intell Fuzzy Syst, 35(1):627-637.

[28]Xu XR, Hong YG, 2012. Matrix expression and reachability analysis of finite automata. J Contr Theory Appl, 10(2):210-215.

[29]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.

[30]Yan YY, Chen ZQ, Yue JM, et al., 2016. STP approach to model controlled automata with application to reachability analysis of DEDS. Asian J Contr, 18(6):2027-2036.

[31]Yan YY, Yue JM, Fu ZM, et al., 2019a. Algebraic criteria for finite automata understanding of regular language. Front Comput Sci, 13(5):1148-1150.

[32]Yan YY, Yue JM, Chen ZQ, et al., 2019b. Algebraic expression and construction of control sets of graphs using semi-tensor product of matrices. IEEE Access, 7:113440-113451.

[33]Yan YY, Yue JM, Chen ZQ, 2019c. Algebraic method of simplifying Boolean networks using semi-tensor product of matrices. Asian J Contr, 21(6):2569-2577.

[34]Yue JM, Yan YY, 2019. Exponentiation representation of Boolean matrices in the framework of semi-tensor product of matrices. IEEE Access, 7:153819-153828.

[35]Yue JM, Yan YY, Chen ZQ, et al., 2019a. Identification of predictors of Boolean networks from observed attractor states. Math Method Appl Sci, 42(11):3848-3864.

[36]Yue JM, Yan YY, Chen ZQ, 2019b. Language acceptability of finite automata based on theory of semi-tensor product of matrices. Asian J Contr, 21(6):2634-2643.

[37]Yue JM, Yan YY, Chen ZQ, 2020a. Matrix approach to simplification of finite state machines using semi-tensor product of matrices. Asian J Contr, 22(5):2061-2070.

[38]Yue JM, Yan YY, Chen ZQ, 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.

[39]Zhang KZ, Zhang LJ, 2016. Observability of Boolean control networks: a unified approach based on finite automata. IEEE Trans Autom Contr, 61(9):2733-2738.

[40]Zhang QL, Feng JE, Yan YY, 2020. Finite-time pinning stabilization of Markovian jump Boolean networks. J Franklin Inst, 357(11):7020-7036.

[41]Zhang ZP, Chen ZQ, Han XG, et al., 2017. Static output feedback stabilization of deterministic finite automata. Proc 36th Chinese Control Conf, p.2421-2425.

[42]Zhang ZP, Chen ZQ, Liu ZX, 2018a. Modeling and reachability of probabilistic finite automata based on semi-tensor product of matrices. Sci China Inform Sci, 61(12):129202.

[43]Zhang ZP, Chen ZQ, Han XG, 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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE