研究带输出延迟的定时有限状态机的归位序列与同步序列

《Theoretical Computer Science》:Studying homing and synchronizing sequences for Timed Finite State Machines with output delays

【字体: 大 中 小 】 时间:2026年09月28日 来源:Theoretical Computer Science 1.1

编辑推荐:

   # 最终状态识别序列及其性质 ## 摘要 本文介绍了带有输出延迟的定时有限状态机(TFSM)的最终状态识别(同步与归位)序列,并研究了它们的性质。我们正式定义了这些TFSM的归位序列(HSs)和同步序列(SSs)的概念,并证明了一些对于非定时机器成立的性质不一定适用于定时

  

# 最终状态识别序列及其性质

## 摘要

本文介绍了带有输出延迟的定时有限状态机(TFSM)的最终状态识别(同步与归位)序列,并研究了它们的性质。我们正式定义了这些TFSM的归位序列(HSs)和同步序列(SSs)的概念,并证明了一些对于非定时机器成立的性质不一定适用于定时机器。此外,我们探讨了各种方法在推导带有输出延迟的定时有限状态机的SSs和HSs时的适用性,如基于截断后继树的方法和基于FSM抽象的方法。相应地,我们识别了这些方法可以直接应用的TFSM子类,以及需要其他(原始)方法的子类。此外,我们评估了带有输出延迟的TFSM中HSs/SSs的存在性检查和推导(最短)HSs/SSs的复杂度。

## 引言

定时有限状态机(TFSM)和定时自动机(TA)被广泛用于实时反应系统的分析和综合(参见例如近期的一些工作[1]、[2]、[3])。在许多情况下,待分析系统的当前状态是未知的,在这种情况下,首先需要将系统置于一个已知的稳定状态,才能进一步进行其分析(例如,应用测试用例、验证某些属性等)。同步和归位序列[4]是有限自动机(FA)和有限状态机(FSM)理论中的基本要素,它们允许将系统设置到已知状态。确实,SSs和HSs为"思想实验"[5]的同步和归位实验提供了基础,这些实验旨在识别机器的最终状态,即在应用序列后的状态。在FA和FSM的语境下,同步实验涉及应用SS使机器到达已知状态,无论其初始状态如何。相反,归位实验不仅涉及应用序列,还涉及观察相应的输出响应,以确定最终状态。

对于用定时有限状态机[6]建模的实时系统,"思想"实验的概念应该扩展到考虑输入和输出的定时方面。文献中已经采取了这些步骤;例如,在[7]和[8]中,作者通过为输入(或事件)关联时间戳来扩展经典实验。在本文中,我们在输出通道上增加了额外的观察点,以精确的时间戳捕获输入和输出。在这种设置下,输入在这些时间戳处被应用,输出在这些时间戳处被产生,这有时会增加最终状态识别问题的复杂度。该领域的主要研究挑战包括SSs和HSs的存在性检查的可判定性和计算复杂度,以及在可能的情况下推导此类最短序列。

经典FA和FSM的SSs和HSs的推导已被广泛研究,并由S. Sandberg[4]进行了总结,同时提供了推导这些序列的算法。这些算法可分为:(i) 迭代方法,通过组合为每对状态推导的序列来为整个机器构建SS(或HS)[9]、[10]、[4]、[11],(ii) 基于后继树的方法[12],通过对状态集合进行迭代拆分或合并来操作,以及(iii) 基于求解器的方法([13]和[14]),该方法用可满足公式来形式化机器被同步(归位)的条件。对于完全确定性的FSM,检查HSs(SSs)的存在性相对简单,可以在多项式时间内完成,而推导最短HS和SS的问题是NP-hard[4]。对于非确定性但可观测的FSM以及非确定性和部分FA,该问题变为PSPACE-hard[15]、[16]、[13]。

本文探讨了为[6]和[17]中考虑的带有输出延迟的TFSM推导SSs和HSs的各种策略。在带有输出延迟的TFSM中,每个转换都与一个定时守卫(区间)和一个输出延迟相关联。转换仅在应用的定时输入满足相应的定时守卫时执行,而输出延迟指定转换执行后产生输出所需的时间。后者允许TFSM在之前输入的输出仍在挂起时接受下一个输入。因此,这种TFSM行为考虑了可能并行的并发过程,用于计算和产生适当的输出。因此,所研究的TFSM具有以下特征:(i) 它作为定时输入/输出自动机运行,允许接受输入而无需等待其相应的输出,以及(ii) 它保留了FSM的属性,即输入数量与相应响应中的输出数量相等。这影响了所研究TFSM的SSs和HSs的性质。例如,我们证明对于这些TFSM,并非归位序列的每个延长都是归位序列。后者不允许"直接"适配迭代方法来推导带有输出延迟的TFSM的HS。尽管如此,我们证明存在所谓的非整数定时输入序列,对于这些序列,两端的延长都保持归位性质。因此,我们改编了截断后继树方法[18]来推导所研究TFSM的最短HS(SS)。

为定时机器推导SSs和HSs的另一种方法是将问题简化为定时机器的非定时抽象的SSs和HSs推导。这种简化通常通过构建区域自动机/FSM来实现(参见例如[19]、[20]、[21]、[8]、[22])。[8]和[22]中的作者已经证明,这种简化可以有效地应用于带有定时守卫的定时有限状态机[8]和带有超时的定时有限状态机[22]。然而,相同的简化不能直接适配本文中考虑的带有输出延迟的定时有限状态机。为了解决这个问题,我们提出修改[22]中引入的FSM抽象,以便于推导SSs和HSs。这激发了我们研究带有输出延迟的TFSM及其非定时抽象之间SSs和HSs的对应性质的动机。这也涉及比较定时和非定时机器中HSs(SSs)存在性检查和推导最短HS(SS)的复杂度。

本文的主要贡献如下:(i) 引入并定义带有输出延迟的TFSM的归位和同步序列,(ii) TFSM的HS和SS存在性检查和推导策略,以及相关复杂度分析,以及(iii) 在最终状态识别的背景下,研究后继树方法和/或FSM抽象适用或不适用的各种TFSM类。

本文的结构如下。第2节介绍了必要的背景知识。第3节介绍了带有输出延迟的TFSM的同步和归位序列及其性质,并调整了截断后继树用于其推导。第4节讨论了不同的FSM抽象推导TFSM的SS和HS的可能性。第5节总结了全文。

## 片段

### 有限状态机、归位和同步序列

有限状态机(FSM)[5]被定义为一个元组?=(??,??,??,???),其中S是有限的非空状态集,I(O)是有限的非空输入(输出)字母表,????S×??×??×S是转换关系。如果对于某些(s, i)∈S×I,存在至少两个不同的对(o′, s′)、(o″, s″)∈O×S,使得(s, i, o′, s′)∈???且(s, i, o″, s″)∈???,则我们说?是非确定性的;否则,FSM是确定性的。FSM ?是完备的,如果转换关系为……

### 最终状态识别序列及其性质

设??=(??,??,??,??,??,???)是一个带有输出延迟的TFSM,我们引入以下定义:

**定义5** 给定s, s′∈S,定时输入序列α对于状态s和s′是可合并的,如果next_state_??(s,α)=next_state_??(s′,α)≠⊥。

**定义6** 定时输入序列α对于??是同步的,如果存在s?∈S,使得对于每个s∈S,我们有next_state_??(s,α)=s?。

考虑TFSM ???(图2)在应用定时输入序列??=(???,2)(???,4)(???……后的行为。

### 区域FSM的推导

首先,考虑两台机器——图5和图6中的TFSM ???和FSM ??。可以容易地验证,??是通过忽略???的所有定时延迟和守卫来构建的,并且??没有归位序列。尽管根据定义7,TFSM ???具有归位序列??=(???,1.5)(???,3)。上述FSM抽象"遗忘"了所有定时参数,即转换的定时守卫和输出延迟,因此该例子表明我们不能简单地擦除所有关于时间的信息来……

## 结论与未来工作

在本文中,我们定义了带有输出延迟的定时有限状态机的同步和归位序列,并分析了它们的性质。我们为TFSM开发了新的SSs和HSs推导方法,并进行了相关的复杂度分析。此外,我们探索了这些序列在TFSM及其FSM抽象之间的对应关系。

本文开辟了许多未来工作方向。一个重要方向是解决推导……的挑战。

## CRediT作者贡献声明

Evgenii Vinarskii:撰写——初稿、可视化、方法学、调查研究、概念化。Jakub Ruszil:撰写——初稿、可视化、方法学、调查研究、概念化。Adam Roman:撰写——审阅与编辑、监督、方法学、概念化。Natalia Kushik:撰写——审阅与编辑、监督、方法学、概念化。

## 利益冲突声明

作者声明他们没有已知的竞争性经济利益或个人关系,这些关系可能会影响本文报告的工作。

Evgenii Vinarskii | Jakub Ruszil | Adam Roman | Natalia Kushik
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号