We show that pebble machines (i.e., 2-way nondeterministic Turing machines with one pebble that can be moved onto the input cells) working in sublogarithmic weak space are not able to simulate strong log-space bounded 2-way deterministic Turing machines. We prove this by exhibiting a witness language. Moreover, we provide an optimal lower bound on the product of space and input head reversals for pebble machines accepting nonregular languages.
One pebble versus log n bits / V. Geffert, C. Mereghetti, G. Pighizzini - In: Non-classical models for auomata and applications (NCMA) / [a cura di] H. Bordihn, R. Freund, M. Holzer, M. Kutrib, F. Otto. - Wien : Austrian computer society, 2009. - ISBN 9783854032564. - pp. 121-133 (( convegno Non-classical models for automata and applications (NCMA) tenutosi a Wroclaw nel 2009.
One pebble versus log n bits
C. MereghettiSecondo
;G. PighizziniUltimo
2009
Abstract
We show that pebble machines (i.e., 2-way nondeterministic Turing machines with one pebble that can be moved onto the input cells) working in sublogarithmic weak space are not able to simulate strong log-space bounded 2-way deterministic Turing machines. We prove this by exhibiting a witness language. Moreover, we provide an optimal lower bound on the product of space and input head reversals for pebble machines accepting nonregular languages.
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
483.92 kB
Formato
Adobe PDF
|
483.92 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.
