从基于迁移的扩展Büchi自动机到Büchi自动机 被引量：7

1

作者 易锦 张文辉 《软件学报》 EI CSCD 北大核心 2006年第4期720-728,共9页

目前的模型检测方法中,有一种方法是基于自动机来实现的.具体做法是:将抽象出的系统模型用Büchi自动机来表示,将需要验证的性质用LTL(lineartemporallogic)公式来表达;然后将LTL公式取反后转化为Büchi自动机,并检查这两个自... 目前的模型检测方法中,有一种方法是基于自动机来实现的.具体做法是:将抽象出的系统模型用Büchi自动机来表示,将需要验证的性质用LTL(lineartemporallogic)公式来表达;然后将LTL公式取反后转化为Büchi自动机,并检查这两个自动机接受语言之间的包含关系.有一类LTL公式转化为Büchi自动机的算法是:在计算过程中,首先得到一个标注在迁移上的扩展Büchi自动机(transition-basedgeneralizedBüchiautomaton,简称TGBA),然后把这种扩展Büchi自动机转换成非扩展的Büchi自动机.针对这类转换算法,根据Büchi自动机接受语言的特点,重新定义了基于迁移的扩展Büchi自动机的求交运算,减少了需要复制的状态个数,使转换后的自动机具有较少的状态.测试的结果表明:对随机产生的公式,新算法相对于以往的算法有明显的优势. 展开更多

关键词 模型检测 büehi自动机 LTL 公式 TGbA

下载PDF 职称材料

Büchi自动机确定化分析工具

2

作者 马润哲 田聪 +1 位作者 王文胜 段振华 《软件学报》 EI CSCD 北大核心 2024年第9期4310-4323,共14页

无限字自动机的确定化是理论计算机研究重要的一部分,在形式化验证,时序逻辑,模型检测等方面有重要应用.自Büchi自动机提出半个世纪以来,其自动机的确定化算法始终是其中的基础.有别于当初只是在理论上对其大小上下界的探索,利用... 无限字自动机的确定化是理论计算机研究重要的一部分,在形式化验证,时序逻辑,模型检测等方面有重要应用.自Büchi自动机提出半个世纪以来,其自动机的确定化算法始终是其中的基础.有别于当初只是在理论上对其大小上下界的探索,利用日新月异的高性能计算机技术不失为一种有效的辅助手段.为了深入研究非确定性Büchi自动机确定化算法的实现过程,希望重点研究确定化过程中的索引能否继续被优化的问题,实现确定化研究工具NB2DR.可以对非确定性Büchi自动机进行高效的确定化,并通过工具提供的分析其确定化过程来达到对其确定化算法改进的目的.通过对生成的确定性无限字自动机的索引的深入分析来探索相关索引的理论.该工具还实现了可以根据需要的Büchi自动机的大小与字母表参数,生成确定化的Rabin自动机族,亦可以反向根据需要的指定索引的大小来生成全部Büchi自动机族,测试生成无限字自动机的等价性等功能. 展开更多

关键词 büchi自动机 Rabin自动机 无限字自动机确定化

下载PDF 职称材料

一种基于自动机理论的LTL检验符号优化方法

3

作者 钱俊彦 赵岭忠 古天龙 《计算机工程》 EI CAS CSCD 北大核心 2005年第23期20-21,27,共3页

模型检验是一种重要的形式化自动验证技术。检验一个模型是否满足LTL公式,可以把LTL公式转换为一个表示相同无穷状态序列的ω自动机,通过转换后的ω自动机与系统自动机的乘积判空来进行模型检验。由于自动机的体积是模型检验的一个关键... 模型检验是一种重要的形式化自动验证技术。检验一个模型是否满足LTL公式,可以把LTL公式转换为一个表示相同无穷状态序列的ω自动机,通过转换后的ω自动机与系统自动机的乘积判空来进行模型检验。由于自动机的体积是模型检验的一个关键性问题,为了得到尽可能小的自动机,在LTL公式转换为ω自动机之前,对LTL公式进行预处理来减少冗余,然后基于ROBDD,通过布尔技术优化自动机。 展开更多

关键词 线性时态逻辑 ω自动机 büfichi自动机 RObDD

下载PDF 职称材料

一种基于时态逻辑的有限状态系统验证方法 被引量：2

4

作者 杜慧敏 杨红丽 +1 位作者 高德远 韩俊刚 《西北工业大学学报》 EI CAS CSCD 北大核心 2000年第1期111-115,共5页

LPTL ( Linear Proposition Temporal Logic)与自动机之间有着紧密的联系 ,结合 LPTL语义和语法 ,提出一种从 LPTL公式导出 Büchi自动机的方法。导出的 Büchi自动机所接受的语言准确地表达了 LPTL公式所描述的特性。从而把由 ... LPTL ( Linear Proposition Temporal Logic)与自动机之间有着紧密的联系 ,结合 LPTL语义和语法 ,提出一种从 LPTL公式导出 Büchi自动机的方法。导出的 Büchi自动机所接受的语言准确地表达了 LPTL公式所描述的特性。从而把由 LPTL公式描述的系统设计规范的验证问题转换成检验 Büchi自动机的包含问题。 展开更多

关键词 命题时态逻辑 形式化验证 有限状态系统 自动机

下载PDF 职称材料

基于Büchi自动机化简的JavaMOP监控器构造方法 被引量：1

5

作者 叶玲玲 钱俊彦 查显伟 《桂林电子科技大学学报》 2019年第5期374-378,共5页

为了提高JavaMOP对程序运行时验证的效率,提出一种基于Büchi自动机化简的JavaMOP监控器构造方法,降低JavaMOP运行时验证的时间和内存开销。该方法将线性时态逻辑(linear temporal logic,简称LTL)描述的属性规范转化为Büchi自... 为了提高JavaMOP对程序运行时验证的效率,提出一种基于Büchi自动机化简的JavaMOP监控器构造方法,降低JavaMOP运行时验证的时间和内存开销。该方法将线性时态逻辑(linear temporal logic,简称LTL)描述的属性规范转化为Büchi自动机,利用自动机化简规则对Büchi自动机进行冗余化简,化简后的Büchi自动机再转化为确定性有限自动机,并由此得到监控器的抽象表示。实验结果表明,与JavaMOP现有监控器的方法相比,该方法能够得到更小的Büchi自动机,从而加速JavaMOP监控器的构造过程。 展开更多

关键词 运行时验证 JavaMOP 监控器 线性时态逻辑 büchi自动机

下载PDF 职称材料

基于启发式NDFS的模型检测新算法 被引量：1

6

作者 王曦 徐中伟 《小型微型计算机系统》 CSCD 北大核心 2012年第8期1740-1746,共7页

以带有多个可接受条件的广义Büchi自动机为研究对象,提出基于启发式NDFS的模型检测新算法.该算法结合on-the-fly算法与启发式NDFS算法,能较快地判断出广义Büchi自动机非空性,通过理论证明和实验验证了算法的正确性和可行性.... 以带有多个可接受条件的广义Büchi自动机为研究对象,提出基于启发式NDFS的模型检测新算法.该算法结合on-the-fly算法与启发式NDFS算法,能较快地判断出广义Büchi自动机非空性,通过理论证明和实验验证了算法的正确性和可行性.与已有算法相比,在广义Büchi自动机非空的情况下,该算法减少了系统状态空间的搜索,提高了检测效率,且能形成相应反例,为缓解形式化验证中的状态空间爆炸问题提供了有效的解决途径,为安全苛求系统的安全性保障提供了有力支撑,丰富了基于模型的软件形式化开发方法. 展开更多

关键词 模型检测 启发式NDFS 安全性验证 on-the-fly算法 büchi自动机

下载PDF 职称材料

一种利用非确定规划的LTL合成方法

7

作者 陆旭 于斌 +1 位作者 田聪 段振华 《软件学报》 EI CSCD 北大核心 2022年第8期2769-2781,共13页

LTL合成(linear temporal logic synthesis)是程序合成(program synthesis)的一类重要子问题,旨在自动构建一个控制器(controller),且要求该控制器和环境(environment)的行为交互满足给定的LTL公式.一般来说,可以将LTL合成定义为二人博... LTL合成(linear temporal logic synthesis)是程序合成(program synthesis)的一类重要子问题,旨在自动构建一个控制器(controller),且要求该控制器和环境(environment)的行为交互满足给定的LTL公式.一般来说,可以将LTL合成定义为二人博弈(two-player game)问题,博弈的双方是环境和控制器,该问题的解称为合成策略.近年来,有研究从理论角度讨论了LTL合成与非确定规划(non-deterministicplanning)的相关性.基于此,提出了一种新的利用非确定规划求解LTL合成问题的方法,并证明了方法的正确性和完备性.具体而言,首先获得LTL公式对应的Büchi自动机,结合二人博弈定义,将LTL合成问题转换为完全可观测的非确定规划模型;然后交由高效规划器求解.通过实验结果说明:与其他LTL合成方法相比,提出的基于规划的合成方法在解质量方面具有较大的优势,能够获得规模较小的合成策略. 展开更多

关键词 二人博弈 büchi自动机 LTL合成 非确定规划

下载PDF 职称材料

多处理器任务调度算法TDS的建模与验证 被引量：5

8

作者 李召妮 雷丽晖 李永明 《计算机科学》 CSCD 北大核心 2012年第11期301-304,F0003,共5页

在多处理器系统中,一个应用所要完成的任务可以分配给同一个处理器处理,也可以分配给多个处理器处理,所以传统的测试方法难以满足多处理器任务调度算法的验证。在此,提出一个基于扩展Büchi自动机的形式化模型,并用该模型来描述多... 在多处理器系统中,一个应用所要完成的任务可以分配给同一个处理器处理,也可以分配给多个处理器处理,所以传统的测试方法难以满足多处理器任务调度算法的验证。在此,提出一个基于扩展Büchi自动机的形式化模型,并用该模型来描述多处理器任务调度算法TDS(Task Duplication based Scheduling);用线性时序逻辑描述出算法TDS期望的一些性质;最后在该模型上验证了这些性质。该方法有效地克服了传统测试的局限性,保证了多处理器任务调度的可靠性。 展开更多

关键词 多处理器调度算法 线性时序逻辑 模型检测 扩展büchi自动机

下载PDF 职称材料

实时系统形式规格说明在PVS中的建立 被引量：1

9

作者 许庆国 缪淮扣 《计算机科学》 CSCD 北大核心 2006年第12期238-242,共5页

本文首先简介了时间自动机和时间B櫣chi自动机形式模型,结合时间化时序逻辑(TimedTemporalLogic)的语法和语义,利用定理证明器PVS(PrototypeVerificationSystem)实现了定义在时间自动机状态(或运行)上的时间化分支(或线性)时序逻辑规格... 本文首先简介了时间自动机和时间B櫣chi自动机形式模型,结合时间化时序逻辑(TimedTemporalLogic)的语法和语义,利用定理证明器PVS(PrototypeVerificationSystem)实现了定义在时间自动机状态(或运行)上的时间化分支(或线性)时序逻辑规格说明的形式体系。在此基础上,结合一个经典的实时系统实例,用该体系对其实时特性进行了形式描述和形式验证,并得到了良好的结果。 展开更多

关键词 实时系统 时间büchi自动机 时间化时序逻辑 PVS

下载PDF 职称材料

线性时序逻辑转换Büchi自动机的按需即时算法 被引量：2

10

作者 单来祥 覃征 +1 位作者 卢欣晔 卢正才 《清华大学学报（自然科学版）》 EI CAS CSCD 北大核心 2014年第2期281-288,共8页

将线性时序逻辑公式转换成Büchi自动机是显式模型检测中的关键环节,Tableau规则是常用转换算法。该文提出了基于Tableau规则的改进算法,将线性时序逻辑公式转换成基于迁移的Büchi自动机。通过在状态和迁移中加入∪公式的满足... 将线性时序逻辑公式转换成Büchi自动机是显式模型检测中的关键环节,Tableau规则是常用转换算法。该文提出了基于Tableau规则的改进算法,将线性时序逻辑公式转换成基于迁移的Büchi自动机。通过在状态和迁移中加入∪公式的满足信息,实现了用一个接受条件集合判断执行序列是否可接受,避免了使用多个接受条件集合进行判断。改进算法引入了按需即时(on-the-fly)去扩展化机制,算法展开状态节点的同时进行状态有效性检测,删除无效节点,合并等价状态和迁移,避免了后置化简。与其他转换工具进行比较实验表明,该算法具有执行速度快、生成自动机的状态数和迁移数少的特征。 展开更多

关键词 线性时序逻辑 基于迁移的büchi自动机 按需即时

原文传递

基于LTL Tableau的自动机构造

11

作者 刘万伟 王戟 陈火旺 《吉林大学学报（工学版）》 EI CAS CSCD 北大核心 2007年第1期132-135,共4页

基于线性时序逻辑(LTL)的模型检验是使用较为广泛的技术。该种模型检验最终归结为有穷自动机的判空问题,其复杂性来源于性质和模型乘积自动机的状态空间膨胀。作者提出了一种构造迟滞交换Co-Büchi自动机(Stuffer Alternating Co-B&... 基于线性时序逻辑(LTL)的模型检验是使用较为广泛的技术。该种模型检验最终归结为有穷自动机的判空问题,其复杂性来源于性质和模型乘积自动机的状态空间膨胀。作者提出了一种构造迟滞交换Co-Büchi自动机(Stuffer Alternating Co-Büchi)的具有线性复杂度的方法,该方法能够降低最终乘积自动机的空间复杂度。 展开更多

关键词 计算机软件 模型检验 LTL TAbLEAU Co—büchi自动机

下载PDF 职称材料

Büchi自动机的优化综述 被引量：1

12

作者 袁志斌 《计算机应用与软件》 CSCD 2010年第6期32-34,88,共4页

对Büchi自动机进行优化是提高基于自动机的模型检测效率的重要手段。对直接模拟关系、延迟模拟关系和公平模拟关系的概念,进行了比较,并探讨了基于这些模拟关系的自动机优化方法。基于左右语言的优化是完全基于自动机理论的优化方... 对Büchi自动机进行优化是提高基于自动机的模型检测效率的重要手段。对直接模拟关系、延迟模拟关系和公平模拟关系的概念,进行了比较,并探讨了基于这些模拟关系的自动机优化方法。基于左右语言的优化是完全基于自动机理论的优化方法,于是深入探讨了利用左右语言对Büchi自动机的优化绍方法。最后对未来的研究方向作了简要的介绍。 展开更多

关键词 büchi自动机 模拟 左右语言

下载PDF 职称材料