One pebble versus n bits

DOI10.3233/FI-2010-335zbMATH Open1216.68111OpenAlexW1551667740WikidataQ116841317 ScholiaQ116841317MaRDI QIDQ3000290FDOQ3000290

Authors: Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini 

Publication date: 18 May 2011

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2010-335

Recommendations

• Algorithms and Computation
• Some properties of one-pebble Turing machines with sublogarithmic space
• A note on alternating one-pebble Turing machines with sublogarithmic space
• A note on one-pebble two-dimensional Turing machines
• A note on one-pebble two-dimensional Turing machines

zbMATH Keywords

computational complexitypebble machinesinput head reversalsspace-bounded computations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited In (8)

• Title not available (Why is that?)
• On pebble automata
• A note on one-pebble two-dimensional Turing machines
• A note on one-pebble two-dimensional Turing machines
• Algorithms and Computation
• Some properties of one-pebble Turing machines with sublogarithmic space
• A note on alternating one-pebble Turing machines with sublogarithmic space
• A variant of inductive counting

This page was built for publication: One pebble versus \(\varepsilon\cdot\log n\) bits

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