Limites mais baixos no tamanho dos CFGs para idiomas finitos específicos

Considere a seguinte pergunta natural: Dada uma linguagem finita , qual é a menor gramática livre de contexto que gera L ?$L$$L$

Nós podemos fazer a pergunta mais interessante, especificando uma sequência de línguas , por exemplo L n é o conjunto de todas as permutações de { 1 , ... , n } : intuitivamente, um CFG para L n seria "necessidade" de ter tamanho Ω ( n ! ) . Portanto, estamos interessados ​​no tamanho assintótico dos menores CFGs para os idiomas.$L_n$$L_n$$\{1,\ldots,n\}$$L_n$$\Omega(n!)$

Perguntas semelhantes foram tratadas em vários artigos:

• Charikar et al. ("Aproximando a menor gramática: complexidade de Kolmogorov em modelos naturais") considere o quão difícil é aproximar o tamanho do menor CFG que gera uma determinada palavra .
• Mais trabalho nessa direção é Arpe e Reischuk, "Sobre a complexidade da compressão ótima baseada em gramática".
• Peter Asveld tem vários artigos sobre o assunto (por exemplo, "Gerando todas as permutações por gramáticas livres de contexto na forma normal de Chomsky"). Ele está tentando otimizar alguns parâmetros em tipos específicos de gramática, gerando o conjunto de todas as permutações, especificamente as formas normais de Chomsky e Greibach.

No entanto, até agora não consegui encontrar nenhum documento tentando provar um limite de No tamanho de um CFG que gera L n .$\Omega(n!)$$L_n$

Existem documentos que fornecem limites inferiores para o tamanho de gramáticas sem contexto para linguagens finitas específicas?

Em resposta a várias perguntas neste site, bem como no math.stackexchange, criei um método simples capaz de provar limites exponenciais inferiores nos CFGs para idiomas específicos, por exemplo, . Esses resultados são novos? Acho isso difícil de acreditar e ficarei feliz em receber alguma indicação da literatura.$L_n$

Um revisor gentil me enviou um artigo que prova exatamente o mesmo limite inferior que eu, exatamente da mesma maneira. O papel é

K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, Expressões regulares: novos resultados e problemas em aberto , J. Autom. Lang. Pente. 10 (2005), 407-432.

O resultado é o Teorema 30 no artigo.