Some observations concerning alternating Turing machines using small space

DOI10.1016/0020-0190(87)90085-8zbMath0635.68040MaRDI QIDQ1097697

Oscar H. Ibarra, Jik H. Chang, Bala Ravikumar, Leonard Berman

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90085-8

zbMATH Keywords

alternating Turing machines; strongly space-bounded; weakly space-bounded

Mathematics Subject Classification ID

Related Items

A hierarchy that does not collapse : alternations in low level space, Alternation for sublogarithmic space-bounded alternating pushdown automata, Erratum to: Some observations concerning alternating Turing machines using small space, On space-bounded synchronized alternating Turing machines, The alternation hierarchy for sublogarithmic space is infinite, On 1-inkdot alternating Turing machines with small space, Some notes on strong and weak log log n space complexity, Sublogarithmic $\sum _2$-space is not closed under complement and other separation results, Constructions for alternating finite automata^∗, Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating on-line Turing machines with only universal states and small space bounds
• Halting space-bounded computations
• Space bounds for processing contentless inputs
• On tape bounds for single letter alphabet language processing
• Alternation
• Some Results on Tape-Bounded Turing Machines
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers