An optimal lower bound for 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 we prove a tight logn lower bound on
the product of space and input head inversions for any
Turing machine (equipped with a read only input tape) accepting a
nonregular language.