Revisiting Reachability in Polynomial Interrupt Timed Automata
Abstract
Polynomial Interrupt Timed Automata (PolITA) are finite automata with clocks organized along hierarchical levels. These clocks are equipped with an interruption mechanism, well suited to the modeling of real-time operating systems. Moreover, transitions between states contain polynomial guards and updates. The reachability problem in this class is known to be in 2EXPTIME with a decision procedure based on the cylindrical algebraic decomposition. We improve this complexity to EXPSPACE mainly using a combinatorial argument and we include a reduction leading to a PSPACE lower bound.
Domains
Computer Science [cs]
Fichier principal
Bérard et Haddad - 2022 - Revisiting reachability in Polynomial Interrupt Ti.pdf (309.99 Ko)
Télécharger le fichier
Origin | Files produced by the author(s) |
---|