Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

I am trying to understand the relation between interval temporal logic and linear temporal logic. Do the two form of expressing temporal constraints have the same expressive power, or is one of the two more expressive?

I found a proof of the ability of translating Allen Interval temporal logic formulas into linear temporal logic formulas (http://fsl.cs.uiuc.edu/index.php/Allen_Linear_(Interval)_Temporal_Logic_-Translation_to_LTL_and_Monitor_Synthesis-), but I couldn't find much info for the other direction.

share|improve this question
In the paper you cite they tailor a special semantics to LTL such that it deals with intervals, thus enabling the translation. In the converse direction, you need to somehow define a semantics for ITL to deal with atomic propositions, discrete time, and infinite sequences. Do you have such a semantics in mind? – Shaull Feb 15 at 8:30

1 Answer

up vote 1 down vote

The paper mentions in the preliminaries that it encodes Allen Interval temporal logic into the FG-fragment of LTL (which only has the "globally" and "eventually" modalities). Full LTL is strictly more expressive (e.g., consider the formula a U b) and thus cannot be encoded in Allen Interval temporal logic.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.