Reachability in Two-Clock Timed Automata is PSPACE-complete

Fearnley, J and Jurdzinski, M
(2015) Reachability in Two-Clock Timed Automata is PSPACE-complete. Information and Computation, 243. 26 - 36.

[img] Text
paper.pdf - Accepted Version

Download (314kB)


Recently, Haase, Ouaknine, and Worrell have shown that reachability in two-clock timed automata is log-space equivalent to reachability in bounded one-counter automata. We show that reachability in bounded one-counter automata is PSPACE-complete.

Item Type: Article
Additional Information: ## TULIP Type: Articles/Papers (Journal) ##
Uncontrolled Keywords: timed automata, counter automata, PSPACE-complete
Depositing User: Symplectic Admin
Date Deposited: 31 Jan 2017 16:37
Last Modified: 15 Aug 2022 20:04
DOI: 10.1016/j.ic.2014.12.004
Related URLs: