Michaela Slaats, I7
|Title||Higher-Order Stacks vs. Higher-Order Counter|
|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.
- Subscribe to the ics feed.
- No Events