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.
One pebble versus ε · log n bits [One pebble versus epsilon.log n bits] / V. Geffert, C. Mereghetti, G. Pighizzini. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - 104:1-2(2010), pp. 55-69. [10.3233/FI-2010-335]
One pebble versus ε · log n bits [One pebble versus epsilon.log n bits]
C. Mereghetti
Secondo
;G. PighizziniUltimo
2010
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.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
127.24 kB
Formato
Adobe PDF
|
127.24 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
fi_2010_104-1,2_FI104(1-2)04.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
133.55 kB
Formato
Adobe PDF
|
133.55 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.