Extended Computation Tree Logic

Roland Axelsson, Matthew Hague, Stephan Kreutzer, Martin Lange, Markus Latte

TL;DR

This paper introduces a powerful extension to Computation Tree Logic (CTL) by allowing its temporal operators to be constrained by formal languages, such as context-free languages. Surprisingly, even with this massive boost in expressive power—which allows for the specification of non-regular properties like unbounded buffer tracking—model checking on finite systems remains solvable in polynomial time.

What Problem Does This Paper Address?

In the world of formal program verification, Computation Tree Logic (CTL) is a fan favorite. It has an intuitive syntax and is computationally cheap: checking if a system satisfies a CTL formula (model checking) can be done in polynomial time.

However, CTL is weak. It can only express a subset of "regular" properties. If you want to verify a software system with an unbounded buffer—for example, ensuring a "consumer" process never removes an item from an empty buffer—standard CTL fails because it cannot count arbitrarily high.

Historically, computer scientists have turned to richer logics like CTL or the modal $\mu$-calculus. But these come with severe trade-offs: they are either notoriously hard to read, computationally expensive (PSPACE to EXPTIME), and crucially, they are still* restricted to regular properties. The authors tackle this gap by designing a logic that breaks the "regular property" barrier, maintains an intuitive syntax, and preserves efficient model checking.

Methods

The authors introduce a generic family of logics called CTL[$\mathfrak{A}$, $\mathfrak{B}$].

Instead of standard temporal operators like "Until" (eventually $X$ happens, and $Y$ holds until then) and "Release", this new logic parameterizes these operators with classes of formal automata ($\mathfrak{A}$ and $\mathfrak{B}$). For example, an "Until" property is only fulfilled if the sequence of events along the path forms a word accepted by the specified automaton.

The authors evaluate this logic across a hierarchy of automata:

  • DFA/NFA: Deterministic/Nondeterministic Finite Automata (Regular languages)
  • DVPA/VPA: Deterministic/Nondeterministic Visibly Pushdown Automata
  • DPDA/PDA: Deterministic/Nondeterministic Pushdown Automata (Context-free languages)

They use standard theoretical computer science techniques—reductions to reachability problems in pushdown systems (PDS), alternating Turing machines, and parity games—to establish strict mathematical bounds for the complexity of both model checking and satisfiability.

Datasets

Not discussed in the paper. This is a theoretical computer science paper focused on formal logic and computational complexity, so no empirical datasets or benchmarks were used.

Key Insights and Ideas

  • The Sweet Spot of Expressivity and Efficiency: The most striking insight is that you can upgrade CTL with Pushdown Automata (giving it the power of context-free languages) without destroying its model-checking efficiency. It stays in PTIME (Polynomial Time) for finite-state systems. This is a rare "free lunch" in complexity theory.
  • Separation of Concerns ($\mathfrak{A}$ vs. $\mathfrak{B}$): The authors cleverly separate the automata classes used for the "Until" operator ($\mathfrak{A}$) and the "Release" operator ($\mathfrak{B}$). Why? Because existential quantification (Until) plays nicely with non-determinism (PDA). However, universal quantification (Release) requires determinism (DPDA) to avoid exponential blowups. By mixing and matching, they optimize the logic's computational footprint.
  • A Strict Expressivity Hierarchy: The paper formally proves that adding richer languages strictly increases the logic's expressive power. They map out a clear hierarchy: CTL $\subset$ CTL[REG] $\subset$ CTL[VPL] $\subset$ CTL[DCFL]. This proves the logic can handle tasks standard temporal logics simply cannot.

Key Results

  • Model Checking is Fast: Checking finite state systems against CTL[PDA, DPDA] is P-complete. This is the standout practical result, making the logic highly viable for real-world verification tools.
  • Satisfiability is Hard: Checking if a formula is logically satisfiable (useful for program synthesis) gets hard fast.
  • CTL[DFA, NFA] is EXPTIME-complete.
  • Stepping up to Visibly Pushdown Languages (VPL) pushes it to 2EXPTIME or 3EXPTIME.
  • For general Pushdown Automata (PDA/DPDA), satisfiability becomes undecidable.
  • Infinite Systems: The authors also analyzed model checking against infinite-state systems (represented by visibly pushdown automata). Here, complexities jump significantly (ranging from EXPTIME-complete to undecidable), mapping out the exact boundaries of what is computationally feasible for software model checking.

Limitations and Future Work

Limitations: The satisfiability problem for the most expressive variants (using PDAs) is undecidable. This limits the logic's use in automated program synthesis, where satisfiability solvers are heavily relied upon. Additionally, the exact mathematical relationship between CTL[CFL] and a competing logic, $\Delta$PDL?[CFL], remains an open question.

Future Work: The authors suggest extending this parametric approach to richer base logics like CTL* or CTL+. They also propose exploring extensions using automata on infinite words ($\omega$-automata), which could be highly relevant for abstraction and refinement frameworks in infinite-system verification.

Summary updated

Abstract

We introduce a generic extension of the popular branching-time logic CTL which refines the temporal until and release operators with formal languages. For instance, a language may determine the moments along a path that an until property may be fulfilled. We consider several classes of languages leading to logics with different expressive power and complexity, whose importance is motivated by their use in model checking, synthesis, abstract interpretation, etc. We show that even with context-free languages on the until operator the logic still allows for polynomial time model-checking despite the significant increase in expressive power. This makes the logic a promising candidate for applications in verification. In addition, we analyse the complexity of satisfiability and compare the expressive power of these logics to CTL* and extensions of PDL.
BibTeX
@inproceedings{axelsson2010extended,
  author = {Roland Axelsson and Matthew Hague and Stephan Kreutzer and Martin Lange and Markus Latte},
  title = {{Extended Computation Tree Logic}},
  booktitle = {LPAR (Yogyakarta)},
  year = {2010},
  url = {https://openreview.net/forum?id=NeYwXRt5pv},
}

Loading related content...

Figure