支持索引式的PPTL定理证明器的实现
作者:
作者简介:

王小兵(1979-),男,博士,副教授,博士生导师,CCF高级会员,主要研究领域为形式化方法,形式化验证,时序逻辑;李春奕(1996-),女,博士,CCF学生会员,主要研究领域为形式化方法,形式化验证,时序逻辑;寇蒙莎(1998-),女,硕士,CCF学生会员,主要研究领域为形式化方法,形式化验证,定理证明;赵亮(1984-),男,博士,副教授,CCF专业会员,主要研究领域为形式化方法,形式化验证,时序逻辑

通讯作者:

赵亮,E-mail:lzhao@xidian.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(61672403,61972301);陕西省重点研发计划(2020GY-043,2020GY-210)


Implementation of Theorem Prover for PPTL with Indexed Expressions
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [31]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    定理证明是目前主流的形式化验证方法,拥有强大的抽象和逻辑表达能力,且不存在状态空间爆炸问题,可用于有穷和无穷状态系统,但其不能完全自动化,并且要求用户掌握较强的数学知识.含索引式的命题投影时序逻辑(PPTL)是一种具有完全正则表达能力,并且包含LTL的时序逻辑,具有较强的建模和性质描述能力.目前,一个可靠完备的含索引式的PPTL公理系统已被构建,然而基于该公理系统的定理证明尚未得到良好工具的支持,存在证明自动化程度较低以及证明冗长易错的问题.鉴于此,首先设计了支持索引式的PPTL定理证明器的实现框架,包括公理系统的形式化与交互式定理证明;然后,在Coq中形式化定义了含索引式的PPTL公式、公理与推理规则,完成了框架中公理系统的实现;最后,通过两个实例的交互式证明验证了该定理证明器的可用性.

    Abstract:

    Theorem proving is a mainstream formal verification method, with a strong ability of abstraction and logical expression. It does not suffer from state space explosion and can be used to verify finite and infinite systems. Nevertheless, it cannot be fully automated and requires users to have deep mathematical knowledge. Propositional projection temporal logic with indexed expressions is a temporal logic with full regular expressiveness and subsumes LTL, having strong modeling and property describing ability. At present, a sound and complete axiom system for PPTL with indexed expressions is presented while the theorem proving based on it is not yet well supported by tools, which leads to the low automaticity, redundancy, and fallibility of theorem proving. Therefore, firstly, the implementation framework of the theorem prover for PPTL with indexed expressions is designed, including two parts, the formalization of the PPTL axiom system and interactive theorem proving. Then the formulas, axioms, and inference rules are formally defined in Coq, implementing the axiom system of the framework. Finally, the availability of the theorem prover is proved by the interactive proving of two proof examples.

    参考文献
    [1] Burch JR, Clarke EM, Long DE, McMillan KL, Dill DL. Symbolic model checking for sequential circuit verification. IEEE Trans. on Computer-aided Design of Integrated Circuits and Systems, 1994, 13(4):401-424.
    [2] Bledsoe W, Loveland D. Automated Theorem Proving:After 25 Years. American Mathematical Society, 1984.[doi:http://dx.doi.org/10.1090/conm/029]
    [3] Bérard B, Bidoit M, Finkel A, Laroussinie F, Petit A, Petrucci L, Schnoebelen P, McKenzie P. Systems and Software Verification:Model-checking Techniques and Tools. Berlin, Heidelberg:Springer, 2001.
    [4] Gabbay D, Pnueli A, Shelah S, Stavi J. On the temporal basis of fairness. In:Proc. of the 7th Annual ACM Symp. on Principles of Programming Languages. 1980. 163-173.
    [5] Pnueli A, Kesten Y. A deductive proof system for CTL. In:Proc. of the 13th Int'l Conf. on Concurrency Theory. London:Springer, 2002. 24-40.
    [6] Moszkowski BC. An automata-theoretic completeness proof for interval temporal logic. In:Proc. of the Int'l Colloquium on Automata, Languages, and Programming. Berlin, Heidelberg:Springer, 2000. 223-234.
    [7] Cini C, Francalanza A. An LTL proof system for runtime verification. In:Proc. of the Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. Berlin, Heidelberg:Springer, 2015. 581-595.
    [8] Dax C, Hofmann M, Lange M. A proof system for the linear time m-calculus. In:Proc. of the Int'l Conf. on Foundations of Software Technology& Theoretical Computer Science. Berlin, Heidelberg:Springer, 2006.
    [9] Bolotov A, Basukoski A, Grigorievy O, Shangin V. Natural deduction calculus for linear-time temporal logic. In:Proc. of the European Workshop on Logics in Artificial Intelligence. Berlin, Heidelberg:Springer, 2006. 56-58.
    [10] Moszkowski B. A complete axiom system for propositional interval temporal logic with infinite time. Logical Methods in Computer Science, 2012, 8(3:10):1-56.
    [11] Duan ZH. Temporal Logic and Temporal Logic Programming. Beijing:Science Press, 2005.
    [12] Tian C, Duan ZH. Expressiveness of propositional projection temporal logic with star. Theoretical Computer Science, 2011, 412:1729-1744.
    [13] Duan ZH, Zhang N, Koutny M. A complete proof system for propositional projection temporal logic. Theoretical Computer Science, 2013, 497:84-107.
    [14] Duan ZH, Zhang N. A complete axiomatization for propositional projection temporal logic. In:Proc. of the 2nd IFIP/IEEE Int'l Symp. on Theoretical Aspects of Software Engineering. Washington:IEEE Computer Society, 2008. 271-278.
    [15] Zhang N, Duan ZH, Tian C. A formal proof of the deadline driven scheduler in PPTL axiomatic system. Theoretical Computer Science, 2014, 554:229-253.
    [16] Zhang N, Yang MF, Gu B, Duan ZH, Tian C. Verifying safety critical task scheduling systems in PPTL axiom system. Journal of Combinatorial Optimization, 2016, 31(2):577-603.
    [17] Duan ZH, Tian C, Zhang N, Ma Q, Du HW. Index set expressions can represent temporal logic formulas. Theoretical Computer Science, 2019, 788:21-38.
    [18] Zhao L, Wang XB, Shu XF, Zhang N. A sound and complete proof system for a unified temporal logic. Theoretical Computer Science, 2020, 838:25-44.
    [19] Harrison H, Urban J, Wiedijk F. History of interactive theorem proving. Handbook of the History of Logic, 2014, 9:135-214.
    [20] Kalvala S. Using Isabelle to prove simple theorems. In:Proc. of the HOL Users'Group Workshop. Berlin, Heidelberg:Springer, 1993. 514-517.
    [21] Bertot Y, Castéran P. Interactive theorem proving and program development. In:Coq'Art:The Calculus of Inductive Constructions. Berlin, Heidelberg:Springer, 2004.
    [22] Brock B, Kaufmann M, Moore JS. ACL2 theorems about commercial microprocessors. In:Proc. of the Int'l Conf. on Formal Methods in Computer-aided Design. Berlin, Heidelberg:Springer, 1996. 275-293.
    [23] Evans N, Schneider S. Verifying security protocols with PVS:Widening the rank function approach. The Journal of Logic and Algebraic Programming, 2005, 64(2):253-284.
    [24] Doorn FV. Propositional calculus in Coq. 2015. http://arxiv.org/abs/1503.08744v2
    [25] Cau A, Zedan H. Refining interval temporal logic specifications. In:Proc. of the 4th Int'l AMAST Workshop on Real-time Systems and Concurrent and Distributed Software. Mallorca, 1997. 79-94.
    [26] Pnueli A, Arons T. TLPVS:A PVS-based LTL verification system. In:Verification:Theory and Practice. Berlin, Heidelberg:Springer, 2003. 598-625.
    [27] Ma Q. Constraint solving and formal verification with MSVL[Ph.D. Thesis]. Xi'an:Xidian University, 2015(in Chinese with English abstract).
    [28] Qian L, Duan ZH, Zhang N, Tian C. A proof system for MSVL programs in Coq. In:Proc. of the Int'l Workshop on Structured Object-oriented Formal Language and Method. Cham:Springer, 2016. 121-143.
    [29] Barras B, Boutin S, Cornes C. The Coq Proof Assistant Reference Manual. 6th ed., Inria, 1997.
    [30] Duan ZH, Tian C. A practical decision procedure for propositional projection temporal logic with innite models. Theoretical Computer Science, 2014, 554:169-190.
    附中文参考文献:
    [27] 马倩. MSVL语言的约束求解与形式验证[博士学位论文].西安:西安电子科技大学, 2015.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王小兵,寇蒙莎,李春奕,赵亮.支持索引式的PPTL定理证明器的实现.软件学报,2022,33(6):2172-2188

复制
分享
文章指标
  • 点击次数:936
  • 下载次数: 3522
  • HTML阅读次数: 2635
  • 引用次数: 0
历史
  • 收稿日期:2021-09-04
  • 最后修改日期:2021-10-14
  • 在线发布日期: 2022-01-28
  • 出版日期: 2022-06-06
文章二维码
您是第19727256位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号