4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Shaull
    Commented Feb 15, 2013 at 8:30

2 Answers 2

Reset to default
2
$\begingroup$

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

1.http://perseo.dif.um.es/~guido/publications.html

2.https://itl.dimi.uniud.it/

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).

cheers

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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