Panic automata

Speaker(s)

Jacek Jurewicz

Affiliation

Uniwersytet Warszawski

Date

Oct. 25, 2006, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---