The Library
Reachability in two-clock timed automata is PSPACE-complete
Tools
Fearnley, J. and Jurdzinski, Marcin (2013) Reachability in two-clock timed automata is PSPACE-complete. In: Freivalds, Rūsiņš and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , David, (eds.) Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II. Lecture Notes in Computer Science, Volume 7966 . Berlin ; London: Springer Berlin Heidelberg, pp. 212-223. ISBN 9783642392115
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-39212-2_21
Abstract
Haase, Ouaknine, and Worrell have shown that reachability in two-clock timed automata is log-space equivalent to reachability in bounded one-counter automata. We show that reachability in bounded one-counter automata is PSPACE-complete.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
Place of Publication: | Berlin ; London | ||||
ISBN: | 9783642392115 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II | ||||
Editor: | Freivalds, Rūsiņš and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , David | ||||
Official Date: | 2013 | ||||
Dates: |
|
||||
Volume: | Volume 7966 | ||||
Page Range: | pp. 212-223 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Description: | |||||
Title of Event: | 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 | ||||
Type of Event: | Other | ||||
Location of Event: | Riga, Latvia | ||||
Date(s) of Event: | 8-12 July 2013 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |