Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages.

Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini

Browse the full MFCS paper archive.