Lower Bounds on Regular Expression Size

Hamoon Mousavi

We introduce linear programs encoding regular expressions of finite languages. We show that, given a language, the optimum value of the associated linear program is a lower bound o…