Relating reachability problems in timed and counter automata

Christoph Haase, Joël Ouaknine, and James Worrell

We establish 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 inter-reducible 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 has recently been employed by Fearnley and Jurdzinski to settle the computational complexity of reachability in two-clock timed automata.

Fundamenta Informaticae 143, 2016. 22 pages.

PDF © 2016 IOS Press.

Imprint / Data Protection