On the relationship between reachability problems in timed and counter automata
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 c...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2012
|
| _version_ | 1797081849388859392 |
|---|---|
| author | Haase, C Ouaknine, J Worrell, J |
| author_facet | Haase, C Ouaknine, J Worrell, J |
| author_sort | Haase, C |
| collection | OXFORD |
| description | 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. © 2012 Springer-Verlag. |
| first_indexed | 2024-03-07T01:19:51Z |
| format | Journal article |
| id | oxford-uuid:8ff3b58c-431c-4c0c-a4ad-b909d59a13d1 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:19:51Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:8ff3b58c-431c-4c0c-a4ad-b909d59a13d12022-03-26T23:08:04ZOn the relationship between reachability problems in timed and counter automataJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:8ff3b58c-431c-4c0c-a4ad-b909d59a13d1EnglishSymplectic Elements at Oxford2012Haase, COuaknine, JWorrell, JThis 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. © 2012 Springer-Verlag. |
| spellingShingle | Haase, C Ouaknine, J Worrell, J On the relationship between reachability problems in timed and counter automata |
| title | On the relationship between reachability problems in timed and counter automata |
| title_full | On the relationship between reachability problems in timed and counter automata |
| title_fullStr | On the relationship between reachability problems in timed and counter automata |
| title_full_unstemmed | On the relationship between reachability problems in timed and counter automata |
| title_short | On the relationship between reachability problems in timed and counter automata |
| title_sort | on the relationship between reachability problems in timed and counter automata |
| work_keys_str_mv | AT haasec ontherelationshipbetweenreachabilityproblemsintimedandcounterautomata AT ouakninej ontherelationshipbetweenreachabilityproblemsintimedandcounterautomata AT worrellj ontherelationshipbetweenreachabilityproblemsintimedandcounterautomata |