| 谭锦豪,李国强.基本并行进程活性的限界模型检测.软件学报,2020,31(8):0 |
| 基本并行进程活性的限界模型检测 |
| Bounded Model Checking Liveness on Basic Parallel Processes |
| 投稿时间：2019-08-27 修订日期：2019-12-30 |
| DOI：10.13328/j.cnki.jos.005959 |
| 中文关键词: 基本并行进程 限界模型检测 活性 线性整数算术 SMT求解 |
| 英文关键词:basic parallel processes bounded model checking liveness linear integer arithmetic SMT solving |
| 基金项目:国家自然科学基金（61872232，61732013） |
|
| 摘要点击次数: 637 |
| 全文下载次数: 333 |
| 中文摘要: |
| 基本并行进程是一个用于描述和分析并发程序的模型，是Petri网的一个重要子类.EG逻辑是一种在Hennessy-Milner Logic的基础上增加EG算子的分支时间逻辑，其中的AF算子表示从当前的状态出发性质最终会被满足，因此EG逻辑是能够表达活性的逻辑.然而，基于基本并行进程的EG逻辑的模型检测问题是不可判定的.由此，本文提出了基本并行进程上EG逻辑的限界模型检测方法.首先，给出了基本并行进程上EG逻辑的限界语义，然后采用基于约束的方法，将基本并行进程上EG逻辑的限界模型检测问题转化为线性整数算术公式的可满足性问题，最后利用SMT求解器进行求解. |
| 英文摘要: |
| Basic parallel processes (BPPs) are a model for describing and analyzing concurrent programs, which is an importance subclass of Petri nets. The logic EG is a branching time logic obtained by extending Hennessy-Milner Logic with the EG operator, in which the AF operator means that a certain property will be satisfied eventually from the current state. Hence, the logic EG is a logic that can express liveness. However, model checking the logic EG over BPPs is undecidable. In this paper, we propose an algorithm for the problem of bounded model checking EG over BPPs. First, a bounded semantics of EG over BPPs is proposed. Then, according to the constraint-based approach, we give a reduction from the problem of bounded model checking EG over BPPs, to the satisfiability problem of linear integer arithmetic formulas. And finally, the linear integer arithmetic formulas are solved by SMT solvers. |
|
HTML 下载PDF全文 查看/发表评论 下载PDF阅读器 |
