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.

Text
paper.pdf - Author Accepted Manuscript
Download (314kB)

Official URL: https://www.sciencedirect.com/science/article/pii/...

Abstract

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:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005483