Some properties of one-pebble Turing machines with sublogarithmic space

DOI10.1016/J.TCS.2005.04.003MaRDI QIDQ2566005zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

AlternationDeterministic one-counter automataOne-pebble Turing machinesSpace hierarchy

Mathematics Subject Classification ID

Recommendations

• Algorithms and Computation
• A note on one-pebble two-dimensional Turing machines
• A note on one-pebble two-dimensional Turing machines
• A note on alternating one-pebble Turing machines with sublogarithmic space
• One pebble versus \(\varepsilon\cdot\log n\) bits

Cites work

• scientific article; zbMATH DE number 3738961 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Alternation
• Language recognition by marking automata
• On pebble automata
• Some Results on Tape-Bounded Turing Machines
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• The alternation hierarchy for sublogarithmic space is infinite
• Turing machines with sublogarithmic space

Cited in

(8)

• Computational power of one-way Turing machines with sublogarithmic memory restrictions
• A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space
• A note on one-pebble two-dimensional Turing machines
• Gradually intractable problems and nondeterministic log-space lower bounds
• Algorithms and Computation
• A note on one-pebble two-dimensional Turing machines
• One pebble versus \(\varepsilon\cdot\log n\) bits
• A note on alternating one-pebble Turing machines with sublogarithmic 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)