A complete axiom system for propositional interval temporal logic with infinite time

De Montfort University Open Research Archive

Show simple item record

dc.contributor.author Moszkowski, B. C. en
dc.date.accessioned 2012-08-20T14:51:53Z
dc.date.available 2012-08-20T14:51:53Z
dc.date.issued 2012-08
dc.identifier.citation Moszkowski, B. (2012) A complete axiom system for propositional interval temporal logic with infinite time. Logical Methods in Computer Science, 8 (3), Paper 10, pp. 1-56 en
dc.identifier.issn 1860-5974
dc.identifier.uri http://hdl.handle.net/2086/6876
dc.description.abstract Interval Temporal Logic (ITL) is an established temporal formalism for reasoning about time periods. For over 25 years, it has been applied in a number of ways and several ITL variants, axiom systems and tools have been investigated. We solve the longstanding open problem of finding a complete axiom system for basic quantifier-free propositional ITL (PITL) with infinite time for analysing nonterminating computational systems. Our completeness proof uses a reduction to completeness for PITL with finite time and conventional propositional linear-time temporal logic. Unlike completeness proofs of equally expressive logics with nonelementary computational complexity, our semantic approach does not use tableaux, subformula closures or explicit deductions involving encodings of omega automata and nontrivial techniques for complementing them. We believe that our result also provides evidence of the naturalness of interval-based reasoning. en
dc.language.iso en en
dc.publisher Tech Univ Braunschweigb en
dc.subject Interval Temporal Logic en
dc.subject axiom system en
dc.subject axiomatic completeness en
dc.subject omega-regular languages en
dc.subject omega-regular logics en
dc.subject compositionality en
dc.title A complete axiom system for propositional interval temporal logic with infinite time en
dc.type Article en
dc.identifier.doi 10.2168/LMCS-8(3:10)2012
dc.researchgroup Software Technology Research Laboratory (STRL) en


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record