Complete Axiomatization for Projection Temporal Logic with Finite Time
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [16]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    To verify the properties of concurrent and reactive systems based on the theorem proving approach, a complete axiomatization is formulized over finite domains for first order projection temporal logic (PTL) with finite time. First, the syntax, semantics and the axiomatization of PTL are presented; next, a normal form (NF) and a normal form graph (NFG) of PTL formulas are defined respectively; further, the algorithm for constructing the NFG is formalized upon the NF; moreover, the decision theorem for PTL formulas and the completeness of the axiomatic system have been proven to be based on the property that the NFG can-describe the models of PTL formulas; finally, an example is given to illustrate how to do system verification based on PTL and its axiomatic system, and the results indicate that the PTL based theorem proving approach can be conveniently applied to modeling and verification of concurrent systems.

    Reference
    [1] Duan ZH. An extended interval temporal logic and a framing technique for temporal logic programming [Ph.D. Thesis]. University of Newcastle Upon Tyne, 1996.
    [2] Moszkowski B. Executing temporal logic programs [Ph.D. Thesis]. Cambridge: Cambridge University Press, 1986.
    [3] Duan ZH, Yang XX, Koutny M. Framed temporal logic programming. Science of Computer Programming, 2008,70(1):31?61. [doi: 10.1016/j.scico.2007.09.001]
    [4] Duan ZH, Tian C. A unified model checking approach with projection temporal logic. In: Proc. of the 10th Int’l Conf. on Formal Engineering Methods (ICFEM 2008). LNCS 5256, Berlin: Springer-Verlag, 2008. 167?186. [doi: 10.1007/978-3-540-88194-0_12]
    [5] Wang XB, Duan ZH. Object-Oriented temporal logic language. Journal of University of Electronic Science and Technology of China, 2009,38(1):97?101 (in Chinese with English abstract).
    [6] Lei LH, Duan ZH. Specification and verification of composite Web services based on extended projection temporal logic. Journal of Xi’an Jiaotong University, 2007,41(10):1155?1159 (in Chinese with English abstract).
    [7] Xiao MH, Xue JY. Formal description of properties of concurrency system by temporal logic. Journal of Naval University of Engineering, 2004,16(5):10?13 (in Chinese with English abstract).
    [8] Bowman H, Thompson S. A decision procedure and complete axiomatization of finite interval temporal logic with projection. Journal of Logic and Computation, 2003,13(2):195?239. [doi: 10.1093/logcom/13.2.195]
    [9] Moszkowski B. A hierarchical completeness proof for propositional interval temporal logic with finite time. Journal of Applied Non-Classical Logics, 2004,14(1-2):55?104. [doi: 10.1007/978-3-540-39910-0_22]
    [10] Abadi M. The power of temporal proofs. Theoretical Computer Science, 1989,65(1):35?83. [doi: 10.1016/0304-3975(89)90138-2]
    [11] Cook S. Soundness and completeness of an axiom system for program verification. SIAM Journal on Computing, 1978,7(1):70?90. [doi: 10.1137/0207005]
    [12] Hodkinson I, Wolter F, Zakharyaschev M. Decidable fragments of first-order temporal logics. Annals of Pure and Applied Logic, 2000,106:85?134. [doi: 10.1016/S0168-0072(00)00018-X]
    [13] Shu XF, Duan ZH. Axiomatization for the first-order projection temporal logic and formal verifications. Journal of Xidian University, 2009,36(4):680?685 (in Chinese with English abstract).
    [14] Kesten Y, Pnueli A. Complete proof system for QPTL. Journal of Logic and Computation, 2002,12(5):701?745. [doi: 10.1093/logcom/12.5.701]
    [15] Moszkowski B. An automata-theoretic completeness proof for interval temporal logic. In: Proc. of the 27th Int’l Colloquium on Automata, Languages and Programming. LNCS 1853, Springer-Verlag, 2000. 223?234. [doi: 10.1007/3-540-45022-X_19]
    [16] Duan ZH, Tian C, Zhang L. A decision procedure for propositional projection temporal logic with infinite models. Acta Information, 2008,45(1):43?78. [doi: 10.1007/s00236-007-0062-z]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

舒新峰,段振华.有穷时间投影时序逻辑的完备公理系统.软件学报,2011,22(3):366-380

Copy
Share
Article Metrics
  • Abstract:4989
  • PDF: 7092
  • HTML: 0
  • Cited by: 0
History
  • Received:April 06,2010
  • Revised:June 09,2010
You are the first2032279Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063