Iterated stack automata and complexity classes

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.

Recommendations

Cites work

Cited in

(30)

This page was built for publication: Iterated stack automata and complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1183602)