Revisiting Reachability in Polynomial Interrupt Timed Automata - Sorbonne Université
Journal Articles Information Processing Letters Year : 2022

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.
Fichier principal
Vignette du fichier
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)

Dates and versions

hal-03390569 , version 1 (21-10-2021)

Identifiers

Cite

Béatrice Bérard, Serge Haddad. Revisiting Reachability in Polynomial Interrupt Timed Automata. Information Processing Letters, 2022, 174, pp.106208. ⟨10.1016/j.ipl.2021.106208⟩. ⟨hal-03390569⟩
155 View
53 Download

Altmetric

Share

More