Reachability in pushdown register automata

Citation data:

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

Publication Year:
Usage 195
Abstract Views 195
Captures 7
Readers 7
Social Media 1
Shares, Likes & Comments 1
A. S. Murawski; S. J. Ramsay; N. Tzevelekos
Elsevier BV
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.