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

checking stackscomplexity classescomputational power of two-way automatasubrecursive storage mediumTwo-way automata with a stack

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

This paper is concerned with the computational power of two-way automata with more than one subrecursive storage medium. Two-way automata with a stack (a nonerasing stack or a pushdown store, respectively) and an arbitrary number of checking stacks are of special interest. They are able to accept exactly those sets which are elementary in the sense of Kalmár. If the number of checking stacks is fixed, then the computational power of the corresponding restricted classes of automata can also be characterized in terms of time and space complexity classes.

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)

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

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)