Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata. (part 2)
- Speaker(s)
- Paweł Parys
- Affiliation
- Uniwersytet Warszawski
- Date
- March 3, 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.
These automata (both with and without collapse) appear naturally in some contexts.