Reachability in Pushdown Register Automata

Andrzrej Murawski; Steven Ramsay; Nikos Tzevelekos

doi:10.1016/j.jcss.2017.02.008

Reachability in Pushdown Register Automata

Andrzrej Murawski
, Steven Ramsay
, Nikos Tzevelekos

Research output: Contribution to journal › Article (Academic Journal) › peer-review

13 Citations (Scopus)

414 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 language	English
Pages (from-to)	58-83
Number of pages	26
Journal	Journal of Computer and System Sciences
Volume	87
Early online date	8 Mar 2017
DOIs	https://doi.org/10.1016/j.jcss.2017.02.008
Publication status	Published - Aug 2017

Research Groups and Themes

Programming Languages

Keywords

Register automata
Pushdown automata
Reachability
Infinite alphabets
Complexity

Access to Document

10.1016/j.jcss.2017.02.008Licence: Unspecified

Full-text PDF (final published version)
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 KBLicence: CC BY

Handle.net

Persistent link

Dr Steven Ramsay
- steven.ramsaybristol.acuk
- School of Computer Science - Associate Professor in Programming Languages
Person: Academic

Cite this

@article{0a7295da301f4f64ba89efa9bccab701,

title = "Reachability in Pushdown Register Automata",

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.",

keywords = "Register automata, Pushdown automata, Reachability, Infinite alphabets, Complexity",

author = "Andrzrej Murawski and Steven Ramsay and Nikos Tzevelekos",

year = "2017",

month = aug,

doi = "10.1016/j.jcss.2017.02.008",

language = "English",

volume = "87",

pages = "58--83",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Reachability in Pushdown Register Automata

AU - Murawski, Andrzrej

AU - Ramsay, Steven

AU - Tzevelekos, Nikos

PY - 2017/8

Y1 - 2017/8

N2 - 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.

AB - 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.

KW - Register automata

KW - Pushdown automata

KW - Reachability

KW - Infinite alphabets

KW - Complexity

U2 - 10.1016/j.jcss.2017.02.008

DO - 10.1016/j.jcss.2017.02.008

M3 - Article (Academic Journal)

SN - 0022-0000

VL - 87

SP - 58

EP - 83

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

Reachability in Pushdown Register Automata

Abstract

Research Groups and Themes

Keywords

Access to Document

Handle.net

Fingerprint

Profiles

Dr Steven Ramsay

Cite this