Skip to content

Reachability in Pushdown Register Automata

Research output: Contribution to journalArticle

Original languageEnglish
Pages (from-to)58-83
Number of pages26
JournalJournal of Computer and System Sciences
Volume87
Early online date8 Mar 2017
DOIs
DateAccepted/In press - 13 Feb 2017
DateE-pub ahead of print - 8 Mar 2017
DatePublished (current) - Aug 2017

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.

    Research areas

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

Download statistics

No data available

Documents

Documents

  • Full-text PDF (final published version)

    Rights statement: This is the final published version of the article (version of record). It first appeared online via Elsevier at http://www.sciencedirect.com/science/article/pii/S0022000017300272 . Please refer to any applicable terms of use of the publisher.

    Final published version, 707 KB, PDF document

    Licence: CC BY

DOI

View research connections

Related faculties, schools or groups