Logical Approach to Livelock and Deadlock of Deterministic Finite State Machines: Modelling and Finding

被引：0
|
作者：
Yan, Yongyi [1 ]
Yue, Jumei [2 ]
Chen, Zengqiang [3 ]
机构：
[1] Henan Univ Sci & Technol, Coll Informat Engn, Luoyang 471023, Henan, Peoples R China
[2] Henan Univ Sci & Technol, Coll Agr Equipment Engn, Luoyang 471023, Henan, Peoples R China
[3] Nankai Univ, Coll Artificial Intelligence, Tianjin 300071, Peoples R China
来源：
2021 PROCEEDINGS OF THE 40TH CHINESE CONTROL CONFERENCE (CCC) | 2021年
基金：
中国国家自然科学基金;
关键词：
Logical systems; logical networks; finite-valued systems; semi-tensor product of matrices; finite state machines; logical blocking; REACHABILITY ANALYSIS; AUTOMATA; DESIGN;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Inspired by the connections between logical dynamic systems and continuous variable dynamic systems, this paper addresses the modelling and finding of the livelock and deadlock of deterministic finite state machines (DFSMs) from a logical viewpoint, where a DFSM is viewed as a logical system by treating the input string and current state of a DFSM as the input signal and state of a logical system, respectively. A difference equation-like model is proposed to formulate the dynamics of DFSMs and the behavior of deadlock and livelock of DFSMs. Based on the model and by generalizing livelock and deadlock as a loop structure, a unified discriminate criterion is established by which whether a DFSM contains livelock or dead lock can be judged easily. Further, an algorithm is designed for finding all the livelocks and deadlocks for a given DFSM.
引用
收藏
页码：1 / 6
页数：6
相关论文
共 18 条
  • [1] An STP look at logical blocking of finite state machines: formulation, detection, and search
    Yan, Yongyi
    Hao, Penglei
    Yue, Jumei
    Li, Haitao
    Feng, Jun-E
    SCIENCE CHINA-INFORMATION SCIENCES, 2024, 67 (10)
  • [2] A matrix-based static approach to analysis of finite state machines
    Deng, He
    Yan, Yongyi
    Chen, Zengqiang
    FRONTIERS OF INFORMATION TECHNOLOGY & ELECTRONIC ENGINEERING, 2022, 23 (08) : 1239 - 1246
  • [3] Matrix approach to simplification of finite state machines using semi-tensor product of matrices
    Yue, Jumei
    Yan, Yongyi
    Chen, Zengqiang
    ASIAN JOURNAL OF CONTROL, 2020, 22 (05) : 2061 - 2070
  • [4] Equivalence checking and intersection of deterministic timed finite state machines
    Bresolin, Davide
    El-Fakih, Khaled
    Villa, Tiziano
    Yevtushenko, Nina
    FORMAL METHODS IN SYSTEM DESIGN, 2021, 59 (1-3) : 77 - 102
  • [5] Model-Reference Adaptive Control of Finite State Machines With Respect to States: A Matrix-Based Approach
    Yan, Yongyi
    Deng, He
    Yue, Jumei
    Chen, Zengqiang
    IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS, 2023, 70 (06) : 2171 - 2175
  • [6] Survey on applications of algebraic state space theory of logical systems to finite state machines
    Yan, Yongyi
    Cheng, Daizhan
    Feng, Jun-E.
    Li, Haitao
    Yue, Jumei
    SCIENCE CHINA-INFORMATION SCIENCES, 2023, 66 (01)
  • [7] STP Approach to Controlliability of Finite State Machines
    Yan Yongyi
    Chen Zengqiang
    Yue Jumei
    IFAC PAPERSONLINE, 2015, 48 (28): : 138 - 143
  • [8] Bounded sequence testing from deterministic finite state machines
    Ipate, Florentin
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (16-18) : 1770 - 1784
  • [9] STP-based verification and synthesis of state opacity for logical finite state machines
    Han, Weiwei
    Li, Yi
    Zhang, Zhipeng
    Xia, Chengyi
    INFORMATION SCIENCES, 2023, 641
  • [10] REVERSE REACHABILITY ANALYSIS - A NEW TECHNIQUE FOR DEADLOCK DETECTION ON COMMUNICATING FINITE-STATE MACHINES
    HUNG, YC
    CHEN, GH
    SOFTWARE-PRACTICE & EXPERIENCE, 1993, 23 (09) : 965 - 979
12