The Library
Reachability in pushdown register automata
Tools
Tools
Tools
Murawski, Andrzej S., Ramsay, Steven J. and Tzevelekos, Nikos (2014) Reachability in pushdown register automata. In: Csuhaj-Varjú, E. and Dietzfelbinger, Martin and Ésik, Zoltán, 1951-, (eds.) Mathematical Foundations of Computer Science 2014 : 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I. Lecture Notes in Computer Science, Volume 8634 . Berlin ; London: Springer, pp. 464-473. ISBN 9783662445211
|
PDF
WRAP_Murawski_1271755-cs-121214-paper_259-2.pdf - Accepted Version - Requires a PDF viewer. Download (595Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-662-44522-8_39
Abstract
We investigate reachability in pushdown automata over infinite alphabets: machines with finite control, a finite collection of registers and pushdown stack. First we show that, despite the stack’s unbounded storage capacity, in terms of reachability/emptiness these machines can be faithfully represented by using only 3r elements of the infinite alphabet, where r is the number of registers. Moreover, this bound is tight. Next we settle the complexity of the associated reachability/emptiness problems. In contrast to register automata, where differences in register storage policies gave rise to differing complexity bounds, the emptiness problem for pushdown register automata is EXPTIME-complete in all cases. We also provide a solution to the global reachability problem, based on representing pushdown configurations with a special register automaton. Finally, we examine extensions of pushdown storage to higher orders and show that reachability is undecidable already at order 2, unlike in the finite alphabet case.
| Item Type: | Book Item | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Machine theory, Formal languages | ||||
| Series Name: | Lecture Notes in Computer Science | ||||
| Publisher: | Springer | ||||
| Place of Publication: | Berlin ; London | ||||
| ISBN: | 9783662445211 | ||||
| ISSN: | 0302-9743 | ||||
| Book Title: | Mathematical Foundations of Computer Science 2014 : 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I | ||||
| Editor: | Csuhaj-Varjú, E. and Dietzfelbinger, Martin and Ésik, Zoltán, 1951- | ||||
| Official Date: | 2014 | ||||
| Dates: |
|
||||
| Volume: | Volume 8634 | ||||
| Number of Pages: | 9 | ||||
| Page Range: | pp. 464-473 | ||||
| DOI: | 10.1007/978-3-662-44522-8_39 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Description: | |||||
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), Royal Academy of Engineering (Great Britain) | ||||
| Grant number: | EP/J019577/1 (EPSRC) |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
