Reachability in pushdown register automata

Citation data:

Journal of Computer and System Sciences, ISSN: 0022-0000, Vol: 87, Page: 58-83

Publication Year:
2017
Usage 195
Abstract Views 195
Captures 2
Readers 2
Social Media 1
Shares, Likes & Comments 1
DOI:
10.1016/j.jcss.2017.02.008
Author(s):
A. S. Murawski, S. J. Ramsay, N. Tzevelekos
Publisher(s):
Elsevier BV
Tags:
Mathematics, Computer Science
article description
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 3 r 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.

This article has 0 Wikipedia mention.