Tight Lower Bound for the State Complexity of Shuffle of Regular Languages.

Cezar Câmpeanu Kai Salomaa Sheng Yu

Published in: J. Autom. Lang. Comb. (2002)

Keyphrases

lower bound
worst case
upper bound
regular languages
context free languages
optimal solution
grammatical inference
objective function
np hard
finite automata
decision problems
regular expressions
context free grammars
statistical queries
computational complexity
sample complexity
context free