We study the formal language theory of multistack pushdown automata (MPA) restricted to computations where a symbol can be popped from a stack S only if it was pushed within a bounded number of contexts of S (scoped MPA). We show that scoped MPA are indeed a robust model of computation, by focusing on the corresponding theory of visibly MPA (MVPA). We prove the equivalence of the deterministic and nondeterministic versions and show that scope-bounded computations of an n-stack MVPA can be simulated, rearranging the input word, by using only one stack. These results have some interesting consequences, such as, the closure under complement, the decidability of universality, inclusion and equality, and the effective semilinearity of the Parikh image (Parikh's theorem). As a further contribution, we give a logical characterization and compare the expressiveness of the scope-bounded restriction with other MVPA classes from the literature. To the best of our knowledge, scoped MVPA languages form the largest class of formal languages accepted by MPA that enjoys all the above nice properties.

Scope-Bounded Pushdown Languages

LA TORRE, Salvatore;NAPOLI, Margherita;PARLATO, GENNARO
2016-01-01

Abstract

We study the formal language theory of multistack pushdown automata (MPA) restricted to computations where a symbol can be popped from a stack S only if it was pushed within a bounded number of contexts of S (scoped MPA). We show that scoped MPA are indeed a robust model of computation, by focusing on the corresponding theory of visibly MPA (MVPA). We prove the equivalence of the deterministic and nondeterministic versions and show that scope-bounded computations of an n-stack MVPA can be simulated, rearranging the input word, by using only one stack. These results have some interesting consequences, such as, the closure under complement, the decidability of universality, inclusion and equality, and the effective semilinearity of the Parikh image (Parikh's theorem). As a further contribution, we give a logical characterization and compare the expressiveness of the scope-bounded restriction with other MVPA classes from the literature. To the best of our knowledge, scoped MVPA languages form the largest class of formal languages accepted by MPA that enjoys all the above nice properties.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4678463
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 13
social impact