zbMATH — the first resource for mathematics

One pebble versus \(\varepsilon\cdot\log n\) bits. (English) Zbl 1216.68111
Summary: We show that, for any \(\varepsilon > 0\), there exists a language accepted in strong \(\varepsilon\)-log \(n\) space by a 2-way deterministic Turing machine working with a single binary worktape, that cannot be accepted in sublogarithmic weak space by any pebble machine (i.e., a 2-way nondeterministic Turing machine with one pebble that can be moved onto the input cells). Moreover, we provide optimal unary lower bounds on the product of space and input head reversals for strong and weak pebble machines accepting nonregular languages.
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
Full Text: DOI