Some properties of one-pebble Turing machines with sublogarithmic space
From MaRDI portal
Publication:2566005
DOI10.1016/J.TCS.2005.04.003zbMATH Open1081.68020OpenAlexW2076177183MaRDI QIDQ2566005FDOQ2566005
Authors: Atsuyuki Inoue, Akira Ito, Katsushi Inoue, Tokio Okazaki 
Publication date: 22 September 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.04.003
Recommendations
Cites Work
- Alternation
- Title not available (Why is that?)
- Turing machines with sublogarithmic space
- Title not available (Why is that?)
- The alternation hierarchy for sublogarithmic space is infinite
- Some Results on Tape-Bounded Turing Machines
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
- Language recognition by marking automata
- On pebble automata
Cited In (8)
- A note on one-pebble two-dimensional Turing machines
- One pebble versus \(\varepsilon\cdot\log n\) bits
- Computational power of one-way Turing machines with sublogarithmic memory restrictions
- A note on one-pebble two-dimensional Turing machines
- Algorithms and Computation
- Gradually intractable problems and nondeterministic log-space lower bounds
- A note on alternating one-pebble Turing machines with sublogarithmic space
- A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space
This page was built for publication: Some properties of one-pebble Turing machines with sublogarithmic space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2566005)
