On the relationship between reachability problems in timed and counter automata

Christoph Haase, Joël Ouaknine, and James Worrell

This paper establishes a relationship between reachability problems in timed automata and space-bounded counter automata. We show that reachability in timed automata with three or more clocks is naturally logarithmic-space interreducible with reachability in space-bounded counter automata with two counters. We moreover show the logarithmic-space equivalence of reachability in two-clock timed automata and space-bounded one-counter automata. This last reduction provides new insight into two problems whose precise computational complexity have independently been identified as open.

Proceedings of RP 12, LNCS 7550, 2012. 12 pages.

PDF © 2012 Springer-Verlag.

Imprint / Data Protection