Lower bounds for the transition complexity of NFAs.

Michael Domaratzki Kai Salomaa

Published in: J. Comput. Syst. Sci. (2008)

Keyphrases

lower bound
worst case
upper bound
branch and bound algorithm
regular expressions
complexity measures
average case complexity
np hard
online learning
branch and bound
average case
search space
computational cost
space complexity
online algorithms
quadratic assignment problem