Frontiers of Information Technology & Electronic Engineering
>> 2021,
Volume 22,
Issue 12
doi:
10.1631/FITEE.2000608
State space optimization of finite state machines from the viewpoint of control theory
Affiliation(s): College of Agricultural Equipment Engineering, Henan University of Science and Technology, Luoyang 471003, China; College of Information Engineering, Henan University of Science and Technology, Luoyang 471003, China; College of Artificial Intelligence, Nankai University, Tianjin 300071, China; less
Received: 2020-11-06
Accepted: 2021-12-23
Available online: 2021-12-23
Next
Previous
Abstract
Motivated by the inconvenience or even inability to explain the mathematics of the state of (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 -equivalent states and -source equivalent states are introduced. Based on the state transition dynamic equations of FSMs proposed in recent years, several mathematical formulations of -equivalent states and -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 -equivalent states and -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.