模糊线性时序逻辑的可实现性

模糊线性时序逻辑(fuzzy linear temporal logic)被应用于刻画模糊系统的规范语言,其可实现性(realizability)用于判断满足该时序逻辑公式的开放系统模型是否存在.模糊线性时序逻辑可实现性和系统合成(synthesis)的基本思想是:给定模糊线性时序逻辑公式,判断是否存在满足该公式的系统.如果存在,则构造满足该公式的最优系统.为了检验模糊线性时序逻辑的可实现性,首先引入模糊Büchi博弈的定义,作为检验模糊线性时序逻辑公式是否可实现的模型.其次通过归约的方法,研究模糊Büchi博弈的性质(最优无记忆策略存在性.最后验证模糊线性时序逻辑的可实现性并且给出其系统合成的过程,并说明它们的时间复杂度.

基于启发式SCCs的广义Büchi自动机判空检测算法

基于自动机理论模型检测的一个关键算法是判断有穷状态系统是否满足属性的判空检测.对标准Büchi自动机作判空检测,容易引起状态爆炸.本文以TGBA为研究对象,提出基于启发式SCCs的广义Büchi自动机判空检测算法.该算法在on-the-fly算法的基础上结合启发式深度优先搜索和SCCs检测算法,能较快地判断TGBA的非空性.通过正确性证明、复杂性分析和实验验证了该算法的正确可行性.在TGBA非空的情况下,该算法的时空性能比已有算法更优.

传播最大和最新接受前驱的On-the-Fly并行空性检测

针对一种结合最大接受前驱的on-the-fly并行空性检测方法,在接受环最大接受前驱处于环外的情境,无法通过传播接受前驱以on-the-fly方式识别接受环的问题,提出一种传播最大和最新接受前驱的on-the-fly并行空性检测方法.在首次遍历积自动机时,它采用最大接受前驱和最新接受前驱的双值传播模式,最大接受前驱仍保留原方法的传播特征,引入的最新接受前驱追踪并行空性检测的局部遍历特征,使其在原方法传播接受前驱识别失效时仍能on-the-fly识别接受环.理论证明了该算法的正确性,对比实验验证了该算法提前终止率更高,时空成本更低,on-the-fly优势更强.在软件模型检测领域,该方法为并行空性检测进一步控制状态空间爆炸,提供了一种有效途径.

Efficient approach of translating LTL formulae into Biichi automata

In explicit-state model checking, system proper- ties are typically expressed in linear temporal logic （LTL）, and translated into a BUchi automaton （BA） to be checked. In order to improve performance of the conversion algo- rithm, some model checkers involve the intermediate au- tomata, such as a generalized Btichi automaton （GBA）. The de-generalization is a translation from a GBA to a BA. In this paper, we present a conversion algorithm to translate an LTL formula to a BA directly. A labeling, acceptance degree, is presented to record acceptance conditions sat- isfied in each state and transition. Acceptance degree is a set of U-subformulae or F-subformulae of the given LTL formula. According to the acceptance degree, on-the-fly de- generalization algorithm, which is different from the standard de-generalization algorithm, is conceived and implemented. On-the-fly de-generalization algorithm is carried out during the expansion of the given LTL formula. It is performed in the case of the given LTL formula contains U-subformulae and F-subformulae, that is, the on-the-fly de-generalization algorithm is performed as required. In order to get a more deterministic BA, the shannon expansion is used recursively during expanding LTL formulae. Ordered binary decision diagrams are used to represent the BA and simplify LTL formulae. We compare the conversion algorithm presented in this paper to previous works, and show that it is more efficient for five families LTL formulae in common use and four setsof random formulae generated by LBTT （an LTL-to-BUchi translator testbench）.