Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata.

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

Feb. 24, 2010, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

A second order pushdown automaton is a pushdown automaton, which has a stack of stacks. It works like a normal pushdown automaton, seeing only the topmost sybmol on the topmost stack, but it has additional operation: copy the topmost stack. Sometimes a additional operation is allowed, called a collapse operation. I show that this operation increases the expressive power, when the automata are deterministic.
These automata (both with and without collapse) appear naturally in some contexts.

---