Two-way automata with more than one storage medium

DOI10.1016/0304-3975(85)90142-2zbMATH Open0604.68055OpenAlexW2077637024MaRDI QIDQ1083206FDOQ1083206

Authors: Jörg Vogel, K. W. Wagner 

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

Recommendations

• Alternating Pushdown and Stack Automata
• The power of two-way deterministic checking stack automata
• Tree-stack automata
• Some characterizations of multihead finite automata
• Remarks on two-way automata with weak-counters

zbMATH Keywords

complexity classeschecking stackscomputational power of two-way automatasubrecursive storage mediumTwo-way automata with a stack

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Two-way pushdown automata
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Time and tape complexity of pushdown automaton languages
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Counter machines and counter languages
• Classes of Predictably Computable Functions
• Nonerasing stack automata

Cited In (6)

• Two-way two-tape automata
• New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines
• Advocating ownership
• Two-way automaton computations
• Iterated stack automata and complexity classes
• Generalizations of Checking Stack Automata: Characterizations and Hierarchies

This page was built for publication: Two-way automata with more than one storage medium

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