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.
Introduction
In the domain of formal program verification, Computation Tree Logic (CTL) is a standard tool due to its intuitive syntax and efficient polynomial-time model checking. However, CTL is limited to expressing a subset of "regular" properties. It cannot verify systems requiring non-regular properties, such as those involving unbounded buffers—for instance, ensuring a consumer never removes an item from an empty buffer. Standard CTL fails here because it lacks the capacity to count arbitrarily high.
Historically, researchers have turned to more expressive logics like CTL* or the modal $\mu$-calculus. However, these alternatives are often computationally expensive (ranging from PSPACE to EXPTIME) and are still restricted to regular properties. This paper addresses this gap by proposing a logic that breaks the regular property barrier while maintaining efficient model checking for finite systems.
Methodology: The CTL[$\mathfrak{A}$, $\mathfrak{B}$] Framework
The authors introduce a generic family of logics, CTL[$\mathfrak{A}$, $\mathfrak{B}$], where standard temporal operators like "Until" and "Release" are parameterized by classes of formal automata ($\mathfrak{A}$ and $\mathfrak{B}$). In this framework, an "Until" property is satisfied only if the sequence of events along a path corresponds to a word accepted by the specified automaton.
The logic's performance and expressivity are evaluated across a hierarchy of automata classes:
- Finite Automata (DFA/NFA): Regular languages (REG).
- Visibly Pushdown Automata (DVPA/VPA): Visibly pushdown languages (VPL).
- Pushdown Automata (DPDA/PDA): Context-free languages (CFL/DCFL).
Theoretical bounds for model checking and satisfiability were derived using reductions to reachability problems in pushdown systems (PDS), alternating Turing machines, and parity games.
Expressivity and Complexity
A significant contribution of this work is identifying a "sweet spot" where expressivity is maximized without compromising efficiency. By extending CTL with Pushdown Automata, the logic gains the power of context-free languages while remaining in PTIME for model checking finite-state systems. This efficiency is achieved by separating the automata classes used for existential (Until) and universal (Release) operators, preventing the exponential blowups typically associated with non-determinism in universal contexts.
The research establishes a strict expressivity hierarchy: CTL $\subset$ CTL[REG] $\subset$ CTL[VPL] $\subset$ CTL[DCFL]. This demonstrates that the extended logic can specify properties that standard temporal logics cannot.
Key Results
- Efficient Model Checking: Checking finite-state systems against CTL[PDA, DPDA] is P-complete. This result suggests the logic is highly suitable for practical verification tools.
- Satisfiability Challenges: While model checking is efficient, satisfiability—crucial for program synthesis—is computationally demanding. CTL[DFA, NFA] is EXPTIME-complete, while VPL-based variants range from 2EXPTIME to 3EXPTIME. For general PDA/DPDA, the satisfiability problem is undecidable.
- Infinite-State Systems: When applied to infinite-state systems (e.g., those modeled by VPA), model checking complexity increases significantly, ranging from EXPTIME-complete to undecidable.
Conclusion
While the undecidability of satisfiability for the most expressive variants limits their application in automated synthesis, the polynomial-time model checking for finite systems represents a major advancement for verification. Future work includes extending this parametric approach to richer base logics like CTL* and exploring the use of $\omega$-automata for infinite-word properties, which would be highly relevant for abstraction and refinement frameworks.
Summary updated