闫永义,李海涛,冯俊娥等 | STP视角下有限状态自动机的逻辑拥堵：描述、检测及搜索
文摘
科技
2024-10-25 12:01
安徽
![]()
![]()
研究团队
闫永义，郝鹏磊，岳菊梅：河南科技大学
李海涛：山东师范大学
冯俊娥：山东大学
文章下载
Yongyi YAN, Penglei HAO, Jumei YUE, Haitao LI & Jun-E FENG. An STP look at logical blocking of finite state machines: formulation, detection, and search. Sci China Inf Sci, 2024, 67(10): 202208, doi: 10.1007/s11432-022-4124-7
![]()
有限状态机（FSM）的逻辑阻塞问题在系统设计与控制中具有重要意义，尤其是死锁和活锁现象会严重影响系统活性，导致资源冲突与错误处理。因此，需要有效的方法来建模和检测这些状态。传统研究多依赖表格查找和状态转移图，虽然易用，但在数学分析上存在局限性，难以处理复杂系统。近年来，控制理论在FSM建模和分析中展现出潜力，特别是STP（半张量积）方法，为FSM状态演变提供了新视角。本研究旨在从控制理论角度探讨FSM的逻辑阻塞问题，提出系统的公式化检测与搜索框架，将FSM视为逻辑动态系统并引入类差分方程模型，从而更全面地理解和解决逻辑阻塞。这不仅丰富了理论研究，还为FSM及其网络的优化提供了新思路。讨论了有限状态机（FSM）的逻辑阻塞问题。把FSM看作一个逻辑系统，分析它在不同层面的表现，包括制定规则、检测和搜索问题。把触发FSM的事件当作输入信号，然后把FSM当前的状态理解为逻辑系统的状态，提出了一种新模型，用来描述FSM的逻辑阻塞现象。通过定义FSM中的循环结构，并利用这个新模型，建立了一种能够快速判断FSM是否发生了阻塞的标准。这些研究成果不仅适用于确定性FSM，还可扩展到非确定性FSM和FSM网络。提出的这种方法可能为解决FSM问题提供新的思路，同时也有助于理解人造规则系统和自然法则系统之间的关系。![]()
(1) 新型框架构建：提出一个从控制理论角度出发的框架，用于公式化检测和搜索有限状态机（FSM）中的逻辑阻塞。(2) STP方法应用：将半张量积（STP）方法用于FSM的逻辑阻塞分析，将FSM的状态演变表述为双线性动态方程，为逻辑系统的研究提供了新的视角。 (3) 循环结构概念引入：通过引入循环结构的概念，对死锁和活锁进行了更一般的描述，使得逻辑阻塞的理解和判定更加系统化，并提出了代数标准来判断FSM是否存在逻辑阻塞。![]()
![]()
