Reachability in two-clock timed automata is PSPACE-complete

DOI10.1016/j.ic.2014.12.004zbMath1345.68155OpenAlexW2952380278MaRDI QIDQ2347796

John Fearnley, Marcin Jurdziński

Publication date: 9 June 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.12.004

zbMATH Keywords

timed automataPSPACE-completecounter automata

Mathematics Subject Classification ID

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

Related Items (17)

On the complexity of timed pattern matching ⋮ Unnamed Item ⋮ Equivalence checking and intersection of deterministic timed finite state machines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bounding Average-Energy Games ⋮ Reachability relations of timed pushdown automata ⋮ Timed Basic Parallel Processes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Trace Refinement in Labelled Markov Decision Processes ⋮ Universality Problem for Unambiguous VASS ⋮ On Affine Reachability Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Continuous One-counter Automata

Cites Work

• Minimum and maximum delay problems in real-time systems
• The complexity of membership problems for circuits over sets of integers
• A theory of timed automata
• Reachability in Succinct and Parametric One-Counter Automata
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• On the Relationship between Reachability Problems in Timed and Counter Automata
• CONCUR 2004 - Concurrency Theory

This page was built for publication: Reachability in two-clock timed automata is PSPACE-complete