Reversal Complexity Classes for Alternating Turing Machines

DOI10.1137/0219014MaRDI QIDQ3034821zbMATH OpenOpenAlexFDO

Authors Mirosław Kutyłowski, Maciej Liśkiewicz, Krzysztof Loryś

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219014

zbMATH Keywords

Alternating Turing machinescomputational complexityregular languagesreversal complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On reversal bounded 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
• Reversals and alternation
• scientific article; zbMATH DE number 88942

Cited in

(16)

• Alternating multicounter machines with constant number of reversals
• Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
• On reversal bounded alternating Turing machines
• The alternation hierarchy for sublogarithmic space is infinite
• On the power of alternation on reversal-bounded alternating Turing machines with a restriction
• Reversal Hierarchies for Small 2DFAs
• GENERALIZED COUNTERS AND REVERSAL COMPLEXITY
• scientific article; zbMATH DE number 88942 (Why is no real title available?)
• ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
• scientific article; zbMATH DE number 1916669 (Why is no real title available?)
• scientific article; zbMATH DE number 781240 (Why is no real title available?)
• On the power of 1-tape off-line ATMs running in a bounded number of reversals
• Reversals and alternation
• Fundamentals of Computation Theory
• On input read-modes of alternating Turing machines
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories

This page was built for publication: Reversal Complexity Classes for Alternating Turing Machines

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