Strong optimal lower bounds for Turing machines that accept nonregular languages

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.