Some observations concerning alternating Turing machines using small space
From MaRDI portal
Publication:1097697
DOI10.1016/0020-0190(87)90085-8zbMath0635.68040OpenAlexW1964179274MaRDI QIDQ1097697
Oscar H. Ibarra, Jik H. Chang, Leonard Berman, Bala 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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (12)
On 1-inkdot alternating Turing machines with small space ⋮ Erratum to: Some observations concerning alternating Turing machines using small space ⋮ Constructions for alternating finite automata∗ ⋮ Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ On space-bounded synchronized alternating Turing machines ⋮ Alternation for sublogarithmic space-bounded alternating pushdown automata ⋮ Complement for two-way alternating automata ⋮ Some notes on strong and weak log log n space complexity ⋮ CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES ⋮ The alternation hierarchy for sublogarithmic space is infinite ⋮ Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Some observations concerning alternating Turing machines using small space
