Temporal Logic — LTL, CTL and Model Checking Properties

In this tutorial, you'll learn about Temporal Logic. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Temporal logic extends classical logic with operators that describe how truth values change over time, making it the standard language for specifying system behaviors in Model Checking.

Learning Path

flowchart LR
  A["First-Order Logic"] --> B["Temporal Logic
LTL, CTL & Properties"]
  B --> C["Model Checking"]
  B --> D["Bounded Model Checking"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Propositional logic. Basic understanding of state machines and transition systems.

What Is Temporal Logic?

Temporal logic adds time-based operators to propositional logic. Instead of saying "door is open," you can say "door will eventually open" or "door is always open until someone closes it."

Linear Temporal Logic (LTL) reasons about a single infinite execution path. Key operators: G (globally/always), F (finally/eventually), X (next), U (until).

Computation Tree Logic (CTL) reasons about branching time — all possible execution paths. Each operator is paired with a path quantifier: A (all paths) or E (exists a path).

Step-by-Step: LTL Formulas

Step 1: Define Atomic Propositions

For a traffic light: red, green, yellow.

Step 2: Write Safety Properties

Safety means "something bad never happens."

G ¬(red ∧ green)    -- Red and green are never both true at the same time

Step 3: Write Liveness Properties

Liveness means "something good eventually happens."

G (request → F grant)   -- Every request is eventually granted

Step 4: Verify with Python

class TLModelChecker:
    def __init__(self, trace):
        self.trace = trace  # list of states, each state is a dict of propositions

    def check_globally(self, prop, trace=None):
        if trace is None:
            trace = self.trace
        return all(prop(s) for s in trace)

    def check_eventually(self, prop, trace=None):
        if trace is None:
            trace = self.trace
        return any(prop(s) for s in trace)

    def check_until(self, prop_p, prop_q, trace=None):
        if trace is None:
            trace = self.trace
        for i, s in enumerate(trace):
            if prop_q(s):
                return all(prop_p(trace[j]) for j in range(i))
            if not prop_p(s):
                return False
        return False

trace = [
    {"request": True, "grant": False},
    {"request": True, "grant": False},
    {"request": False, "grant": True},
    {"request": False, "grant": False},
]
mc = TLModelChecker(trace)
result = mc.check_until(
    lambda s: True,
    lambda s: s["grant"]
)
print(f"Request leads to grant (U): {result}")

Expected output:

Request leads to grant (U): True

Step-by-Step: CTL Formulas

CTL prefixes each temporal operator with A (all paths) or E (some path).

AG (red → AX green)   -- Along all paths, red is always followed by green in the next state
EF (done ∧ ready)     -- There exists a path where done and ready are both true

class CTLChecker:
    def __init__(self, states, transitions):
        self.states = states
        self.transitions = transitions  # dict: state -> list of successors

    def check_EF(self, prop):
        visited = set()
        stack = list(self.states.keys())
        while stack:
            s = stack.pop()
            if s in visited:
                continue
            visited.add(s)
            if prop(self.states[s]):
                return True
            stack.extend(self.transitions.get(s, []))
        return False

states = {"s1": {"red": True}, "s2": {"green": True}, "s3": {"done": True}}
transitions = {"s1": ["s2"], "s2": ["s3"], "s3": []}
ctlc = CTLChecker(states, transitions)
found = ctlc.check_EF(lambda s: s.get("done", False))
print(f"Exists path to done state: {found}")

Expected output:

Exists path to done state: True

Common Errors

1. Confusing LTL and CTL Expressiveness

Some properties are expressible only in LTL or only in CTL. For example, fairness constraints are easier in LTL.

2. Missing Fairness Assumptions

Without fairness, a model checker may report spurious counterexamples where a Process is scheduled infinitely often but never makes progress.

3. Wrong Nesting of Operators

G F p (infinitely often p) is very different from F G p (eventually always p). The first is recurring, the second is stable.

4. Forgetting the Initial State

Properties must hold from the initial state. A system may be correct from some states but not from the intended starting point.

5. Bounded Traces for LTL

LTL operates on infinite traces. Checking on finite prefixes requires assuming something about the suffix (e.g., weak or strong fairness).

Practice Questions

Q1: What does G F p mean?

Globally eventually p — p holds infinitely often along the trace.

Q2: Express mutual exclusion in LTL.

G ¬(critical1 ∧ critical2).

Q3: What is the difference between AG EF p and AG AF p?

AG EF p: from any state, there exists some path reaching p. AG AF p: from any state, all paths eventually reach p infinitely often.

Q4: Why is fairness needed in Model Checking?

Without fairness, a scheduler could starve a Process and the model checker would report a counterexample that is unrealistic.

Q5: Convert G (p → F q) to CTL if possible.

This exact property is not expressible in CTL. The closest is AG (p → AF q).

Challenge

Model a simple mutual exclusion protocol with two processes. Each Process has states: idle, waiting, critical. Write LTL formulas for mutual safety and individual liveness. Verify with a manual trace enumeration.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.