Reachability in Pushdown Register Automata

Andrzrej Murawski, Steven Ramsay, Nikos Tzevelekos

Research output: Contribution to journalArticle (Academic Journal)peer-review

231 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)58-83
Number of pages26
JournalJournal of Computer and System Sciences
Volume87
Early online date8 Mar 2017
DOIs
Publication statusPublished - Aug 2017

Keywords

  • Register automata
  • Pushdown automata
  • Reachability
  • Infinite alphabets
  • Complexity

Fingerprint Dive into the research topics of 'Reachability in Pushdown Register Automata'. Together they form a unique fingerprint.

Cite this