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. Mereghetti
Secondo
;
G. Pighizzini
Ultimo
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.
Computational complexity; space bounded computations; pebble machines; input head reversals
Settore INF/01 - Informatica
2009
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/67441
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact