Real-Time Higher-Order Recursion Schemes

Eric Alsmann, Florian BruseTIME 2024 · DOI

TL;DR

This paper introduces "timed Higher-Order Recursion Schemes" (timed HORS), a new formalism for modeling real-time systems with complex recursive structures. The authors show that checking these timed HORS against timed automata significantly increases the complexity of model-checking, pushing it from k-EXPTIME to (k+1)-EXPTIME for order-k schemes, while also establishing a 2-EXPTIME hardness result for the order-1 case.

What Problem Does This Paper Address?

Verifying complex software systems often involves modeling their behavior. Higher-Order Recursion Schemes (HORS) are a powerful tool for describing the infinite trees generated by functional programs. Model-checking these HORS against parity automata is known to be computationally challenging, with complexity tied to the "order" of the recursion scheme.

However, many real-world systems, like schedulers or control systems, operate with real time – time that flows continuously, not just in discrete steps. Timed Automata (TA) are a standard model for such systems. The challenge this paper addresses is how to combine the expressiveness of HORS for modeling complex program structures with the need to reason about continuous time. The authors introduce "timed HORS" and investigate the complexity of model-checking them against a combination of a timed automaton and a parity automaton.

Methods

The core of the paper involves two main contributions:

  1. Introducing Timed HORS: The authors extend the standard definition of HORS by annotating tree constructors with time intervals. This allows the generated trees to implicitly encode temporal behavior.
  2. Model-Checking Timed HORS: They define a model-checking problem for timed HORS against a pair of a timed automaton (TA) and a timed alternating parity tree automaton (APT). The acceptance game for this problem synchronizes the TA's continuous time evolution with the APT's discrete state transitions, mediated by the timed HORS.
  3. Complexity Analysis:
    • Upper Bound: They show that model-checking a timed HORS of order k can be done in (k+1)-EXPTIME. This is achieved by reducing the problem to the model-checking of untimed HORS. The reduction involves constructing an untimed HORS and an APT that simulate the timed behavior and the region abstraction of the TA.
  4. Lower Bound: They establish a 2-EXPTIME hardness result for order-1 timed HORS. This is done by encoding the word problem of deterministic 2-EXPTIME Turing machines into timed HORS, using a clever construction involving timed automata and APTs that simulate the computation of the Turing machine.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Discrete and Continuous Time Verification: The paper successfully bridges the gap between formalisms for verifying discrete, recursive structures (HORS) and those for continuous-time systems (TA).
  • The Cost of Real Time: Adding dense linear time to HORS increases the model-checking complexity by exactly one exponential. This is a significant finding, showing that real-time aspects, while powerful, come with a predictable computational cost.
  • Region Abstraction for HORS: The paper leverages the well-established region abstraction for timed automata to create a finite representation that can be integrated into the model-checking process for timed HORS.
  • Encoding Complex Computations: The hardness proof demonstrates a sophisticated technique for encoding the behavior of powerful computational models (2-EXPTIME Turing machines) into timed HORS, highlighting the expressiveness of the new formalism.

Key Results

  • Upper Bound: Model-checking order-k timed HORS is in (k+1)-EXPTIME.
  • Lower Bound: Model-checking order-1 timed HORS is 2-EXPTIME-hard.
  • The paper introduces the formalisms of timed HORS and timed APTs, and defines their semantics via an acceptance game that synchronizes timed automata and parity tree automata.

Limitations and Future Work

  • Hardness for Higher Orders: While the upper bound holds for all orders k, the lower bound is only proven for k=1. The authors conjecture that the 2-EXPTIME hardness extends to all orders, suggesting that further work is needed to prove this.
  • Expressiveness of Timed HORS: The authors suggest exploring extensions to timed HORS and their verification frameworks. This includes:
  • Allowing the APT to reset clocks in the companion TA, which could simplify modeling certain properties.
  • Inverting the semantics of the TA to control time flow, potentially enabling the modeling of safety properties like "no matter how long it takes, correctness is guaranteed."
    • Investigating restricted versions of timed HORS and APT-TA pairs that might capture "space" complexity rather than "time" complexity.

Summary updated

BibTeX
@inproceedings{alsmann2024real,
  author = {Eric Alsmann and Florian Bruse},
  title = {{Real-Time Higher-Order Recursion Schemes}},
  booktitle = {TIME},
  year = {2024},
  doi = {10.4230/lipics.time.2024.16},
}
Figure