Skip to main content

04 - Temporal Logic: LTL and CTL, how to express "eventually" and "always"

Write "eventually" and "always" in LTL and CTL and check them with your own program: counterexamples, safety and liveness, and why the two logics differ.

What do you think about this article?

04 - Temporal Logic: LTL and CTL, how to express "eventually" and "always"
Formal Methodsfedericocalo.dev

At a Glance

Write "eventually" and "always" in LTL and CTL and check them with your own program: counterexamples, safety and liveness, and why the two logics differ.

You have written a protocol, and you want to state, in a way a machine can check, that "every request eventually gets a response" and that "the system never deadlocks". Propositional logic is not enough: a formula such as request → response talks about a single instant, while "eventually" concerns every instant still to come. The answer is a temporal logic, and in practice there are two dialects. LTL (Linear Temporal Logic) describes a single execution, seen as an infinite sequence of states. CTL (Computation Tree Logic) describes the set of all the executions that are possible from a state, with two extra quantifiers: "for all paths" and "there exists a path". Neither is more powerful than the other, and the choice changes what you are able to write. In this article you implement both in under a hundred lines of Python and test them on a concrete protocol.

This is the fourth article in the Formal Methods series. You need the logical connectives from the second article and the idea of a state-based system from the third. The next step, model checking, will use these formulas as properties to verify on much larger models.

What you cannot say without time

A propositional formula is evaluated in an isolated state. For a reactive system, which keeps receiving stimuli and answering them, the interesting properties stretch across time. Three typical examples, with the request-response protocol as the running thread:

  • "After a request, a response arrives": request → response asks for the response at the same instant as the request, which is not what you mean.
  • "The resource stays free until somebody acquires it": you need an "until" that propositional logic does not have.
  • "The system never deadlocks": a "never" over all future instants, not over just one.

The three sentences have the same structure: a condition on one state, tied to states that come later. Temporal logics add operators for exactly this tie, and leave everything else unchanged. Pnueli proposed temporal logic for reasoning about programs in a 1977 paper, The temporal logic of programs; Clarke and Emerson introduced a branching-time language in a work on the synthesis of "synchronization skeletons" (Logics of Programs, LNCS 131). For both I checked title and references on the Crossref registry; I did not read the text.

The operators: X, F, G, U and their duals

On an infinite sequence of states s₀, s₁, s₂, …, each of which says which propositions are true, there are five basic temporal operators. They are always evaluated "starting from the current instant", and the present counts.

  • X φ (neXt): φ holds in the next state.
  • F φ (Finally): φ holds in some state from now on, the present one included.
  • G φ (Globally): φ holds in all states from now on.
  • φ U ψ (Until): ψ becomes true sooner or later, and until then φ is always true.
  • φ R ψ (Release): ψ stays true until φ "releases" it, or forever if φ never happens; it is the dual of Until.

Two facts in the list escape a quick reader. First, U is strong: it demands that ψ really happens, so "free until acquired" (free U acquired) is false if nobody ever acquires the resource. If you want to say "free until it is acquired, and possibly forever" you need the weak variant φ W ψ, defined as (φ U ψ) ∨ G φ. Second, F and G are not primitive: F φ is true U φ and G φ is ¬F ¬φ. In the code below you derive them this way, and X, U, R and the connectives are all you need.

LTL: evaluating a formula on an infinite trace

An infinite trace cannot be stored, but there is a family of traces that can be represented finitely: the eventually periodic ones, made of an initial stretch (stem) followed by a cycle (loop) that repeats forever. I call it a "lasso". Every finite-state system that violates an LTL property has a violation in lasso form, and this lets you use a lasso as a counterexample. The function ltl_eval takes the formula, the stem and the loop, unrolls the trace into n positions and computes, for each one, whether the formula holds. The successor relation is circular: after the last position it goes back to the first state of the loop (the nxt vector).

def neg(f): return ("not", f)

# ---------- LTL on a lasso: stem + loop (lists of sets of propositions) ----------
def ltl_eval(f, stem, loop):
    word = list(stem) + list(loop)
    n = len(word)
    nxt = [i + 1 if i + 1 < n else len(stem) for i in range(n)]
    def val(g):
        op = g[0]
        if op == "ap":  return [g[1] in word[i] for i in range(n)]
        if op == "not": return [not x for x in val(g[1])]
        if op == "and": return [x and y for x, y in zip(val(g[1]), val(g[2]))]
        if op == "or":  return [x or y for x, y in zip(val(g[1]), val(g[2]))]
        if op == "imp": return [(not x) or y for x, y in zip(val(g[1]), val(g[2]))]
        if op == "X":
            v = val(g[1]); return [v[nxt[i]] for i in range(n)]
        if op == "U":                       # least fixed point
            a, b = val(g[1]), val(g[2]); z = list(b)
            while True:
                nz = [z[i] or (a[i] and z[nxt[i]]) for i in range(n)]
                if nz == z: return z
                z = nz
        if op == "R":                       # greatest fixed point: b ∧ (a ∨ X Z)
            a, b = val(g[1]), val(g[2]); z = [True] * n
            while True:
                nz = [b[i] and (a[i] or z[nxt[i]]) for i in range(n)]
                if nz == z: return z
                z = nz
        raise ValueError(op)
    return val(f)[0]

def F(f): return ("U", ("or", f, ("not", f)), f)
def G(f): return ("not", F(("not", f)))

The lines that matter are those for U and R. Until is computed as a least fixed point: you start from z = b (ψ holds right away) and add every position where φ holds and the successor is already in z, until nothing changes. The least fixed point guarantees that ψ really arrives; had you started from "everything true" you would have computed a weak until, which also accepts the case where ψ never arrives. Release uses the greatest fixed point, for the opposite reason. The program never measures a time: it reasons on the shape of the lasso, and it always terminates because the z vectors grow (for U) or shrink (for R) at every round, and a vector of n Boolean values can change at most n times.

An example with a real trace, that of a request being served: two idle states, then request, wait, response, and finally idle forever. The property "every request gets a response" is written G(request → F response). In the program below you evaluate it, and then compare U with W on a trace where nothing ever happens: that is the case where the difference between the two versions becomes visible.

from ltl_ctl import *

# A real trace: idle, idle, request, wait, response, then idle forever.
trace = [{"idle"}, {"idle"}, {"request"}, {"wait"}, {"response"}]
loop = [{"idle"}]
response = G(("imp", ap("request"), F(ap("response"))))
print("G(request -> F response):", ltl_eval(response, trace, loop))

# "Do not write before initialisation", on a trace where nothing ever happens.
nothing = ([], [set()])
print("¬write U init :", ltl_eval(U(neg(ap("write")), ap("init")), *nothing))
print("¬write W init :", ltl_eval(W(neg(ap("write")), ap("init")), *nothing))

# The formula ¬write U (init ∨ ¬init) holds even if write happens at once: it says nothing.
tautology = U(neg(ap("write")), ("or", ap("init"), neg(ap("init"))))
print("¬write U (init ∨ ¬init), with write at once:", ltl_eval(tautology, [{"write"}], [set()]))

# Release is the dual of until: a R b is equivalent to ¬(¬a U ¬b). Check on every lasso
# of up to 4 states of a structure that contains every combination of p and q.
labels = {"pq": {"p", "q"}, "p": {"p"}, "q": {"q"}, "-": set()}
complete = kripke(labels, [(a, b) for a in labels for b in labels])
dual = lambda a, b: ("not", U(("not", a), ("not", b)))
cases = mismatches = 0
for s0 in labels:
    for stem, lp in lassos(complete, s0, 4):
        lab = lambda xs: [complete["L"][s] for s in xs]
        cases += 1
        mismatches += ltl_eval(("R", ap("p"), ap("q")), lab(stem), lab(lp)) != \
                      ltl_eval(dual(ap("p"), ap("q")), lab(stem), lab(lp))
print(f"R against its dual on {cases} lassos: {mismatches} mismatches")

# Output:
# G(request -> F response): True
# ¬write U init : False
# ¬write W init : True
# ¬write U (init ∨ ¬init), with write at once: True
# R against its dual on 880 lassos: 0 mismatches

Read the output in this order. The first line confirms the response property on the trace. The second and third show that ¬write U init is false when initialisation never arrives, while ¬write W init is true: nobody wrote before initialising, and nobody initialised. If you wanted to force initialisation to happen, you need the strong form; if you only wanted to forbid premature writing, you need the weak one. The fourth line exposes a formula that circulates in lecture notes: ¬Y U (X ∨ ¬X) is presented as "Y does not happen before X", but its second argument is a tautology, so it is true as soon as the trace starts, even if Y happens immediately. The last line is a check of the program itself: Release and its dual definition ¬(¬a U ¬b) give the same verdict on all 880 lassos of up to four states of a structure that contains every combination of two propositions.

CTL: checking all the paths of a Kripke structure

LTL looks at one path at a time. To talk about the choices the system can make, you need the whole model: a Kripke structure, that is a directed graph whose nodes are states, labelled with the propositions that are true in each. By convention every state has at least one successor, because paths must be infinite: a terminal state is represented with a self-loop. The code rejects a structure that violates this, with an assert.

In CTL every temporal operator must be preceded by a path quantifier: AX, AF, AG ("on all paths") and EX, EF, EG ("on at least one path"), plus the until E[φ U ψ]. The function sat returns the set of states where a formula holds, and computes everything with three primitive operators: EX, EG and EU. The others follow by duality: EF φ = E[true U φ], AF φ = ¬EG ¬φ, AG φ = ¬EF ¬φ, AX φ = ¬EX ¬φ.

"""CTL checking (fixed points over states) and LTL evaluation (on lasso paths)."""

# ---------- Kripke structure ----------
def kripke(labels, edges):
    succ = {s: [] for s in labels}
    for a, b in edges:
        succ[a].append(b)
    for s, nxt in succ.items():
        assert nxt, f"state without a successor: {s}"   # the relation must be total
    return {"L": {s: frozenset(v) for s, v in labels.items()}, "succ": succ}

# ---------- CTL: formulas as tuples ----------
def sat(M, f):
    S = set(M["L"])
    op = f[0]
    if op == "ap":   return {s for s in S if f[1] in M["L"][s]}
    if op == "true": return S
    if op == "not":  return S - sat(M, f[1])
    if op == "and":  return sat(M, f[1]) & sat(M, f[2])
    if op == "or":   return sat(M, f[1]) | sat(M, f[2])
    if op == "imp":  return (S - sat(M, f[1])) | sat(M, f[2])
    if op == "EX":
        a = sat(M, f[1])
        return {s for s in S if any(t in a for t in M["succ"][s])}
    if op == "EU":                       # least fixed point: g ∪ (f ∩ EX Z)
        a, b = sat(M, f[1]), sat(M, f[2])
        z = set(b)
        while True:
            nz = z | {s for s in a if any(t in z for t in M["succ"][s])}
            if nz == z: return z
            z = nz
    if op == "EG":                       # greatest fixed point: f ∩ EX Z
        a = sat(M, f[1])
        z = set(a)
        while True:
            nz = {s for s in z if any(t in z for t in M["succ"][s])}
            if nz == z: return z
            z = nz
    raise ValueError(op)

def EF(f): return ("EU", ("true",), f)
def AF(f): return ("not", ("EG", ("not", f)))
def AG(f): return ("not", EF(("not", f)))
def AX(f): return ("not", ("EX", ("not", f)))
def ap(p): return ("ap", p)

Here too the work is in the two fixed points. EU starts from the states where ψ holds and widens backwards, one step at a time, to the states where φ holds and that have a successor already collected: it is a backward reachability search. EG goes the other way round: it starts from all the states where φ holds and repeatedly discards those with no successor left, until what remains is the set of states from which you can stay in φ forever. This is why AF (liveness on all paths) boils down to the search for a cycle: it is false if and only if there is a path that stays forever in states where φ does not hold.

This version is deliberately naive: every round of the while loop scans the whole graph and the rounds can be as many as there are states, so in the worst case the cost grows with the square of the size. Implementations with work lists exist that reach the linear cost I mention further on; what matters here is that the idea (labelling states with fixed points) is readable.

Looking for counterexamples: all the lassos up to a length

To check an LTL formula on a whole structure you need to enumerate its paths. The function lassos walks depth-first the walks from an initial state, at most max_len states long, and every time an edge returns to an already visited state it records a lasso. A_ltl sorts them from the shortest, evaluates them with ltl_eval and returns the first one that falsifies the formula, or None. Here is a limit you must keep in mind: a lasso that is found is a true counterexample, but the absence of violations up to max_len is not a proof. A serious verifier does not enumerate paths: it builds the product between the structure and an automaton derived from the formula, which is the topic of the next article. Enumeration is enough for the five-state structures in this article, where every verdict can also be checked by hand.

def U(a, b): return ("U", a, b)
def W(a, b): return ("or", ("U", a, b), G(a))   # weak until

def lassos(M, s0, max_len):
    """All walks from s0 with at most max_len states, closed by a back edge."""
    out = []
    def walk(path):
        last = path[-1]
        for t in M["succ"][last]:
            if t in path:
                out.append((path[:path.index(t)], path[path.index(t):]))
        if len(path) < max_len:
            for t in M["succ"][last]:
                walk(path + [t])
    walk([s0])
    # duplicates are possible: remove them, keeping the order
    seen, uniq = set(), []
    for st, lp in out:
        k = (tuple(st), tuple(lp))
        if k not in seen: seen.add(k); uniq.append((st, lp))
    return uniq

def A_ltl(M, s0, f, max_len):
    """First violation found (a lasso) or None. The search is BOUNDED by max_len states."""
    for st, lp in sorted(lassos(M, s0, max_len), key=lambda c: len(c[0]) + len(c[1])):
        lab = lambda xs: [M["L"][s] for s in xs]
        if not ltl_eval(f, lab(st), lab(lp)):
            return st, lp
    return None

The sorted line is the reason why the results below show counterexamples of only two states: the shortest lasso is also the most readable, and a short counterexample is one an engineer can follow step by step. Without the sorting, for G ¬error the first lasso the depth-first enumeration meets has six states (idle, requesting, processing, done, idle, faulted) instead of the two in the output: the violation is the same, but the fault is buried in a whole round of the protocol. I checked this by removing the call to sorted.

A protocol that can fail, verified both ways

The model is a client-server protocol with five states. From idle the client can ask for a service (requesting, then processing, then done, then idle again) or the system can fail (faulted) and restart from idle. Each state has a single label: ready, pending, working, success, error. The program checks five CTL formulas on the whole structure and four LTL formulas on the lassos that start from idle, returning for each violation the shortest lasso.

from ltl_ctl import *

# Client-server protocol: from idle the client can ask for a service, or the system can fail.
K = kripke(
    {"idle": {"ready"}, "requesting": {"pending"}, "processing": {"working"},
     "done": {"success"}, "faulted": {"error"}},
    [("idle", "requesting"), ("idle", "faulted"), ("requesting", "processing"),
     ("processing", "done"), ("done", "idle"), ("faulted", "idle")])

print("CTL, states where the formula holds:")
for name, f in [("AG ¬error", AG(neg(ap("error")))),
                ("EF success", EF(ap("success"))),
                ("AF success", AF(ap("success"))),
                ("AG EF ready", AG(EF(ap("ready")))),
                ("AG(pending -> AX working)", AG(("imp", ap("pending"), AX(ap("working")))))]:
    print(f"  {name:<26}", sorted(sat(K, f)))

print("LTL from idle, lassos up to 7 states, shortest violation:")
for name, f in [("G ¬error", G(neg(ap("error")))),
                ("F success", F(ap("success"))),
                ("G(pending -> F working)", G(("imp", ap("pending"), F(ap("working"))))),
                ("G F ready", G(F(ap("ready"))))]:
    v = A_ltl(K, "idle", f, 7)
    print(f"  {name:<26}", "no violation" if v is None else f"stem={v[0]} loop={v[1]}")

# Output:
# CTL, states where the formula holds:
#   AG ¬error                  []
#   EF success                 ['done', 'faulted', 'idle', 'processing', 'requesting']
#   AF success                 ['done', 'processing', 'requesting']
#   AG EF ready                ['done', 'faulted', 'idle', 'processing', 'requesting']
#   AG(pending -> AX working)  ['done', 'faulted', 'idle', 'processing', 'requesting']
# LTL from idle, lassos up to 7 states, shortest violation:
#   G ¬error                   stem=[] loop=['idle', 'faulted']
#   F success                  stem=[] loop=['idle', 'faulted']
#   G(pending -> F working)    no violation
#   G F ready                  no violation

Reading. AG ¬error holds in no state, because faulted can be reached from every state. EF success holds everywhere, so the service is always reachable. AF success holds only in requesting, processing and done: from the idle and faulted states there is a path that alternates faults and restarts without ever completing a request. This is the concrete difference between EF ("it can") and AF ("it must"). AG EF ready holds everywhere: from any point the system can return to the ready state, a "recoverability" property that you cannot write in LTL, as you will see shortly. On the LTL side the counterexamples are two very short lassos, idle, faulted repeated: for G ¬error the finite prefix idle, faulted is enough to show the fault, while for F success no finite prefix is enough, because some extension could always still reach success, and the infinite cycle is needed to show that it never arrives.

Safety and liveness: what shape a counterexample has

That contrast between the two violations is the most useful distinction of the chapter. A safety property says that "something bad never happens": if it is violated, the violation shows in a finite prefix of the trace, and the model checker hands it to you as a sequence of states. A liveness property says that "something good eventually happens": no finite prefix violates it, because a lucky extension could always satisfy it, and the counterexample is an infinite cycle in which the good thing never arrives. Almost all the specifications you will write are combinations of a few patterns, and it pays to recognise them.

  • Absence: G ¬bad, for example G ¬(crit₁ ∧ crit₂) for mutual exclusion. It is a safety property.
  • Reachability: F good. It is a liveness property.
  • Response: G(request → F response). It is a liveness property.
  • Precedence: ¬write W init, "no writing before initialisation", in the weak form. It is a safety property.
  • Fairness: G F enabled → G F executed, "if an action is enabled infinitely often, it is executed infinitely often". It serves to rule out pathological paths in which the scheduler ignores a process forever.

The patterns change the verifier's work and the way you read the answer. If a safety property fails, it is enough to read the prefix and understand which step was one too many. If a liveness property fails you have to inspect a cycle, and often the cause is the absence of a fairness assumption: the scheduler never gave anyone a turn. This is why, when a response property fails with a cycle in which one process waits forever while the others run, the first question to ask is whether the model should assume fairness or not.

LTL and CTL are not comparable

The obvious question is: which of the two logics is more expressive? Neither, and you can see it on two small structures. The first experiment concerns FG p ("from some point on, p always holds"). The structure has three states: s0 (with p) has a self-loop and an edge to s1 (without p), which leads to s2 (with p), which has a self-loop. Every path either stays in s0 forever, or goes through s1 and ends in s2: in both cases p eventually holds forever, so A FG p is true. Yet the "obvious" translation into CTL, AF AG p, is false in s0: AG p holds neither in s0 (it can exit to s1) nor in s1, and the path that stays in s0 never reaches s2.

The second experiment goes the opposite way. The structures M1 and M2 are almost the same: in M1 state a (without p) has a self-loop and an edge to b (with p, self-loop). M2 adds an edge from a to a dead end c, without p and with a self-loop, from which p is no longer reachable. The label sequences that can be read are the same: the program enumerates them up to length 10 and finds the same ten words. An LTL formula is true or false depending only on the set of traces, so it cannot tell M1 from M2. The CTL formula AG EF p, instead, holds in M1 and not in M2.

from ltl_ctl import *

# (a) "A FG p" holds, "AF AG p" does not.
Ma = kripke({"s0": {"p"}, "s1": set(), "s2": {"p"}},
            [("s0", "s0"), ("s0", "s1"), ("s1", "s2"), ("s2", "s2")])
print("A FG p, violations among lassos up to 6 states:", A_ltl(Ma, "s0", F(G(ap("p"))), 6))
print("AF AG p holds in s0:", "s0" in sat(Ma, AF(AG(ap("p")))))

# (b) two structures with the same traces, but M2 has a dead end.
M1 = kripke({"a": set(), "b": {"p"}}, [("a", "a"), ("a", "b"), ("b", "b")])
M2 = kripke({"a": set(), "b": {"p"}, "c": set()},
            [("a", "a"), ("a", "b"), ("a", "c"), ("c", "c"), ("b", "b")])

def words(M, s0, n):
    """All label sequences of length n starting from s0."""
    cur = {(s0,)}
    for _ in range(n - 1):
        cur = {w + (t,) for w in cur for t in M["succ"][w[-1]]}
    return {tuple(tuple(sorted(M["L"][s])) for s in w) for w in cur}

print("same words of length 10:", words(M1, "a", 10) == words(M2, "a", 10),
      f"({len(words(M1, 'a', 10))} words)")
print("CTL, AG EF p from a:  M1 =", "a" in sat(M1, AG(EF(ap("p")))), " M2 =", "a" in sat(M2, AG(EF(ap("p")))))
for name, f in [("F p", F(ap("p"))), ("F G p", F(G(ap("p")))), ("G F p ∨ G ¬p", ("or", G(F(ap("p"))), G(neg(ap("p")))))]:
    print(f"LTL, {name:<13} holds on every lasso:  M1 =", A_ltl(M1, "a", f, 6) is None,
          " M2 =", A_ltl(M2, "a", f, 6) is None)

# Output:
# A FG p, violations among lassos up to 6 states: None
# AF AG p holds in s0: False
# same words of length 10: True (10 words)
# CTL, AG EF p from a:  M1 = True  M2 = False
# LTL, F p           holds on every lasso:  M1 = False  M2 = False
# LTL, F G p         holds on every lasso:  M1 = False  M2 = False
# LTL, G F p ∨ G ¬p  holds on every lasso:  M1 = True  M2 = True

The output confirms both experiments. In the first line the search for violations of A FG p among the lassos of up to six states finds none, and AF AG p turns out false in s0: the search is bounded, but in a three-state structure you can check it by eye too. In the last lines three LTL formulas give the same verdict on M1 and on M2, as expected, while AG EF p separates them. Be careful about what these experiments prove: they show that the chosen translation is not equivalent, and that in one case the separation is unavoidable for any LTL formula, but they do not prove by themselves that no CTL formula expresses FG p. That inexpressibility result is established by Emerson and Halpern in the paper "Sometimes" and "not never" revisited, which compares the expressive power of the languages and introduces CTL*, the logic in which a path quantifier can precede an arbitrary LTL formula. I read the abstract, not the full text.

What verification costs: linear for CTL, not for LTL

Clarke, Emerson and Sistla show in 1986 a CTL verification algorithm whose complexity is linear both in the size of the specification and in the global state graph of the system, and extend it to handle fairness: it is the same labelling scheme you have just seen, made efficient. For LTL the picture is different. Sistla and Clarke prove that the truth of a formula in a finite structure is PSPACE-complete for the logics with F and X or with U, while it is NP-complete for the logic with F alone. In other words, the formula is the part that makes LTL verification hard in the worst case, while the size of the model is the factor that makes costs explode in practice, as you will see in the next article. I read the abstracts of both.

The choice between the two logics, then, is not just a matter of speed. CTL expresses properties about the possibilities of the system (AG EF ready: "it can always restart") and is checked in linear time, but it cannot say "from some point on, always". LTL expresses properties about executions, fairness ones included, but ignores choices: for it M1 and M2 are the same system.

Common mistakes

  • Reading "eventually" as probability. F p does not say that p is probable: it says that on that path p occurs, somewhere. There is no probability measure in LTL or in CTL.
  • Swapping EX and AX. The first asks for one path with p in the next state, the second asks for p in the next state of all paths. On the protocol, EX error holds in idle while AX error does not.
  • Using F for "within N steps". LTL has no metric time: "p within three steps" is written p ∨ X p ∨ X X p ∨ X X X p. Time-bounded extensions exist, but they are other logics.
  • Forgetting that paths are infinite. A halting state has no successors, and the verifier rejects it: it must be modelled with a self-loop, and it becomes a path that eventually repeats the same state.
  • Using U where you need W. Remember that U forces the event to arrive: a precedence specification written with U quietly becomes a liveness property too.

These five mistakes have a single root: reading a formula with the meaning it would have in everyday language. The remedy is always the same, the one you applied in this article: write the formula, pick a small trace or structure in which the verdict is obvious, and have the program compute it. If the verdict surprises you, the formula does not say what you thought.

Exercises

  1. In the protocol, add an edge from faulted to itself, that is a fault that is never repaired. Before running, predict which of the five CTL formulas change verdict, then rerun d1_protocol.py and check.
  2. Write in CTL the property "from every state success can be reached" and check that on the protocol it holds in all five states. Then write the same idea in LTL and explain why the LTL formula that comes to mind is not equivalent.
  3. Build a traffic light with four states (red, yellow, green, broken) and check AG ¬(red ∧ green), EF broken and AF green. Which of the three fails, and with which lasso?
  4. Classify as safety or liveness: AG ¬error, AF success, G F fairness. Then check with the program that a finite prefix is enough for the safety ones.

The exercises have no published solution because the program is the verifier: if the verdict agrees with your prediction, you have understood the formula; if it does not, the doubt is already pinpointed. For the third exercise remember that the structure must have a total transition relation, so broken too must have a successor.

Frequently asked questions

What is the difference between LTL and CTL?

LTL describes the properties of a single execution, seen as an infinite sequence of states, and a system satisfies them if all its executions satisfy them. CTL describes the properties of the tree of all possible executions, with the quantifiers "for all paths" and "there exists a path". Neither contains the other: AG EF p is CTL only and A FG p has no faithful translation into CTL.

What is the difference between safety and liveness?

A safety violation is shown by a finite prefix of the trace ("the fault happened"). A liveness violation requires an infinite cycle in which the awaited event never arrives, because no finite prefix rules out that it arrives later.

Why does F p in LTL not mean "probably p"?

Because the temporal logics of this article have no notion of probability: F p is true on a path if p holds in at least one of its states. A probabilistic property requires different logics, which I do not cover here.

What you can do now

You can write in LTL and in CTL the properties that matter for a reactive system (absence, reachability, response, precedence, fairness), telling the strong form of until from the weak one. You can evaluate them with a program of your own, and for every violation you can say whether the counterexample is a finite prefix or a cycle. You can choose between the two logics according to what you need to express, and you have seen with two three-state structures why the choice is not a detail. In the next article the same formulas become properties to verify on models that grow exponentially, and the problem moves from the meaning of the formulas to the cost of computing them.

The last article in the series, Petri Nets: structure, markings, reachability, liveness and safety, closes the path with a model that is an alternative to the state machine.

Sources

The scripts ltl_ctl.py, d1_protocol.py, d2_until.py and d3_incomparable.py were run with Python 3.14 on Linux, twice each, with the same output. No external model checker was run: the verifier in the article is the one shown, and its purpose is to explain, not to replace tools such as Spin.

Next part: model checking and the state space →

Commenti

Caricamento commenti...

Sign in to comment

New articles and tools on Telegram too

The Telegram channel flags the site's new articles and tools.

Did you like this article?

Explore other content on the blog or discover my projects