Complexité de l'intersection des langues régulières en tant que grammaires hors contexte

Étant donné les expressions régulières , existe-t-il des limites non triviales à la taille de la plus petite grammaire sans contexte pour R 1 ∩ ⋯ ∩ R n ?$R_1, \dots, R_n$$R_1 \cap \cdots \cap R_n$

C'est une grande question et elle relève vraiment de mes intérêts. Je suis content que tu lui aies demandé Max.

Soit DFA avec au plus O ( n ) états chacun. Ce serait bien s'il existait un PDA avec de nombreux états sous-exponentiels qui accepte l'intersection des langues du DFA. Cependant, je suggère qu'un tel PDA pourrait ne pas toujours exister.$n$$O(n)$

Considérez la langue de copie. Maintenant, limitez-le à copier des chaînes de longueur n.

Formellement, considérons copie : = { x $n$$:=$ .$\{ xx \, | \, x \in \{0,1\}^{n}\}$

Nous pouvons représenter copie comme l'intersection de n DFA de taille au plus O ( n ) . Cependant, le plus petit DFA qui accepte n- copie a 2 états Ω ( n ) .$n$$n$$O(n)$$n$$2^{\Omega(n)}$

De même, si nous nous limitons à un alphabet de pile binaire, alors je soupçonne que le plus petit PDA qui accepte copie a exponentiellement de nombreux états.$n$

PS N'hésitez pas à m'envoyer un e-mail si vous souhaitez en discuter davantage. :)

Je ne pense pas qu'il puisse y avoir de limites inférieures ou supérieures non triviales.
Pour les bornes inférieures, considérons le langage pour un k fixe . La taille de la plus petite grammaire sans contexte est logarithmique dans la taille de l' expression régulière de L 1 , tandis que la taille du plus petit automate pour L 1 est linéaire dans la taille de l' expression régulière de L 1 . Cette différence exponentielle reste la même si nous croisons L 1 avec d'autres langages de ce type. Pour les bornes supérieures, considérons un langage L 2 qui se compose exactement d'un$L_1 = \{ a^{2^k} \}$$k$$L_1$$L_1$$L_1$$L_1$
$L_2$deBruijn-Séquence de longueur . On sait que la taille d'une plus petite grammaire pour L 2 est le pire des cas, c'est-à-dire O ( $n$$L_2$, donc la différence avec le "plus petit" automate pourL2est simplement un facteur logarithmique, proposition 1 dans$O\left( \frac{n}{\log n} \right)$$L_2$

• D. Hucke, M. Lohrey, E. Noeth Constructing Small Tree Grammars and Small Circuits for Formulas , à paraître dans FSTTCS 2014

Une borne inférieure ou supérieure générale non triviale contredirait ces résultats, car ce qui est vrai pour l'intersection de langues doit l'être pour l'intersection de 1 langue.$n$$1$

Permettez-moi d'appuyer le jugement de Michael, c'est en effet une question intéressante. L'idée principale de Michael peut être combinée avec un résultat de la littérature, fournissant ainsi une borne inférieure similaire avec une preuve rigoureuse.

$n$$k$

$2^{k+1}$$2^k+1$$s$$O(s^2)$$O(4^{k})$

$2^{\Omega(\sqrt{k}/\log k)}$

$L_n = \{\,ww^Rw \in \{a,b\}^*\mid |w|=n\,\}$$w^R$$w$$L_n$$2n+1$

• $r_i = (a+b)^ia(a+b)^{2(n-i-1)}a(a+b)^*+(a+b)^ib(a+b)^{2(n-i-1)}b(a+b)^*$$1\le i \le n$
• $s_i = (a+b)^*a(a+b)^{2(n-i-1)}a(a+b)^i+(a+b)^*b(a+b)^{2(n-i-1)}b(a+b)^i$$1\le i \le n$
• $\ell = (a+b)^{3n}$

$k$$O(n^2)$

$L_n$$2^n/(2n) = 2^{\Omega(\sqrt{k}/\log k)}$$2$$n$$n^n/(2n)$

$O(4^n)$

Les références:

• V. Arvind, Pushkar S. Joglekar, Srikanth Srinivasan. Circuits arithmétiques et produit Hadamard des polynômes , FSTTCS 2009, vol. 4 des LIPIcs, pp. 25-36

• Lange, Martin; Leiß, Hans (2009). " Vers CNF ou pas vers CNF? Une version efficace mais présentable de l'algorithme CYK ". Informatica Didactica 8.