Some observations concerning alternating Turing machines using small space

DOI10.1016/0020-0190(87)90085-8MaRDI QIDQ1097697zbMATH OpenOpenAlexFDO

Authors Jik H. Chang, Oscar H. Ibarra, Leonard Berman, B. Ravikumar

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 machinesstrongly space-boundedweakly space-bounded

Mathematics Subject Classification ID

Recommendations

• Alternating on-line Turing machines with only universal states and small space bounds
• On 1-inkdot alternating Turing machines with small space
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• scientific article; zbMATH DE number 3917711
• ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE

Cites work

• scientific article; zbMATH DE number 3723863 (Why is no real title available?)
• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 3575000 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• Alternating on-line Turing machines with only universal states and small space bounds
• Alternation
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Halting space-bounded computations
• On tape bounds for single letter alphabet language processing
• Some Results on Tape-Bounded Turing Machines
• Space bounds for processing contentless inputs

Cited in

(18)

• A note on alternating on-line Turing machines
• Constructions for alternating finite automata^∗
• A hierarchy that does not collapse : alternations in low level space
• Alternation with restrictions on looping
• scientific article; zbMATH DE number 3917711 (Why is no real title available?)
• A note on three-dimensional alternating Turing machines with space smaller than m
• Erratum to: Some observations concerning alternating Turing machines using small space
• The alternation hierarchy for sublogarithmic space is infinite
• Closure property of probabilistic Turing machines and alternating Turing machines with sublogarithmic spaces
• A remark on middle space bounded alternating Turing machines
• On 1-inkdot alternating Turing machines with small space
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• Complement for two-way alternating automata
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
• Alternating on-line Turing machines with only universal states and small space bounds
• On space-bounded synchronized alternating Turing machines
• Some notes on strong and weak log log n space complexity
• Alternation for sublogarithmic space-bounded alternating pushdown automata

This page was built for publication: Some observations concerning alternating Turing machines using small space

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