Some observations concerning alternating Turing machines using small space
From MaRDI portal
DOI10.1016/0020-0190(87)90085-8zbMATH Open0635.68040OpenAlexW1964179274MaRDI QIDQ1097697FDOQ1097697
Oscar H. Ibarra, Jik H. Chang, 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
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
- Title not available (Why is that?)
- Alternation
- Halting space-bounded computations
- Title not available (Why is that?)
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Some Results on Tape-Bounded Turing Machines
- Title not available (Why is that?)
- Space bounds for processing contentless inputs
- Alternating on-line Turing machines with only universal states and small space bounds
- Title not available (Why is that?)
- On tape bounds for single letter alphabet language processing
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
- CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES
- Title not available (Why is that?)
- A note on three-dimensional alternating Turing machines with space smaller than \(\log m\)
- Erratum to: Some observations concerning alternating Turing machines using small space
- The alternation hierarchy for sublogarithmic space is infinite
- 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)
