Iterated stack automata and complexity classes (Q1183602): Difference between revisions

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.