Abstract
Rectangular hybrid automata represent a critical class of hybrid systems—those combining discrete control with continuous dynamics—for which model checking is theoretically decidable. However, a significant gap has persisted between theoretical decidability proofs and the practical performance of symbolic verification tools. While tools like HyTech utilize efficient symbolic operators, they lack termination guarantees for this class. This paper presents a symbolic Linear Temporal Logic (LTL) model-checking procedure, termed Observation Refinement ($A_{OR}$), which is mathematically guaranteed to terminate for initialized rectangular hybrid systems. By shifting the focus from bisimulation to trace equivalence and utilizing the guarded fragment of the $\mu$-calculus, the authors provide a robust decision procedure that bridges the gap between theory and implementation.
Introduction
Hybrid systems, which integrate discrete control logic with continuous physical processes, are essential for modeling safety-critical applications such as automated highways, medical devices, and industrial controllers. Within this domain, rectangular hybrid automata (RHA) are particularly significant because they are the most expressive class of hybrid systems for which the reachability problem remains decidable.
Despite this theoretical decidability, practical verification has faced a dichotomy. Theoretical proofs typically rely on complex reductions to timed automata, which are computationally expensive and rarely implemented. Conversely, practical symbolic model checkers like HyTech employ "Pre" operators to explore state spaces efficiently but often fail to terminate, even on systems known to be decidable. This paper addresses this discrepancy by introducing a symbolic procedure that is both implementable within existing frameworks and guaranteed to terminate.
The Problem: The Termination Gap
The primary challenge in verifying hybrid systems is the infinite nature of their state spaces. To manage this, model checkers use symbolic representations to group infinite sets of states. Traditional symbolic algorithms often attempt to find a "bisimulation"—a partition of the state space where all states in a group behave identically.
However, for rectangular hybrid automata, a finite bisimulation does not always exist. This causes standard partition-refinement algorithms to loop indefinitely. The authors identified that while bisimulation is a sufficient condition for model checking, it is not a necessary one for LTL properties.
Methodology: Observation Refinement
The authors propose the Observation Refinement ($A_{OR}$) algorithm. This symbolic procedure differs from standard methods in several key ways:
1. Trace Equivalence over Bisimulation
Instead of seeking bisimulation, $A_{OR}$ targets "trace equivalence." Two states are trace-equivalent if they produce the same sequences of observations over time. Because trace equivalence is a coarser relationship than bisimulation, it results in a finite number of equivalence classes for rectangular automata, even when bisimulation remains infinite. This shift is the "missing link" that ensures the algorithm stops.
2. Logical Translation to $G\mu$
To check LTL properties symbolically, the authors translate LTL formulas into a specific subset of the $\mu$-calculus known as the Guarded Fragment ($G\mu$). This translation allows the model-checking problem to be framed as the evaluation of a fixpoint expression using symbolic Pre (predecessor) and Post (successor) operators.
3. Integration with HyTech
Rather than building a new tool from the ground up, the $A_{OR}$ procedure was designed to utilize the existing symbolic primitives of the HyTech model checker. This demonstrates that the lack of termination in previous tools was not a limitation of the symbolic engine itself, but rather the strategy used to explore the state space.
Case Study: Assembly Line Scheduler
The algorithm's efficacy was evaluated using a formal model of an assembly line scheduler. The system consisted of two lines with varying processing speeds (1-2 m/s and 2-3 m/s) and specific cleanup requirements. The verification goal was a liveness property: ensuring that the scheduler could process an infinite stream of jobs without reaching a "shutdown" state.
Using the $A_{OR}$ procedure, the system successfully verified the property in 0.39 seconds of CPU time. This result confirmed that the symbolic approach is not only theoretically sound but also computationally efficient for practical engineering models.
Key Insights and Results
- Guaranteed Termination: The paper provides the first symbolic LTL model-checking algorithm proven to terminate on all initialized rectangular hybrid automata.
- Syntax Independence: A significant finding is that the termination of the algorithm depends on the structural properties of the hybrid system (the automata) rather than the complexity of the LTL formula being checked.
- Algorithmic Equivalence: The authors proved that their $\mu$-calculus-based approach is equivalent to the traditional product-automaton approach, making it a versatile foundation for future symbolic analysis.
Limitations and Future Directions
While the paper marks a major advancement, certain constraints remain:
- Initialization Requirement: The termination guarantee is strictly for "initialized" automata, where variables are reset or constrained when their dynamics change. Non-initialized rectangular systems remain undecidable.
- State Space Explosion: Although the algorithm terminates, the number of symbolic regions can grow exponentially with the number of continuous variables. Addressing this "dimensionality bottleneck" is a primary focus for future scaling.
- Zeno Behavior: The authors acknowledge the challenge of "divergent runs" (where time must progress to infinity). While they provide a construction to handle this, it increases the complexity of the model and requires careful implementation.
Conclusion
By aligning symbolic verification techniques with the coarser abstraction of trace equivalence, this research transforms theoretical decidability into a practical tool for hybrid system design. The $A_{OR}$ algorithm provides a reliable foundation for verifying complex, real-time control systems where safety and liveness are paramount.
Summary updated