Synthesising Classic and Interval Temporal Logic

Linear-Time Temporal Logic (LTL) is one of the most influential logics for the specification and verification of reactive systems. An important selling point of LTL is its striking simplicity, which might be a reason why none of the many extensions suggested to LTL have gained the same influence. Interval based temporal logics like Interval Temporal Logic (ITL) are a more recent branch of temporal logics with their own niche of interesting applications. On first glance, interval based temporal logics very little resemble LTL and the spread of these logics beyond their niche is hampered by a seeming structural incompatibility with LTL. When competing for being applied on a larger scale, interval based temporal logics would fight a losing battle against a more established competitor with better complexity and mature tools. In this paper, we suggest to extend ITL to Pop Logic (PL) by introducing a simple pop operator that revokes the binding of the chop operation-very much like the popping operation in a stack-and show that LTL can be viewed as a syntactic subset of PL. This is a surprising twist: by strengthening the comparably exotic logic ITL slightly and by using the new pop and the old chop operator as primitive constructs, we obtain a logic for which LTL is a de-facto syntactic fragment. The power of this extension is that it can, by subsuming both interval and classic temporal logics, synthesise both concepts to a common framework. The charm of this extension is that PL does not sacrifice the simplicity that makes its sub-logics attractive.

Authors

• Sven Schewe
• Cong Tian

Keywords

• Semantics
• Syntactics
• Complexity theory
• Cognition
• Radiation detectors
• Indexes
• Grammar
• Temporal Logic
• Classical Logic
• Interval Temporal Logic
• Linear Time
• Scoping
• Decision Problem
• Directed Acyclic Graph
• Binary String
• Infinite Model
• Set Of Propositions
• Word Problems
• Linear Logic
• Temporal Operators
• Top Element