Some observations concerning alternating Turing machines using small space
From MaRDI portal
Publication:1097697
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
Related Items
A hierarchy that does not collapse : alternations in low level space, CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES, 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