Model-checking real-time systems: revisiting the alternating automaton route
Patricia Bouyer, B Srivathsan, Vaishnavi Vishwanath · 2025
Read Model-checking real-time systems: revisiting the alternating automaton route by Patricia Bouyer, B Srivathsan, Vaishnavi Vishwanath (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-17576.txt.
Introduction
Patricia Bouyer, Srivathsan, and Vaishnavi Vishwanath wrote this paper in two thousand twenty-five. It revisits model-checking for real-time systems through alternating timed automata, machines that track clocks and can flip between states in a game-like way.
Timed logics such as Metric Temporal Logic can be turned into one-clock versions of these automata, and checking a formula comes down to checking if the automaton is empty. Past emptiness tests rest on region builds that suit theory more than code. The authors add a deactivation move that switches a clock off in plain sight, sharpen the logic swap, and build zone-based tests. They give a fast entailment check and show the general check is NP-hard.
Catalog record
| CREATOR | Patricia Bouyer, B Srivathsan, Vaishnavi Vishwanath |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 135 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-17576
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Model-checking real-time systems: revisiting the alternating automaton route Patricia Bouyer, B Srivathsan, Vaishnavi Vishwanath Abstract . Alternating timed automata (ATA) are an extension of timed automata where the effect of each transition is described by a positive boolean combination of (state-reset) pairs. Unlike classical timed automata, ATA are closed under complementation and are therefore suitable for logic-to-automata translations. Several timed logics, including Metric Temporal Logic (MTL), can be converted to equivalent 1-clock ATAs (1-ATAs). Satisfiability of an MTL formula reduces to checking emptiness of a 1-ATA. A straightforward modification of the 1-ATA emptiness algorithm can be applied for model-checking timed automata models against 1-ATA specifications. Existing emptiness algorithms for 1-ATA proceed by a region construction, and are not satisfactory for implementations. On the other hand, emptiness for classical timed automata proceeds by zone-based methods that have been extensively studied with well developed implementations. Therefore, logic-to-automata tools typically perform a sophisticated conversion of the formula into a network of timed automata, sometimes, via a 1-ATA as an intermediate step. Our goal in this work is to initiate the study of zone-based methods directly for 1-ATAs. The challenge here, as opposed to timed automata, is the fact that the zone graph may generate an unbounded number of variables. We first introduce a deactivation operation on the 1-ATA syntax to allow an explicit deactivation of the clock in transitions. Using the deactivation operation, we improve the existing MTL-to-1-ATA conversion and present a fragment of MTL for which the equivalent 1-ATA generate a bounded number of variables. Secondly, we develop the idea of zones for 1-ATA and present an emptiness algorithm which explores a corresponding zone graph. For termination, a special entailment check between zones is necessary. Our main technical contributions are: (1) an algorithm for the entailment check using simple zone operations and (2) an 𝖭𝖯 \mathsf{NP} -hardness for the entailment check in the general case. Finally, we adapt our methods to the problem of model-checking timed automata models against 1-ATA specifications. We observe that when the timed automaton is strongly non-Zeno or when the 1-ATA generates a bounded number of variables, a modified entailment check with quadratic complexity can be applied. [a] [b,c] [b] 1. Introduction Model-checking real-time systems. The task of verifying if a model A (typically a network of automata) satisfies a specification \varphi (a formula in a logic) can be cast as the emptiness of an automaton A\times B_{\neg\varphi} , where B_{\neg\varphi} is an automaton recognizing the set of behaviours that violate the specification – in other words, an automaton corresponding to \neg\varphi . This is the well-known model-checking paradigm. In the context of real-time systems, timed automata [ 5 ] are the de-facto choice for the automaton model. For the logic part, metric temporal logic (MTL) is a natural extension of the widely used linear temporal logic (LTL), incorporating timing constraints in the modalities. However, timed logics cannot be easily converted to timed automata, since they are not closed under complementation. A popular choice for logic-to-automata translations for timed logics, is the model of 1-clock Alternating Timed Automata (1-ATAs) [ 38 , 35 ] . 1-ATAs are closed under complementation, and are incomparable in expressive power to (multi-clock) timed automata. The power of alternation enables resetting fresh copies of the single clock at different positions along the word. Therefore, while reading a timed word, a 1-ATA can keep track of the time elapsed from multiple positions in the word. This feature is quite convenient to handle timed modalities like \operatorname{U}_{I} , which is an Until operator with an interval constraint I . Therefore, the model-checking problem reduces to checking the emptiness of A\times B_{\neg\varphi} where A is a timed automaton and B_{\neg\varphi} is a 1-ATA. This is a rather natural formulation of the model-checking problem in the real-time setting. Surprisingly, there is no tool that implements an algorithm to this problem, to the best of our knowledge. Decidability of this question follows from [ 36 ] and [ 35 ] . However it is based on extended regions and not suitable for practical implementations. On the other hand, emptiness for classical timed automata has been extensively studied over the last three decades, and there are mature and well developed tools like UPPAAL [ 33 ] , PAT [ 40 ] , LTSMin [ 30 ] , TChecker [ 27 ] , Theta [ 41 ] . Algorithms for classical timed automata are based on zones . These are convenient data structures that symbolically capture reachable configurations of a timed automaton. Our goal is to eventually adapt the best known methods from timed automata literature to solve the emptiness of A\times B_{\neg\varphi} . The crucial missing piece in this picture is a zone-based algorithm to handle 1-ATAs, like B_{\neg\varphi} . This is the subject of this paper. The challenge. Undoubtedly, the biggest challenge in developing a zone-based procedure for 1-ATA is the unbounded size of the configurations that it generates (illustrated in Fig. 4 ). As said earlier, a 1-ATA maintains several copies of its clock, each of them storing the time since a specific position. This not only adds technical difficulty in describing zone graphs, but it also makes some of the operations used in the computation algorithmically hard. In this work, we pinpoint the challenges and provide some efficient algorithmic solutions for some restricted cases of 1-ATA which arise from fragments of MTL. Contributions. As a first contribution, we introduce a new deactivation operation for the clock, on transitions. When a clock is deactivated, the branch of the 1-ATA that passes through the transition maintains only the control state, and not the clock value (until the clock gets reactivated again through a reset). This explicit deactivation helps reducing the number of active clock copies maintained by the 1-ATA. To substantiate this idea, we improve the MTL-to-1-ATA construction of [ 38 ] using the deactivation operator and identify a fragment that induces 1-ATAs with bounded width – these are automata which contain a bounded number of active clock copies in any reachable configuration. Next, we present a definition of a zone graph for the enhanced 1-ATAs with the deactivation operation, and provide an algorithm to compute the zone successors. For termination of the zone graph computation, we adapt the entailment relation between zones, studied in [ 1 ] , to our setting. Our main technical contribution is a close study of this entailment check. • We provide an algorithm for the entailment check using standard zone operations known from the timed automata literature. • We prove that deciding non-entailment is \mathsf{NP} -hard, by reducing the monotone 3-SAT problem to the non-entailment check. • Then, we present a modified entailment check, with quadratic complexity, for 1-ATAs with bounded width. A shorter version of this work, reporting on all the contributions mentioned above, appeared in [ 15 ] . In this extended version, we firstly include all the missing proofs and present a new elaborate section on extending the zone graph algorithm to the product A\times B_{\neg\varphi} in order to solve the model-checking problem. As a new contribution, we focus on the case when A is strongly non-Zeno , that is, there is a number k such that in every