In this paper, simultaneous lower bounds on space and input head reversals for deterministic, nondeterministic and alternating Turing machines accepting nonregular languages are studied. Three notions of space complexity, namely strong, middle, and weak, are considered; moreover, another notion called accept, is introduced. For all cases we obtain tight lower bounds. In particular, we prove that while in the deterministic and nondeterministic case these bounds are “strongly” optimal—in the sense that we exhibit a nonregular language over a unary alphabet exactly fitting them—in the alternating case optimal lower bounds for tally languages turn out to be higher than those for arbitrary languages.
Strong optimal lower bounds for Turing machines that accept nonregular languages / A. Bertoni, C. Mereghetti, G. Pighizzini (LECTURE NOTES IN COMPUTER SCIENCE). - In: Mathematical Foundations of Computer Science 1995 / [a cura di] J. Wiedermann, P. Hájek. - [s.l] : Springer, 1995. - ISBN 9783540602460. - pp. 309-318 (( Intervento presentato al 20. convegno MFCS '95 tenutosi a Prague nel 1995 [10.1007/3-540-60246-1_137].
Strong optimal lower bounds for Turing machines that accept nonregular languages
A. BertoniPrimo
;C. MereghettiSecondo
;G. PighizziniUltimo
1995
Abstract
In this paper, simultaneous lower bounds on space and input head reversals for deterministic, nondeterministic and alternating Turing machines accepting nonregular languages are studied. Three notions of space complexity, namely strong, middle, and weak, are considered; moreover, another notion called accept, is introduced. For all cases we obtain tight lower bounds. In particular, we prove that while in the deterministic and nondeterministic case these bounds are “strongly” optimal—in the sense that we exhibit a nonregular language over a unary alphabet exactly fitting them—in the alternating case optimal lower bounds for tally languages turn out to be higher than those for arbitrary languages.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
445.07 kB
Formato
Adobe PDF
|
445.07 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.