PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA
Hermann Gruber, Markus Holzer · International Journal of Foundations of Computer Science · 2013
Based on recent results from extremal graph theory, we prove that every n-state binary deterministic finite automaton can be converted into an equivalent regular expression of size O(1.742n) using state elimination. Furthermore, we give improved upper bounds on the language operations intersection and interleaving on regular expressions.