Strong Optimal Lower Bounds for Turing Machines that Accept
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, 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.
Download
Compressed postscript
Compressed dvi