You are not logged in | Log in

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.