Iterated stack automata and complexity classes (Q1183602): Difference between revisions
From MaRDI portal
Revision as of 15:50, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Iterated stack automata and complexity classes |
scientific article |
Statements
Iterated stack automata and complexity classes (English)
0 references
28 June 1992
0 references
Iterated stacks and iterated pushdowns are defined from the respective elementary storage types of a repeated application of a ``stack of \(X\)'' resp. ``pushdown of \(X\)'' construction on a storage type \(X\). The increase in computational power of automata using such storage types in the investigated cases is exponential for ``pushdown of'' resp. doubly exponential for ``stack of''. A typical result shown in the article is the characterization of the class \(\text{DTIME}(\exp_ k(\text{poly}))\) by \((k+1)\)-iterated multi- head pushdown automata. Here \(\exp_ k(\text{poly})\) means 2 to the 2 to the \dots to the 2 to the \(p\) (\(k\) iterations of ``2 to the'') for some polynomial \(p\). Similar results hold for iterated versions of stack automata, nested stack automata, checking stack automata, and stack-pushdown automata.
0 references
iterated pushdowns
0 references
pushdown automata
0 references
stack automata
0 references