11
$\begingroup$

I already read examples of formulas in CTL but not in LTL and vice-versa, but I'm having trouble gaining a mental grasp on LTL formulas and really what, at the heart, is the difference.

$\endgroup$
  • 1
    $\begingroup$ Loads of notes on the interwebs deal with this issue. Have googled for "the difference between LTL and CTL"? $\endgroup$ – Dave Clarke May 25 '11 at 19:08
  • 1
    $\begingroup$ Try writing down simple formulae and evaluating their semantics on Kripke structures. $\endgroup$ – Vijay D May 25 '11 at 21:45
21
$\begingroup$

To really understand the difference between LTL and CTL you have to study the semantics of both languages. LTL formulae denote properties that will be interpreted on each execution of a program. For each possible execution (a run), which can be see as a sequence of events or states on a line — and this is why it is named "linear time" — satisfiability is checked on the run with no possibility of switching to another run during the checking. On the other hand, CTL semantics checks a formula on all possible runs and will try either all possible runs (A operator) or only one run (E operator) when facing a branch.

In practice this means that some formulae of each language cannot be stated in the other language. For example, the reset property (an important reachability property for circuit design) states that there is always a possibility that a state can be reached during a run, even if it is never actually reached (AG EF reset). LTL can only state that the reset state is actually reached and not that it can be reached.

On the other hand, the LTL formula $\Diamond\Box s$ cannot be translated into CTL. This formula denotes the property of stability : in each execution of the program, s will finally be true until the end of the program (or forever if the program never stops). CTL can only provide a formula that is too strict (AF AG s) or too permissive (AF EG s). The second one is clearly wrong. It is not so straightforward for the first. But AF AG s is erroneous. Consider a system that loops on A1, can go from A1 to B and then will go to A2 on the next move. Then the system will stay in A2 state forever. Then "the system will finally stay in a A state" is a property of the type $\Diamond\Box s$. It is obvious that this property holds on the system. However, AF AG s cannot capture this property since the opposite is true : there is a run in which the system will always be in the state from which a run finally goes in a non A state.

I don't know if this answers to your question, but I would like to add some comments.

There is a lot of discussion of the best logic to express properties for software verification... but the real debate is somewhere else. LTL can express important properties for software system modelling (fairness) when the CTL must have a new semantics (a new satisfiability relation) to express them. But CTL algorithms are usually more efficient and can use BDD-based algorithms. So... there is no best solution. Only two different approaches, so far.

One of the commenters suggests Vardi's paper "Branching versus Linear Time: Final Showdown".

$\endgroup$
  • $\begingroup$ see a discussion on LTL vs CTL by Vardi: "Branching vs. Linear Time: Final Showdown" $\endgroup$ – Guy Jun 20 '11 at 8:03
  • $\begingroup$ thanks a bunch, that is exactly the kind of insight I was looking for! $\endgroup$ – Anonymous Coward Jun 21 '11 at 22:45
1
$\begingroup$

If given one object (e.g. trace in case of LTL), you consider only one future for every point in time, in CTL you have a plethora of them.

In particular, next gives a unique action in LTL but (potentially) a whole set in CTL.

$\endgroup$
  • 6
    $\begingroup$ But you typically apply the LTL formula to all runs of the system, rather than just one, thus closing the gap between the one/many future issue. It would be more precise to say that LTL deals with linear-time, whereas CTL deals with branching time. $\endgroup$ – Dave Clarke May 25 '11 at 19:56
  • 4
    $\begingroup$ Saying, in LTL you consider one future is like saying in CTL you consider one state. Satisfiability is defined this way. It's not about how many futures, but the structure of the future. In one it is a trace, in the other, a tree. $\endgroup$ – Vijay D May 25 '11 at 21:47
  • $\begingroup$ @Vijay - indeed, the structure matters. E.g. you can't just take an LTL formula, transform it like FGp -> AF AG p and get an equivalent CTL formula (these two formulae are not equivalent; moreover FGp is not expressible in CTL and AF AG p is not expressible in LTL). $\endgroup$ – jkff May 26 '11 at 5:17
  • $\begingroup$ I assumed the OP was familiar with the formal definition and asking for some kind of intuition, hence my try. Can this answer be salvaged by saying "one future per model"? $\endgroup$ – Raphael May 26 '11 at 5:57
  • $\begingroup$ I cannot tell what the OP is familiar with. For example, is it clear to them what a model is in each case? $\endgroup$ – Vijay D May 26 '11 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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