Können wir eine NFA in einen regulären Ausdruck der Polynomlänge umwandeln?

Können wir eine NFA mit Zuständen in einen regulären Ausdruck der Länge konvertieren ?$n$$\mathrm{poly}(n)$

Im Gegensatz dazu ist bekannt, dass ein regulärer Ausdruck der Länge leicht in einen NFA mit -Zustand umgewandelt werden kann.$n$$\mathcal{O}(n)$

Unter Verwendung des Konzepts der Sternhöhe zeigten Gruber und Holzer in Finite Automaten, Digraph Connectivity und Regular Expression Size, dass es eine Konstante und eine Folge von Sprachen über gibt, die von DFAs akzeptiert werden können mit Zuständen, für die aber jeder reguläre Ausdruck eine Länge von mindestens .$C>1$$L_n$$\{0,1\}$$n$$C^n$