A note on bounded-reversal multipushdown machines (Q1057071)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A note on bounded-reversal multipushdown machines |
scientific article; zbMATH DE number 3896331
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on bounded-reversal multipushdown machines |
scientific article; zbMATH DE number 3896331 |
Statements
A note on bounded-reversal multipushdown machines (English)
0 references
1984
0 references
Let P(k,n) denote the class of deterministic two-way k-pushdown automata M such that the accepted language T(M) is included in \(a^*\) and M can make at most n reversals in each of its k pushdown tapes. It is shown that P(1,n) induces only regular languages T(M) but there is an automaton M in P(2,1) with T(M) not regular.
0 references
multicounter machines
0 references
pushdown automata
0 references
regular languages
0 references
