@article{BERARD2022106208,
    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.},
    Author = {B{\'e}rard, B{\'e}atrice and Haddad, Serge},
    ISSN = {0020-0190},
    Journal = {Information Processing Letters},
    Keywords = {Interrupt Timed Automata, Reachability problems, Complexity, Real-time systems},
    Pages = {106208},
    Title = {Revisiting reachability in Polynomial Interrupt Timed Automata},
    URL = {https://www.sciencedirect.com/science/article/pii/S002001902100123X},
    Volume = {174},
    Year = {2022},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S002001902100123X},
    bdsk-url-2 = {https://doi.org/10.1016/j.ipl.2021.106208},
    date-added = {2021-11-11 22:35:20 +0100},
    date-modified = {2021-11-11 22:35:20 +0100},
    doi = {10.1016/j.ipl.2021.106208}
}

@article{BERARD2022106208, 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.}, Author = {B{\'e}rard, B{\'e}atrice and Haddad, Serge}, ISSN = {0020-0190}, Journal = {Information Processing Letters}, Keywords = {Interrupt Timed Automata, Reachability problems, Complexity, Real-time systems}, Pages = {106208}, Title = {Revisiting reachability in Polynomial Interrupt Timed Automata}, URL = {https://www.sciencedirect.com/science/article/pii/S002001902100123X}, Volume = {174}, Year = {2022}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S002001902100123X}, bdsk-url-2 = {https://doi.org/10.1016/j.ipl.2021.106208}, date-added = {2021-11-11 22:35:20 +0100}, date-modified = {2021-11-11 22:35:20 +0100}, doi = {10.1016/j.ipl.2021.106208} }