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.
$\begingroup$
$\endgroup$
2
asked May 25, 2011 at 18:30
-
1$\begingroup$ Loads of notes on the interwebs deal with this issue. Have googled for "the difference between LTL and CTL"? $\endgroup$– Dave ClarkeCommented May 25, 2011 at 19:08
-
1$\begingroup$ Try writing down simple formulae and evaluating their semantics on Kripke structures. $\endgroup$– Vijay DCommented May 25, 2011 at 21:45
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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".
-
1$\begingroup$ see a discussion on LTL vs CTL by Vardi: "Branching vs. Linear Time: Final Showdown" $\endgroup$– GuyCommented Jun 20, 2011 at 8:03
-
$\begingroup$ thanks a bunch, that is exactly the kind of insight I was looking for! $\endgroup$ Commented Jun 21, 2011 at 22:45
-
$\begingroup$ I understand this is a very very old thread. But I have a question. In the example you gave, the system might always be in A1 states that means there is a path where it can reach a B state. But isn't it addressed with fairness? Or did CTL not have fairness constraints like LTL? $\endgroup$ Commented Oct 14, 2024 at 8:00
-
$\begingroup$ Your point is slightly out of the scope of the OP question. However, the fairness constraint is not inherent in the "usual" satisfiability of a CTL formula. As I mention, you can embedded a fairness constraint in a LTL formula (e.g., ◻◊B to ensure that a B will always finally be executed), but you cannot do it in CTL without changing the semantics. $\endgroup$ Commented Oct 15, 2024 at 14:53
$\begingroup$
$\endgroup$
6
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.
-
7$\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$ Commented May 25, 2011 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 DCommented May 25, 2011 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$– jkffCommented May 26, 2011 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$– RaphaelCommented May 26, 2011 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 DCommented May 26, 2011 at 10:34