A note on one-pebble two-dimensional Turing machines

DOI10.1016/S1571-0653(04)00499-8MaRDI QIDQ5899349zbMATH OpenFDO

Authors Atsuyuki Inoue, Katsushi Inoue, Akira Ito, Yue Wang, Tokio Okazaki

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S1571-0653(04)00499-8

zbMATH Keywords

alternationdeterminismnondeterminismone pebblespace-bounded computationtwo-dimensional Turing machine

Mathematics Subject Classification ID

Recommendations

• A note on one-pebble two-dimensional Turing machines
• Algorithms and Computation
• Some properties of one-pebble Turing machines with sublogarithmic space
• One pebble versus n bits
• Two-dimensional alternating turing machines with only universal states

Cites work

• Alternation
• scientific article; zbMATH DE number 3738961 (Why is no real title available?)
• The alternation hierarchy for sublogarithmic space is infinite
• The Sublogarithmic Alternating Space World
• Turing machines with sublogarithmic space
• Two-dimensional alternating turing machines with only universal states
• Two-dimensional alternative Turing machines

Cited in

(10)

• On space functions constructed by two-dimensional Turing machines
• A note on two-dimensional probabilistic Turing machines
• Non-closure property of space-bounded two-dimensional alternating Turing machines
• Some properties of one-pebble Turing machines with sublogarithmic space
• One pebble versus n bits
• scientific article; zbMATH DE number 3856412 (Why is no real title available?)
• ZUR RAUMKOMPLIZIERTHEIT MEHRDIMENSIONALER TURING‐AUTOMATEN
• Algorithms and Computation
• A note on one-pebble two-dimensional Turing machines
• A note on alternating one-pebble Turing machines with sublogarithmic space

This page was built for publication: A note on one-pebble two-dimensional Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899349)