The Library
Reachability in pushdown register automata
Tools
Murawski, Andrzej S., Ramsay , S. J. and Tzevelekos, N. (2017) Reachability in pushdown register automata. Journal of Computer and System Sciences, 87 . pp. 58-83. doi:10.1016/j.jcss.2017.02.008 ISSN 0022-0000.
|
PDF
WRAP-reachability-pushdown-register-automata-Murawski-2017.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1043Kb) | Preview |
|
PDF
WRAP_dcs-060317-wrap_-pdra.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (614Kb) |
Official URL: https://doi.org/10.1016/j.jcss.2017.02.008
Abstract
We investigate reachability in pushdown automata over infinite alphabets. We show that, in terms of reachability/emptiness,
these machines can be faithfully represented using only 3r elements of the alphabet, where r is the number of registers. We settle the complexity of associated reachability/emptiness problems. In contrast to register automata, the emptiness problem for pushdown register automata is EXPTIME-complete, independent of the register
storage policy used. We also solve the global reachability problem by representing pushdown configurations with a special register automaton. Finally, we examine extensions of pushdown storage to higher orders and show that reachability is undecidable at order 2.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Journal or Publication Title: | Journal of Computer and System Sciences | ||||||||
Publisher: | Academic Press | ||||||||
ISSN: | 0022-0000 | ||||||||
Official Date: | August 2017 | ||||||||
Dates: |
|
||||||||
Volume: | 87 | ||||||||
Page Range: | pp. 58-83 | ||||||||
DOI: | 10.1016/j.jcss.2017.02.008 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 8 March 2017 | ||||||||
Date of first compliant Open Access: | 4 August 2017 | ||||||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||||||
Grant number: | EP/J019577/1 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year