An STP look at logical blocking of finite state machines: formulation, detection, and search  

作　　者：Yongyi YAN Penglei HAO Jumei YUE Haitao LI Jun-E FENG 

机构地区：[1]College of Information Engineering,Henan University of Science and Technology,Luoyang 471023,China [2]College of Agricultural Equipment Engineering,Henan University of Science and Technology,Luoyang 471023,China [3]School of Mathematics and Statistics,Shandong Normal University,Jinan 250014,China [4]School of Mathematics,Shandong University,Jinan 250100,China

出　　处：《Science China(Information Sciences)》2024年第10期328-338,共11页中国科学（信息科学）（英文版）

基　　金：supported in part by the National Natural Science Foundation of China (Grant Nos. U1804150, 62073124)。

摘　　要：The logical blocking of finite state machines(FSMs) is examined at the three levels of formulation,detection, and search from an STP viewpoint(semi-tensor product of matrices). The research idea regards an FSM as a logical system. The realizing method treats the event sequence exciting an FSM as the input signal of a logical system and treats the current states of an FSM as the states of a logical system. Based on a recently developed bilinear dynamic model of FSMs, a difference equation-like model is first proposed to describe the logical blocking. By defining a loop structure of FSMs and using the difference equation-like model, a criterion is built by which whether a given FSM is blocking can be easily judged. If it is, several algorithms are designed to find all the logical blocking of the FSM. Further, these results are extended to apply to the case of nondeterministic FSMs and, thus, to networks of FSMs. The proposed STP approach may provide a new angle for considering the problems of FSMs, and the presented results may strengthen the links between systems governed by human-designed rules and systems governed by natural laws.

关 键 词：semi-tensor product of matrices STP matrix approach finite-valued systems logical systems logical networks finite state machines 

分 类 号：TP13[自动化与计算机技术—控制理论与控制工程]