Take the 2-minute tour ×
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.

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.

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

2 Answers

up vote 11 down vote accepted

To really understand the difference between LTL and CTL you have to study semantics of both language. The 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" —, the satisfiability is checked on the run with no possibility of switching to another run during the checking. On the other hand, the 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 properties (an important reachability property for circuit design) states that there is always a possibility that a state can be reached during the run, even if it is never reach actually (AG EF reset). The LTL can only states that the reset state is actually reached and not that it can be reached. In the same time, the LTL formula $\Diamond\Box s$ cannot be translate in 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). The 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. Indeed, consider the system that loop on A1, can goes from A1 to B and then will goes to A2 on the next move. Then the system will go in A2 state forever. Then "the system will finally stayed 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 reply to your question, but I would like to add some comment.

There is a lot of discussion on the best logic to express property for software verification... but the real debate is somewhere else. The LTL can express an 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 differents approaches, until now.

share|improve this answer
    
see a discussion on LTL vs CTL by Vardi: "Branching vs. Linear Time: Final Showdown" –  Guy Jun 20 '11 at 8:03
    
thanks a bunch, that is exactly the kind of insight I was looking for! –  Anonymous Coward Jun 21 '11 at 22:45
add comment

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.

share|improve this answer
5  
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. –  Dave Clarke May 25 '11 at 19:56
4  
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. –  Vijay D May 25 '11 at 21:47
    
@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). –  jkff May 26 '11 at 5:17
    
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"? –  Raphael May 26 '11 at 5:57
    
I cannot tell what the OP is familiar with. For example, is it clear to them what a model is in each case? –  Vijay D May 26 '11 at 10:34
show 1 more comment

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.