Two-way automata with more than one storage medium
From MaRDI portal
Publication:1083206
DOI10.1016/0304-3975(85)90142-2zbMath0604.68055OpenAlexW2077637024MaRDI QIDQ1083206
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90142-2
complexity classeschecking stackscomputational power of two-way automatasubrecursive storage mediumTwo-way automata with a stack
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (3)
New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Iterated stack automata and complexity classes
Cites Work
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Nonerasing stack automata
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
- Classes of Predictably Computable Functions
- Two-way pushdown automata
- Counter machines and counter languages
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Time and tape complexity of pushdown automaton languages
This page was built for publication: Two-way automata with more than one storage medium
