Panic automata

Prelegent(ci)

Jacek Jurewicz

Afiliacja

Uniwersytet Warszawski

Termin

25 października 2006 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Panic automata are an extension of second-order pushdown automata (that operate on a second-order pushdown store, ie. a stack of stacks) by the destructive "panic" operation introduced by P. Urzyczyn in order to fully relate second-order automata to second-order grammars. I will show how a panic automaton (and a non-panic second-order automaton in particular) can be efficiently simulated by a multitape Turing machine, with the preservation of determinism, in spite of a possible quadratic growth of the store. In this case, efficiency means that the length of a run of the machine is proportional to the length of a run of the automaton, which need not be proportional to the size of the input. The result is achieved by introducing an encoding of the pushdown store by a string. Interestingly, while the proof holds for ordinary second-order automata, the encoding relies on additional information stored in the stack, invented exclusively for the "panic" operation.

---