@article{Haase:2016aa,
    Abstract = {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 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 Jurdzi{\'n}ski to settle the computational complexity of reachability in two-clock timed automata.},
    Author = {Haase, Christoph and Ouaknine, Jo{\"e}l and Worrell, James},
    BookTitle = {Fundamenta Informaticae},
    File = {Relating Reachability Problems in Timed and Counter Automata - haase2016 - a - j.pdf},
    ISBN = {1875-8681},
    Keywords = {timed automata; counter automata; reachability; infinite-state systems},
    Pages = {317--338},
    Publisher = {IOS Press},
    Title = {Relating Reachability Problems in Timed and Counter Automata},
    Volume = {143},
    Year = {2016},
    bdsk-url-1 = {https://doi.org/10.3233/FI-2016-1316},
    date-added = {2020-05-12 22:04:11 +0200},
    date-modified = {2020-05-12 22:04:11 +0200},
    m1 = {3-4},
    ty = {JOUR},
    doi = {10.3233/FI-2016-1316}
}

@article{Haase:2016aa, Abstract = {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 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 Jurdzi{\'n}ski to settle the computational complexity of reachability in two-clock timed automata.}, Author = {Haase, Christoph and Ouaknine, Jo{\"e}l and Worrell, James}, BookTitle = {Fundamenta Informaticae}, File = {Relating Reachability Problems in Timed and Counter Automata - haase2016 - a - j.pdf}, ISBN = {1875-8681}, Keywords = {timed automata; counter automata; reachability; infinite-state systems}, Pages = {317--338}, Publisher = {IOS Press}, Title = {Relating Reachability Problems in Timed and Counter Automata}, Volume = {143}, Year = {2016}, bdsk-url-1 = {https://doi.org/10.3233/FI-2016-1316}, date-added = {2020-05-12 22:04:11 +0200}, date-modified = {2020-05-12 22:04:11 +0200}, m1 = {3-4}, ty = {JOUR}, doi = {10.3233/FI-2016-1316} }