Limites inférieures de la taille des CFG pour des langues finies spécifiques

14

Considérons la question naturelle suivante: étant donné un langage fini , quelle est la plus petite grammaire sans contexte générant ?LL

Nous pouvons rendre la question plus intéressante en spécifiant une séquence de langues , par exemple est l'ensemble de toutes les permutations de : intuitivement, un CFG pour aurait "besoin" d'avoir la taille . Nous nous intéressons donc à la taille asymptotique des plus petits CFG pour les langues.LnLn{1,,n}LnΩ(n!)

Des questions similaires ont été traitées dans plusieurs articles:

  • Charikar et al. ("Approximation de la plus petite grammaire: complexité de Kolmogorov dans les modèles naturels"), examinez la difficulté d'approximer la taille du plus petit CFG générant un mot donné .
  • Plus de travaux dans ce sens sont Arpe et Reischuk, "Sur la complexité de la compression optimale basée sur la grammaire".
  • Peter Asveld a plusieurs articles sur le sujet (par exemple "Génération de toutes les permutations par des grammaires sans contexte sous forme normale de Chomsky"). Il essaie d'optimiser certains paramètres sur des types de grammaires spécifiques générant l'ensemble de toutes les permutations, en particulier les formes normales de Chomsky et Greibach.

Ω(n!)Ln

Existe-t-il des articles fournissant des limites inférieures pour la taille des grammaires hors contexte pour des langues finies spécifiques?

Ln

Yuval Filmus
la source
(commentaire précédent réf à la question supprimée supprimée). formulé ce problème de compression de telle sorte qu'il pourrait être très pertinent ou utile pour prouver les limites inférieures par rapport à la compression cfg éventuellement via des techniques de diagonalisation & (peut-être aussi lié à la complexité de kolmogorov).
vzn
Voir la question connexe cstheory.stackexchange.com/q/4962
András Salamon

Réponses:

11

Un bon critique m'a envoyé un article qui prouve exactement la même limite inférieure que moi, exactement de la même manière. Le papier est

K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, Expressions régulières: nouveaux résultats et problèmes ouverts , J. Autom. Lang. Peigne. 10 (2005), 407–432.

Le résultat est le théorème 30 dans l'article.

Yuval Filmus
la source
Une préimpression de l'article est disponible sur cs.uwaterloo.ca/~shallit/Papers/re3.pdf
András Salamon du