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.
|Titolo:||The descriptional power of sublogarithmic resource bounded Turing machines|
|Autori interni:||MEREGHETTI, CARLO (Primo)|
|Parole Chiave:||Computational lower bounds; Regular languages|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2007|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|
- PubMed Central loading...