In this paper we prove a tight log n lower bound on the product of space and input head inversions for any Turing machine (equipped with a read-only input tape) accepting a nonregular language.
In this paper we prove a tight log n lower bound on the product of space and input head inversions for any Turing machine (equipped with a read-only input tape) accepting a nonregular language.
An optimal lower-bound for nonregular languages / A. Bertoni, C. Mereghetti, G. Pighizzini. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 50:6(1994), pp. 289-292. [10.1016/0020-0190(94)00056-5]
An optimal lower-bound for nonregular languages
A. Bertoni;C. Mereghetti;G. Pighizzini
1994
Abstract
In this paper we prove a tight log n lower bound on the product of space and input head inversions for any Turing machine (equipped with a read-only input tape) accepting a nonregular language.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
551.68 kB
Formato
Adobe PDF
|
551.68 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
|
pubblicato(5).pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
130.1 kB
Formato
Adobe PDF
|
130.1 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.
