Henzinger, TA, Lehtinen, K and Totzke, P 
ORCID: 0000-0001-5274-8190
(2022)
History-Deterministic Timed Automata.
.
Abstract
We explore the notion of history-determinism in the context of timed automata (TA). History-deterministic automata are those in which nondeterminism can be resolved on the fly, based on the run constructed thus far. History-determinism is a robust property that admits different game-based characterisations, and history-deterministic specifications allow for game-based verification without an expensive determinization step. We show yet another characterisation of history-determinism in terms of fair simulation, at the general level of labelled transition systems: a system is history-deterministic precisely if and only if it fairly simulates all language smaller systems. For timed automata over infinite timed words it is known that universality is undecidable for Büchi TA. We show that for history-deterministic TA with arbitrary parity acceptance, timed universality, inclusion, and synthesis all remain decidable and are ExpTime-complete. For the subclass of TA with safety or reachability acceptance, we show that checking whether such an automaton is history-deterministic is decidable (in ExpTime), and history-deterministic TA with safety acceptance are effectively determinizable without introducing new automata states.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 21 Apr 2023 13:47 |
| Last Modified: | 26 Apr 2024 13:47 |
| DOI: | 10.4230/LIPIcs.CONCUR.2022.14 |
| Open Access URL: | https://doi.org/10.4230/LIPIcs.CONCUR.2022.14 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3169856 |
Dimensions
Dimensions
