On reversal bounded alternating Turing machines

DOI10.1016/0304-3975(87)90138-1MaRDI QIDQ1102114zbMATH OpenOpenAlexFDO

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

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

space complexityregular languagesalternating Turing machinesreversal complexity

Mathematics Subject Classification ID

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

Recommendations

• Reversal Complexity Classes for Alternating Turing Machines
• Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
• On the power of 1-tape off-line ATMs running in a bounded number of reversals
• Alternating multicounter machines with constant number of reversals
• On the power of alternation on reversal-bounded alternating Turing machines with a restriction

Cites work

• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• A characterization of reversal-bounded multipushdown machine languages
• Alternation
• Finite-Turn Pushdown Automata
• Note on tape reversal complexity of languages
• On alternation
• On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
• Reversal-Bounded Acceptors and Intersections of Linear Languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Reversal-bounded multipushdown machines
• Tape-reversal bounded Turing machine computations
• The reduction of tape reversals for off-line one-tape Turing machines

Cited in

(24)

• A note on alternating on-line Turing machines
• On the power of alternation on reversal-bounded alternating Turing machines with a restriction
• Automata with Reversal-Bounded Counters: A Survey
• Alternation with restrictions on looping
• Unboundedness problems for machines with reversal-bounded counters
• Solvable problems for transformers with reversal-bounded counters
• scientific article; zbMATH DE number 3885308 (Why is no real title available?)
• On reversible Turing machines and their function universality
• On the power of 1-tape off-line ATMs running in a bounded number of reversals
• Reversal complexity revisited
• Reversal-Bounded Counter Machines Revisited
• A lower bound for reversible automata
• Reversal Complexity Classes for Alternating Turing Machines
• Turing machines with access to history
• The alternation hierarchy for sublogarithmic space is infinite
• A remark on middle space bounded alternating Turing machines
• ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
• The difference between one tape and two tapes: With respect to reversal complexity
• scientific article; zbMATH DE number 88942 (Why is no real title available?)
• Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
• A NOTE ON REBOUND TURING MACHINES
• An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
• On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
• On input read-modes of alternating Turing machines

This page was built for publication: On reversal bounded alternating Turing machines

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