Reachability in Two-Clock Timed Automata Is PSPACE-Complete

DOI10.1007/978-3-642-39212-2_21zbMath1327.68118arXiv1302.3109OpenAlexW2046095317MaRDI QIDQ5327435

Marcin Jurdziński, John Fearnley

Publication date: 7 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.3109

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (13)

Quantum alternation ⋮ On the decidability and complexity of problems for restricted hierarchical hybrid systems ⋮ Average-energy games ⋮ Reachability games with relaxed energy constraints ⋮ Coverability in 2-VASS with one unary counter is in NP ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parametrized automata simulation and application to service composition ⋮ On parametric timed automata and one-counter machines ⋮ Unnamed Item ⋮ The Complexity of Flat Freeze LTL ⋮ Timed network games

This page was built for publication: Reachability in Two-Clock Timed Automata Is PSPACE-Complete