本文已被:浏览 1304次 下载 1801次
Received:March 11, 2016 Revised:April 08, 2016
Received:March 11, 2016 Revised:April 08, 2016
中文摘要: 演绎推理是形式化验证中一种重要的方法,具有可以处理无穷状态系统的优点.本文研究与实现关于交替式下推系统中可达性的证明,该系统可以将无穷证明树转换为有穷树.文中首先利用迭代收敛思想实现了饱和算法,并通过全排列算法实现了系统完备化;然后采用余归纳方式对搜索证明进行了优化;最后利用可视化技术对证明树在三维空间进行展示.
Abstract:Deductive reasoning is an important method in formal verification, which can address programs in infinite state systems. In this paper, a proof system is studied and implemented, where infinite proof trees transform into finite ones. Firstly, a saturation algorithm is implemented based on iterative convergence, and the completion of the saturated system is implemented using Full Permutation Algorithm; Secondly, an optimization of proof search is carried out by inductive method; At last, the proof tree is visualized in 3D space using visualization technology.
keywords: deductive reasoning formal verification alternating pushdown system infinite state systems visualization
文章编号: 中图分类号: 文献标志码:
基金项目:中法NSFC-ANR共同资助合作研究项目LOCALI(61161130530)
Author Name | Affiliation |
ZHOU Qing | Institute of Software, Chinese Academy of Sciences, Beijing 100190, China University of Chinese Academy of Sciences, Beijing 100190, China |
Author Name | Affiliation |
ZHOU Qing | Institute of Software, Chinese Academy of Sciences, Beijing 100190, China University of Chinese Academy of Sciences, Beijing 100190, China |
引用文本:
周青.关于交替式下推系统可达性证明的研究与实现.计算机系统应用,2016,25(11):69-76
ZHOU Qing.Research and Implementation of Reachability Proof for Alternating Pushdown System.COMPUTER SYSTEMS APPLICATIONS,2016,25(11):69-76
周青.关于交替式下推系统可达性证明的研究与实现.计算机系统应用,2016,25(11):69-76
ZHOU Qing.Research and Implementation of Reachability Proof for Alternating Pushdown System.COMPUTER SYSTEMS APPLICATIONS,2016,25(11):69-76