Two-way automata with more than one storage medium

DOI10.1016/0304-3975(85)90142-2MaRDI QIDQ1083206zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Classes of Predictably Computable Functions
• Counter machines and counter languages
• Nonerasing stack 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
• Two-way pushdown 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)