Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

One Pebble Versus e log n Bits

Geffer V., Mereghetti C., Pighizzin G.

Fundamenta Informaticae

2010

Vol. 104, nr 1/2

55-69

We show that, for any ε> 0, there exists a language accepted in strong ĺź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.