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

He DENG; Yongyi YAN; Zengqiang CHEN

doi:10.1631/FITEE.2100561

Your Location：

Home >

Browse articles >

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

Regular Papers | Updated：2022-09-08

- A matrix-based static approach to analysis of finite state machines
  Enhanced Publication
- 一种基于矩阵的有限状态机静态分析方法
- Frontiers of Information Technology & Electronic Engineering Vol. 23, Issue 8, Pages: 1239-1246(2022)
- Affiliations：
  
  1.College of Information Engineering, Henan University of Science and Technology, Luoyang 471000, China
  2.College of Artificial Intelligence, Nankai University, Tianjin 300071, China
- Author bio：
  
  ‡Corresponding author
- Funds：
- DOI：10.1631/FITEE.2100561
  CLC： TP13
- Published：23 August 2022，
  
  Received：03 December 2021，
  
  Accepted：2022-02-23
- Accepted：
Scan QR Code
HE DENG, YONGYI YAN, ZENGQIANG CHEN. A matrix-based static approach to analysis of finite state machines. [J]. Frontiers of information technology & electronic engineering, 2022, 23(8): 1239-1246.
DOI：

HE DENG, YONGYI YAN, ZENGQIANG CHEN. A matrix-based static approach to analysis of finite state machines. [J]. Frontiers of information technology & electronic engineering, 2022, 23(8): 1239-1246. DOI： 10.1631/FITEE.2100561.

摘要

在有限状态机研究领域，传统矩阵法首先构造状态转移矩阵，然后利用状态转移矩阵的幂来表示系统动态转移过程。这一过程是有限状态机系统分析的基石。本文提出一种基于矩阵的静态方法。该方法从拓扑结构的视角审视有限状态机，而非传统动态转移过程的视角，因此能够避免现有方法中存在的“维度爆炸”问题。基于这种静态方法，本文重新分析确定有限状态机的闭环检测与可控性问题。此外，我们提出可控等价型与最小可控等价型概念，并给出相关算法。

Abstract

Traditional matrix-based approaches in the field of finite state machines construct state transition matrices

and then use the powers of the state transition matrices to represent corresponding dynamic transition processes

which are cornerstones of system analysis. In this study

we propose a static matrix-based approach that revisits a finite state machine from its structure rather than its dynamic transition process

thus avoiding the "explosion of complexity" problem inherent in the existing approaches. Based on the static approach

we reexamine the issues of closed-loop detection and controllability for deterministic finite state machines. In addition

we propose controllable equivalent form and minimal controllable equivalent form concepts and give corresponding algorithms.

关键词

逻辑系统有限值系统矩阵的半张量积有限状态机矩阵方法

Keywords

Logical systemsFinite-valued systemsSemi-tensor product of matricesFinite state machinesMatrix approaches

references

Chen ZQ, Zhou YR, Zhang ZP, et al., 2020. Semi-tensor product of matrices approach to the problem of fault detection for discrete event systems (DESs). IEEE Trans Circ Syst II Expr Briefs, 67(12):3098-3102. doi: 10.1109/TCSII.2020.2967062http://doi.org/10.1109/TCSII.2020.2967062

Cheng DZ, Qi HS, 2010. A linear representation of dynamics of Boolean networks. IEEE Trans Autom Contr, 55(10):2251-2258. doi: 10.1109/TAC.2010.2043294http://doi.org/10.1109/TAC.2010.2043294

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. doi: 10.1080/00207179.2017.1295319http://doi.org/10.1080/00207179.2017.1295319

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. doi: 10.1049/iet-cta.2016.1659http://doi.org/10.1049/iet-cta.2016.1659

Lu JQ, Sun LJ, Liu Y, et al., 2018. Stabilization of Boolean control networks under aperiodic sampled-data control. SIAM J Contr Optim, 56(6):4385-4404. doi: 10.1137/18M1169308http://doi.org/10.1137/18M1169308

Xu Q, Zhang ZP, Yan YY, et al., 2021. Security and privacy with K-step opacity for finite automata via a novel algebraic approach. Trans Inst Meas Contr, 43(16):3606-3614. doi: 10.1177/01423312211040314http://doi.org/10.1177/01423312211040314

Xu XR, Hong YG, 2013a. Matrix approach to model matching of asynchronous sequential machines. IEEE Trans Autom Contr, 58(11):2974-2979. doi: 10.1109/TAC.2013.2259957http://doi.org/10.1109/TAC.2013.2259957

Xu XR, Hong YG, 2013b. Observability analysis and observer design for finite automata via matrix approach. IET Contr Theory Appl, 7(12):1609-1615. doi: 10.1049/iet-cta.2013.0096http://doi.org/10.1049/iet-cta.2013.0096

Yan YY, Chen ZQ, Liu ZX, 2014. Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition. Front Comput Sci, 8(6):948-957. doi: 10.1007/s11704-014-3425-yhttp://doi.org/10.1007/s11704-014-3425-y

Yan YY, Deng H, Chen ZQ, 2021. A new look at the critical observability of finite state machines from an algebraic viewpoint. Asian J Contr, early access. doi: 10.1002/asjc.2705http://doi.org/10.1002/asjc.2705

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 Expr Briefs, 69(2):434-438. doi: 10.1109/TCSII.2021.3087189http://doi.org/10.1109/TCSII.2021.3087189

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

Zhu R, Chen ZQ, Zhang JL, et al., 2022. Strategy optimization of weighted networked evolutionary games with switched topologies and threshold. Knowl-Based Syst, 235:107644. doi: 10.1016/j.knosys.2021.107644http://doi.org/10.1016/j.knosys.2021.107644

Zhu SM, Feng JE, Sun LY, 2021. Matrix expression of Owen values. Asian J Contr, early access. doi: 10.1002/asjc.2738http://doi.org/10.1002/asjc.2738

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

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

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

Related Author

Jumei YUE

Chao DONG

Yongyi YAN

Huiqin LI

Jumei YUE

Chao DONG

Yongyi Yan

Huiqin Li

Related Institution

College of Agricultural Equipment Engineering, Henan University of Science and Technology

College of Information Engineering, Henan University of Science and Technology

College of Agricultural Equipment Engineering, Henan University of Science and Technology

National Center for Applied Mathematics in Chongqing, Chongqing Normal University

Institute of Mathematics, School of Mathematical Sciences, Nanjing Normal University

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰