@article{MurawskiTzevelekos:JCSS:2017,
    Abstract = {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.},
    Author = {Murawski, A.S. and Ramsay, S.J. and Tzevelekos, N.},
    File = {1-s2.0-S0022000017300272-main (0) - a - a - j.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Keywords = {readme},
    Pages = {58--83},
    Title = {Reachability in pushdown register automata},
    URL = {http://www.sciencedirect.com/science/article/pii/S0022000017300272},
    Volume = {87},
    Year = {2017},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000017300272},
    bdsk-url-2 = {https://doi.org/10.1016/j.jcss.2017.02.008},
    date-added = {2017-06-27 08:59:10 +0000},
    date-modified = {2019-03-07 18:33:23 +0100},
    doi = {10.1016/j.jcss.2017.02.008}
}

@article{MurawskiTzevelekos:JCSS:2017, Abstract = {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.}, Author = {Murawski, A.S. and Ramsay, S.J. and Tzevelekos, N.}, File = {1-s2.0-S0022000017300272-main (0) - a - a - j.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Keywords = {readme}, Pages = {58--83}, Title = {Reachability in pushdown register automata}, URL = {http://www.sciencedirect.com/science/article/pii/S0022000017300272}, Volume = {87}, Year = {2017}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000017300272}, bdsk-url-2 = {https://doi.org/10.1016/j.jcss.2017.02.008}, date-added = {2017-06-27 08:59:10 +0000}, date-modified = {2019-03-07 18:33:23 +0100}, doi = {10.1016/j.jcss.2017.02.008} }