Higher-Order Stacks vs. Higher-Order Counter

Speaker

Michaela Slaats, I7
Title Higher-Order Stacks vs. Higher-Order Counter
When 09.12..2010, 15:00
Where Lecture Room Informatik 11
Abstract The focus of this talk is to compare the language clases that two closely related automata models can accept. We consider the higher-order pushdown automata and the higher-order counter. The higher-order pushdown automata work with nested stacks which are stacks of stacks of stacks …. The higher-order counter are a special case of the pushdown automata where only one stack symbol is allowed. In this case a level 1 stack can be considered as a natural number and the higher-order counter as stacks of stacks … of numbers. We will show how a level-k pushdown automaton can be simulated by a level-(k+1) counter and claim that the higher-order counter automata can recognize less languages as the higher-order pushdown automata for each level k.
This is work in progress.
Slides