Space and Reversals Complexity
of Nonregular Languages
Alberto Bertoni, Carlo Mereghetti, and Giovanni Pighizzini
Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
Abstract
In this paper, lower bounds on space and input
head reversals for deterministic, nondeterministic, and alternating Turing
machines accepting nonregular languages are studied.
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 prove 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.
Download
Compressed postscript
Compressed dvi