时间自动机与自动验证

给出时间自动机的基本概念，描述了区域自动机的构造方法，并且实现了区域自动机的构造算法，简述了通过时间自动机进行自动验证的过程，最后分析了区域自动机构算法的时间复杂度。     

时间自动机与信号自动机的互模拟算法

基于时间自动机的验证工具已被广泛应用于实时系统模型验证。信号自动机为一类实时系统建立了比时间自动机更适合的模型,但是它还不能用于实际的实时系统模型验证,因为没有验证算法可用。把信号自动机验证问题归约到了时间自动机验证问题：证明了两种自动机具有相同的识别语言能力,证明了二者具有双向模拟关系,并在此基础上提出了线性的互模拟算法。把互模拟算法和已有的时间自动机验证算法结合起来,就得到了信号自动机的验证算法,从而解决了对信号自动机模型的验证问题。     

一种时间自动机时钟离散化算法

稠密时间自动机被广泛应用于实时系统自动验证.然而其在补操作下不封闭,因而导致多种线性实时性质不可验证.离散时间自动机虽不存在此问题,但该模型表达能力偏弱.因此,提出了一种时间自动机时钟离散化算法,结合时钟物理约束因素,证明了新方法可有效解决上述问题.     

一种改进的实时系统可达性分析算法

首先简介了时间自动机、时钟区域、区域等价、时钟带的概念.利用时钟带,可以将时间自动机的无穷状态空间转化为有穷.实时系统的绝大多数安全性和部分活性可以通过可达性分析算法来验证.然而,当系统时钟个数较多时,用DBM存储时钟带,会造成内存空间的很大耗费.该文提出了用邻接表存储时钟带,给出了改进的算法,并对算法的空间复杂度作了分析.实验表明,当时钟个数大于5时能节约很大的内存空间,从而在一定程度上缓解了状态爆炸.     

基于混合策略的单模式匹配算法

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.     

时间ω-树自动机识别语言的一个条件

时间自动机被广泛用于实时系统验证和模型检验.为适应不同类型的系统验证需要,不少时间自动机的相关模型被提出.时间树自动机是这样的新模型之一.目前主要是针对时间树自动机识别的语言类及相关性质的研究.本文提出了时间树自动机识别语言的一个条件,并证明了结论的正确性.如果一个语言不能满足该条件,它一定不能被时间树自动机识别.这为证明一个具体语言不能被时间树自动机识别提供了思路.     

对时间输入/输出自动机一致性测试的改进

Jan.S等提出了对时间输入／输出自动机（TIOA）模型进行黑盒一致性测试的算法。针对其生成的测试序列数量太大这一问题，提出用可最小化的时间自动机（MTA）模型来描述稠密的实际系统，并用递归算法实现了对测试序列的首部即转换覆盖P的构造。由分析得出结论：使用MTA模型可使上述测试算法生成的测试序列的数量大大减少，从而在不影响其完全性的情况下使该算法更具实用性。     

基于自动机技术的XML复杂数据类型验证

复杂数据类型验证是XML文档验证的主要内容,是检查XML文档结构是否符合模式规则的关键.根据Schema规范中复杂数据类型的描述和自动机理论,提出了一种称为模式自动机的数据结构,讨论了将XML复杂数据类型结构转换成模式自动机的方法,并设计了用来验证文档结构的算法.使用模式自动机验证算法可以全面地发现XML文档中的结构错误并准确地给出相应的错误信息,在实际应用中具有很高的效率.     

一种时间自动机可达性检测方法

本文首先给出对时间自动机时钟约束作等价处理的方法,然后以一个例子详细说明如何构造时钟区域自动机以及对它作相应的可达性关系的分析。     

基于UPPAAL的铁路车站信号联锁系统模型验证

详细介绍了适于描述实时系统的形式化方法,时间自动机以及基于时间自动机的模型验证工具UPPAAL.给出了铁路车站信号系统中的联锁功能进路建立的时间自动机模型,并利用UPPALL对其进行了分析与验证.