On reversal bounded alternating Turing machines

DOI10.1016/0304-3975(87)90138-1zbMath0643.68065OpenAlexW1983106665MaRDI QIDQ1102114

Marek Piotrów, Krzysztof Loryś, Maciej Liśkiewicz

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90138-1

zbMATH Keywords

regular languagesspace complexityalternating Turing machinesreversal complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items

On the power of 1-tape off-line ATMs running in a bounded number of reversals, On the power of alternation on reversal-bounded alternating Turing machines with a restriction, The alternation hierarchy for sublogarithmic space is infinite

Cites Work

• Unnamed Item
• A characterization of reversal-bounded multipushdown machine languages
• On alternation
• Reversal-bounded multipushdown machines
• The reduction of tape reversals for off-line one-tape Turing machines
• Tape-reversal bounded Turing machine computations
• On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
• Alternation
• Reversal-Bounded Acceptors and Intersections of Linear Languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Finite-Turn Pushdown Automata
• Note on tape reversal complexity of languages