###
计算机系统应用英文版:2016,25(11):69-76
本文二维码信息
码上扫一扫!
关于交替式下推系统可达性证明的研究与实现
(1.中国科学院软件研究所, 北京 100190;2.中国科学院大学, 北京 100190)
Research and Implementation of Reachability Proof for Alternating Pushdown System
(1.Institute of Software, Chinese Academy of Sciences, Beijing 100190, China;2.University of Chinese Academy of Sciences, Beijing 100190, China)
摘要
图/表
参考文献
相似文献
本文已被:浏览 1198次   下载 1434
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.
文章编号:     中图分类号:    文献标志码:
基金项目:中法NSFC-ANR共同资助合作研究项目LOCALI(61161130530)
引用文本:
周青.关于交替式下推系统可达性证明的研究与实现.计算机系统应用,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