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. pp. 26-36.

[img] Text
paper.pdf - Author Accepted Manuscript

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: 19 Jan 2023 07:19
DOI: 10.1016/j.ic.2014.12.004
Related URLs: