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.

An optimal lower-bound for nonregular languages

A. Bertoni
Primo
;
C. Mereghetti
Secondo
;
G. Pighizzini
Ultimo
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.
computational complexity; formal languages; lower bounds
Settore INF/01 - Informatica
Article (author)
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
Pubblicazioni consigliate

Caricamento 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: http://hdl.handle.net/2434/179187
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 9
social impact