Please wait a minute...
Frontiers of Information Technology & Electronic Engineering

ISSN 2095-9184

Frontiers of Information Technology & Electronic Engineering  2021, Vol. 22 Issue (12): 1598-1609   https://doi.org/10.1631/FITEE.2000608
  本期目录
从控制论观点审视有限状态自动机的状态空间优化
岳菊梅1(), 闫永义2(), 陈增强3, 邓鹤2
1. 河南科技大学农业装备工程学院,中国洛阳市,471003
2. 河南科技大学信息工程学院,中国洛阳市,471003
3. 南开大学人工智能学院,中国天津市,300071
State space optimization of finite state machines from the viewpoint of control theory
Jumei YUE1(), Yongyi YAN2(), Zengqiang CHEN3, He DENG2
1. College of Agricultural Equipment Engineering, Henan University of Science and Technology, Luoyang 471003, China
2. College of Information Engineering, Henan University of Science and Technology, Luoyang 471003, China
3. College of Artificial Intelligence, Nankai University, Tianjin 300071, China
 全文: PDF(577 KB)  
摘要:

现有大多数关于有限状态自动机(finite state machines, FSM)状态空间的优化方法不便甚至不能给出优化的数学意义。本文将FSM视为逻辑动态系统,借鉴控制论中动态系统平衡点的概念,引入t-等价状态和t-源等价状态概念。基于近年提出的FSM状态转移动力学方程,得到t-等价状态和t-源等价状态的数学描述(该数学描述可类比于控制论中关于动态系统平衡点的充要条件),进而给出该优化问题的数学解释。基于这些数学描述,设计了求解FSM所有t-等价状态和t-源等价状态的两种方法。此外,找到降低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.

Key wordsFinite state machines    Finite-valued systems    Logical systems    Logical networks    Semi-tensor product of matrices    Space optimization
收稿日期: 2020-11-06      出版日期: 2022-01-18
通讯作者: 岳菊梅,闫永义     E-mail: yjm@mail.nankai.edu.cn;yyyan@mail.nankai.edu.cn
Corresponding Author(s): Jumei YUE,Yongyi YAN   
 引用本文:   
岳菊梅, 闫永义, 陈增强, 邓鹤. 从控制论观点审视有限状态自动机的状态空间优化[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(12): 1598-1609.
Jumei YUE, Yongyi YAN, Zengqiang CHEN, He DENG. State space optimization of finite state machines from the viewpoint of control theory. Front. Inform. Technol. Electron. Eng, 2021, 22(12): 1598-1609.
 链接本文:  
https://academic.hep.com.cn/fitee/CN/10.1631/FITEE.2000608
https://academic.hep.com.cn/fitee/CN/Y2021/V22/I12/1598
[1] FITEE-1598-20005-JMY_suppl_1 Download
[2] FITEE-1598-20005-JMY_suppl_2 Download
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed