Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 (, but I couldn't find much info for the other direction.

share|cite|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 '13 at 8:30

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|cite|improve this answer

The question you ask is more complex than it seems. ITLs have been defined in different ways and fashions, and the answer depends on the particular definition and the particular semantics. To get an intuition, you have to decide first if points are to be considered special intervals or excluded by the semantics; the second choice is more common, and it makes more difficult the comparison. I suggest to check, first, the webpages



to get an idea of the last 10 years of research on this topic. Second, you can contact me to discuss more in particular your question (my address is on the link number 1).


share|cite|improve this answer

Your Answer


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.