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
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.

Compressed postscript
Compressed dvi