Untere Schranken für die Größe von CFGs für bestimmte endliche Sprachen

Betrachten Sie die folgende natürliche Frage: Was ist bei einer endlichen Sprache die kleinste kontextfreie Grammatik, die L erzeugt ?$L$$L$

Wir können die Frage interessanter machen, indem wir eine Folge von Sprachen , zum Beispiel L n ist die Menge aller Permutationen von { 1 , … , n } : Intuitiv müsste ein CFG für L n die Größe Ω haben ( n ! ) . Wir sind also an der asymptotischen Größe der kleinsten CFGs für die Sprachen interessiert.$L_n$$L_n$$\{1,\ldots,n\}$$L_n$$\Omega(n!)$

Ähnliche Fragen wurden in mehreren Artikeln behandelt:

• Charikar et al. ("Approximation der kleinsten Grammatik: Kolmogorov-Komplexität in natürlichen Modellen") Überlegen Sie, wie schwierig es ist, die Größe der kleinsten CFG zu approximieren, die ein bestimmtes Wort erzeugt .
• Weitere Arbeiten in dieser Richtung sind Arpe und Reischuk, "Über die Komplexität der optimalen grammatikbasierten Komprimierung".
• Peter Asveld hat mehrere Artikel zu diesem Thema verfasst (z. B. "Generieren aller Permutationen durch kontextfreie Grammatik in Chomsky-Normalform"). Er versucht, einige Parameter für bestimmte Grammatiktypen zu optimieren, um die Menge aller Permutationen zu generieren, insbesondere Chomsky- und Greibach-Normalformen.

Bisher konnte ich jedoch kein Papier finden, das versucht, eine Schranke von die Größe eines CFG zu beweisen, das L n erzeugt .$\Omega(n!)$$L_n$

Gibt es Papiere, die untere Grenzen für die Größe von kontextfreien Grammatiken für bestimmte endliche Sprachen festlegen?

In Beantwortung mehrerer Fragen auf dieser Website sowie zu math.stackexchange habe ich eine einfache Methode gefunden, mit der sich exponentielle Untergrenzen für CFGs für bestimmte Sprachen, z. B. . Sind diese Ergebnisse neu? Ich kann das kaum glauben und bin froh, Literaturhinweise zu bekommen.$L_n$

Ein freundlicher Rezensent hat mir eine Arbeit geschickt, die genau die gleiche untere Schranke beweist wie ich. Das Papier ist

K. Ellul, B. Krawetz, J. Shallit, M.-W. Wang, Reguläre Ausdrücke: neue Ergebnisse und offene Probleme , J. Autom. Lang. Kamm.10 (2005), 407–432.

Das Ergebnis ist Satz 30 in der Arbeit.