We study lower bounds on space and input head reversals for deterministic, nondeterministic, and alternating Turing machines accepting nonregular languages. Three notions of space, namely strong, middle, weak, are considered and another notion, called accept, is introduced. In all cases we obtain tight lower bounds. Moreover, we show that, while for determinism and nondeterminism such lower bounds are optimal even with respect to unary languages, for alternation optimal lower bounds for unary languages turn out to be strictly higher than those for languages over alphabets with two or more symbols.
The descriptional power of sublogarithmic resource bounded Turing machines / C. Mereghetti - In: Descriptional Complexity of Formal Systems / [a cura di] V. Geffert, G. Pighizzini. - Kosice : Institute of Computer Science, 2007. - ISBN 9788070976883. - pp. 12-26 (( Intervento presentato al 9. convegno Descriptional Complexity of Formal Systems tenutosi a High Tatras nel 2007.
The descriptional power of sublogarithmic resource bounded Turing machines
C. MereghettiPrimo
2007
Abstract
We study lower bounds on space and input head reversals for deterministic, nondeterministic, and alternating Turing machines accepting nonregular languages. Three notions of space, namely strong, middle, weak, are considered and another notion, called accept, is introduced. In all cases we obtain tight lower bounds. Moreover, we show that, while for determinism and nondeterminism such lower bounds are optimal even with respect to unary languages, for alternation optimal lower bounds for unary languages turn out to be strictly higher than those for languages over alphabets with two or more symbols.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
246.42 kB
Formato
Adobe PDF
|
246.42 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.