On Multi-stack Visibly Pushdown Languages
Salvatore La Torre, Margherita Napoli, Gennaro Parlato · ePrints Soton (University of Southampton) · 2013
Abstract. We contribute to the theory of formal languages of visibly multistack pushdown automata (Mvpa). First, we show closure under the main operations and decidability of the main decision problems for the class of Mvpa restricted to computations where a symbol can be popped from a stack S only if it was pushed within the last k contexts of S, for a given k (in each context only one stack can be pushed or popped). In particular, this class turns out to be determinizable. Second, we show the closure under complement of the class of languages accepted by ordered Mvpa, where the limitation is that a stack can be popped only if all the lower indexed stacks are empty. This also gains the decidability of universality, inclusion and equivalence. As a further contribution, we compare the classes of languages accepted by different models of Mvpa. 1