Evènement pour le groupe Graphes et Logique


Date 2009-01-13  11:00-12:00
TitreEmptiness of (ordered) multi-pushdown automata is 2ETIME-complete 
RésuméWe consider multi-pushdown automata (Breveglieri et al. 1996), a multi-stack extension of pushdown automata that comes with a constraint on stack operations: a pop can only be performed on the first non-empty stack (which implies that we assume a linear ordering on the collection of stacks). We show that the emptiness problem for multi-pushdown automata is 2ETIME-complete wrt. the number of stacks. Containment in 2ETIME is shown by translating an automaton into a grammar for which we can check if the generated language is empty. We correct the proof given by Breveglieri et al. The lower bound is established by simulating the behavior of an alternating Turing machine working in exponential space. We also compare multi-pushdown automata with the model of bounded-phase multi-stack (visibly) pushdown automata. 
Lieu076 
OrateurPeter Habermehl 
UrlLIAFA 



Aucun document lié à cet événement.

Retour
Retour à l'index