Browse/search for people

Publication - Dr Steven Ramsay

    Reachability in Pushdown Register Automata

    Citation

    Murawski, A, Ramsay, S & Tzevelekos, N, 2017, ‘Reachability in Pushdown Register Automata’. Journal of Computer and System Sciences, vol 87., pp. 58-83

    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.

    Full details in the University publications repository