Journal article icon

Journal article

On the relationship between reachability problems in timed and counter automata

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 pro...

Expand abstract

Actions


Access Document


Publisher copy:
10.1007/978-3-642-33512-9_6

Authors


Ouaknine, J More by this author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Journal:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume:
7550 LNCS
Pages:
54-65
Publication date:
2012
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
URN:
uuid:8ff3b58c-431c-4c0c-a4ad-b909d59a13d1
Source identifiers:
355003
Local pid:
pubs:355003
Language:
English

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP