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

Prelegent(ci)

Paweł Parys

Afiliacja

Uniwersytet Warszawski

Termin

24 lutego 2010 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---