@inproceedings{10.1007/978-3-642-33512-9_6,
    Abstract = {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.},
    Address = {Berlin, Heidelberg},
    Author = {Haase, Christoph and Ouaknine, Jo{\"e}l and Worrell, James},
    BookTitle = {Reachability Problems},
    Editor = {Finkel, Alain and Leroux, J{\'e}r{\^o}me and Potapov, Igor},
    File = {Haase2012\_Chapter\_OnTheRelationshipBetweenReacha (0) - a - a - t.pdf},
    ISBN = {978-3-642-33512-9},
    Pages = {54--65},
    Publisher = {Springer Berlin Heidelberg},
    Title = {On the Relationship between Reachability Problems in Timed and Counter Automata},
    Year = {2012},
    date-added = {2019-04-09 16:59:54 +0200},
    date-modified = {2019-04-09 16:59:54 +0200},
    doi = {10.1007/978-3-642-33512-9_6}
}

@inproceedings{10.1007/978-3-642-33512-9_6, Abstract = {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.}, Address = {Berlin, Heidelberg}, Author = {Haase, Christoph and Ouaknine, Jo{\"e}l and Worrell, James}, BookTitle = {Reachability Problems}, Editor = {Finkel, Alain and Leroux, J{\'e}r{\^o}me and Potapov, Igor}, File = {Haase2012_Chapter_OnTheRelationshipBetweenReacha (0) - a - a - t.pdf}, ISBN = {978-3-642-33512-9}, Pages = {54--65}, Publisher = {Springer Berlin Heidelberg}, Title = {On the Relationship between Reachability Problems in Timed and Counter Automata}, Year = {2012}, date-added = {2019-04-09 16:59:54 +0200}, date-modified = {2019-04-09 16:59:54 +0200}, doi = {10.1007/978-3-642-33512-9_6} }