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.