Affiliations: Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia. viliam.geffert@upjs.sk | Dip. di Informatica e Comunicazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy. pighizzini@dico.unimi.it | Dip. di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy. mereghetti@dsi.unimi.it
Note: [] Partially supported by the Slovak Grant Agency for Science (VEGA) under contract 1/0035/09 “Combinatorial structures and complexity of algorithms”.
Note: [] Partially supported by the Italian MIUR under project “Aspetti matematici e applicazioni emergenti degli automi e dei linguaggi formali: metodi probabilistici e combinatori in ambito di linguaggi formali”.
Note: [] Partially supported by the Italian MIUR under project “Aspetti matematici e applicazioni emergenti degli automi e dei linguaggi formali: metodi probabilistici e combinatori in ambito di linguaggi formali”.; Address for correspondence: Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy.
Abstract: 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.
Keywords: computational complexity, space bounded computations, pebble machines, input head reversals
