On reversal bounded alternating Turing machines
DOI10.1016/0304-3975(87)90138-1zbMATH Open0643.68065OpenAlexW1983106665MaRDI QIDQ1102114FDOQ1102114
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
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
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)
Cites Work
- Reversal-bounded multipushdown machines
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- Alternation
- On alternation
- Finite-Turn Pushdown Automata
- Title not available (Why is that?)
- 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
- The reduction of tape reversals for off-line one-tape Turing machines
- Tape-reversal bounded Turing machine computations
- Note on tape reversal complexity of languages
- A characterization of reversal-bounded multipushdown machine languages
Cited In (24)
- A note on alternating on-line Turing machines
- Automata with Reversal-Bounded Counters: A Survey
- On the power of alternation on reversal-bounded alternating Turing machines with a restriction
- Alternation with restrictions on looping
- Unboundedness problems for machines with reversal-bounded counters
- Solvable problems for transformers with reversal-bounded counters
- Title not available (Why is that?)
- On the power of 1-tape off-line ATMs running in a bounded number of reversals
- On reversible Turing machines and their function universality
- Reversal complexity revisited
- Reversal-Bounded Counter Machines Revisited
- A lower bound for reversible automata
- Reversal Complexity Classes for Alternating Turing Machines
- The alternation hierarchy for sublogarithmic space is infinite
- Turing machines with access to history
- 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
- Title not available (Why is that?)
- 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)
