Article ID Journal Published Year Pages File Type
426444 Information and Computation 2015 11 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Reachability in two-clock timed automata is PSPACE-complete
Authors
, ,