The Tail-Recursive Fragment of Timed Recursive CTL

Florian Bruse, Martin Lange, Étienne LozesTIME 2022 · OpenReview

TL;DR

This paper introduces a "tail-recursive" fragment of Timed Recursive CTL (TRCTL), a powerful logic for specifying real-time systems. By imposing a syntactic restriction on how recursion is used, they reduce the model-checking complexity from 2-EXPTIME to EXPSPACE, making verification more feasible while retaining significant expressive power.

What Problem Does This Paper Address?

Specifying and verifying complex real-time systems, like those in embedded systems, is a significant challenge. Timed Automata (TA) are a common model for these systems, and temporal logics are used to express desired behaviors. While standard temporal logics like CTL are decidable in polynomial time, they lack expressiveness for certain complex properties. Extensions like Timed CTL (TCTL) add real-time capabilities, and Recursive CTL (RecCTL) adds recursion for higher expressiveness. Merging these led to Timed Recursive CTL (TRCTL), which is very expressive but has a high model-checking complexity of 2-EXPTIME-complete. This paper aims to find a fragment of TRCTL that is still highly expressive but has a lower, more manageable model-checking complexity.

Methods

The core idea is to introduce a syntactic restriction called "tail-recursiveness" to TRCTL formulas. In functional programming, tail recursion means the recursive call is the very last operation in a function, allowing for efficient execution without growing the call stack. Applied to TRCTL, this restriction limits how recursive formulas can be structured. The authors define this restriction formally using a derivation system.

To establish the upper bound for the model-checking complexity of this tail-recursive fragment (trTRCTL), they leverage existing results for untimed logics. They use a standard "untiming" construction via region graphs to translate the problem from timed systems (TA) to untimed systems (LTS). This reduction, combined with the known complexity of tail-recursive fragments of higher-order modal logics (which is PSPACE-complete), leads to an EXPSPACE-complete upper bound for trTRCTL.

For the lower bound, they employ a reduction from the "exponential corridor tiling problem" (ExpTiling), which is known to be EXPSPACE-complete. They construct a timed automaton and a trTRCTL formula that encodes the tiling problem, demonstrating that trTRCTL is at least EXPSPACE-hard.

Datasets

Not discussed in the paper. The paper focuses on theoretical aspects of a logic and its model-checking complexity, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Tail Recursion as a Complexity Reducer: The paper demonstrates that the concept of tail recursion, well-known in programming for efficiency, can significantly reduce the model-checking complexity of temporal logics with recursion, even in the real-time setting.
  • Bridging the Gap: By introducing trTRCTL, the authors provide a logic that sits between the highly expressive but computationally expensive TRCTL and simpler logics like TCTL. This offers a practical sweet spot for verifying complex real-time properties.
  • Real-Time vs. Untimed Complexity: The paper highlights that adding real-time aspects to logics with recursion doesn't simply add a fixed exponential factor. The interaction between time and recursion is nuanced, and the tail-recursive restriction effectively manages this complexity.
  • The Power of Syntactic Restrictions: This work underscores how carefully chosen syntactic restrictions can lead to significant improvements in decidability and complexity without sacrificing too much expressive power.

Key Results

  • Upper Bound: The model-checking problem for the tail-recursive fragment of TRCTL (trTRCTL) over timed automata is decidable in EXPSPACE.
  • Lower Bound: The model-checking problem for trTRCTL is EXPSPACE-hard.
  • Combined Complexity: The model-checking problem for trTRCTL is EXPSPACE-complete.
  • Comparison: This is a significant reduction from the 2-EXPTIME-complete complexity of full TRCTL.

Limitations and Future Work

  • Data Complexity: The authors conjecture that the EXPSPACE hardness result might already hold for the "data complexity" (i.e., when the size of the tiling system is fixed and only the number $n$ varies), although the presented reduction relies on binary encoding of $n$ for polynomial time construction.
  • Practical Applications: The paper suggests that further research should focus on practical applications of trTRCTL, as the tail-recursive restriction might enable techniques like local model checking.
  • Expressiveness Enhancement: Exploring ways to make clock values more visible to the logic, perhaps through "diagonal constraints," is suggested as a direction for adding more expressive power.
  • Untimed vs. Timed: While the paper shows that tail recursion reduces complexity in the timed setting, it also notes that the number of clocks has little impact beyond the first one, which is a notable difference from TCTL.

Summary updated

Abstract

Timed Recursive CTL (TRCTL) was recently proposed as a merger of two extensions of the well-known branching-time logic CTL: Timed CTL on one hand is interpreted over real-time systems like timed automata, and Recursive CTL (RecCTL) on the other hand obtains high expressiveness through the introduction of a recursion operator. Model checking for the resulting logic is known to be 2-EXPTIME-complete. The aim of this paper is to investigate the possibility to obtain a fragment of lower complexity without losing too much expressive power. It is obtained by a syntactic property called "tail-recursiveness" that restricts the way that recursive formulas can be built. This restriction is known to decrease the complexity of model checking by half an exponential in the untimed setting. We show that this also works in the real-time world: model checking for the tail-recursive fragment of TRCTL is EXPSPACE-complete. The upper bound is obtained by a standard untiming construction via region graphs, and rests on the known complexity of tail-recursive fragments of higher-order modal logics. The lower bound is established by a reduction from a suitable tiling problem.
BibTeX
@inproceedings{bruse2022tail,
  author = {Florian Bruse and Martin Lange and Étienne Lozes},
  title = {{The Tail-Recursive Fragment of Timed Recursive CTL}},
  booktitle = {TIME},
  year = {2022},
  url = {https://openreview.net/forum?id=D5FGDT7nW0},
}
Figure