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

Alberto Bertoni Carlo Mereghetti Giovanni Pighizzini

Published in: MFCS (1995)

Keyphrases

lower bound
turing machine
upper bound
worst case
optimal cost
objective function
optimal solution
expressive power
data structure
closed form
branch and bound algorithm
branch and bound
optimal strategy
lower and upper bounds
average case
language identification
lower bounding
learning algorithm