Complexidade da interseção de linguagens regulares como gramáticas sem contexto

Dadas as expressões regulares , existem limites não triviais no tamanho da menor gramática livre de contexto para ?R 1 ∩ ⋯ ∩ R $R_1, \dots, R_n$$R_1 \cap \cdots \cap R_n$

Essa é uma ótima pergunta e realmente está dentro dos meus interesses. Fico feliz que você pediu Max.

Seja DFA com no máximo O ( n ) estados cada um. Seria bom se existisse um PDA com subexponencialmente muitos estados que aceitassem a interseção dos idiomas do DFA. No entanto, sugiro que esse PDA nem sempre exista.$n$$O(n)$

Considere o idioma da cópia. Agora, restrinja-o a copiar cadeias de comprimento n.

Formalmente, considere -copy : = { x $n$$:=$ .$\{ xx \, | \, x \in \{0,1\}^{n}\}$

Podemos representar -copy como a interseção de n DFA do de tamanho no máximo O ( n ) . No entanto, o menor DFA que aceita n -copy possui 2 Ω ( n ) estados.$n$$n$$O(n)$$n$$2^{\Omega(n)}$

Da mesma forma, se nos restringirmos a um alfabeto de pilha binária, suspeito que o menor PDA que aceita -copy exponencialmente tenha muitos estados.$n$

PS Sinta-se livre para me enviar um e-mail se você gostaria de discutir mais. :)

Não acho que possa haver limites inferiores ou superiores não triviais.
Para limites inferiores, considere o idioma para um k fixo . O tamanho da menor gramática livre de contexto é logarítmica no tamanho de L 1 de expressão regular, ao passo que o tamanho da menor autómato para L 1 é linear no intervalo de tamanho de L 1 de expressão regular. Essa diferença exponencial permanece a mesma se cruzarmos L 1 com outros idiomas. Para limites superiores, considere um idioma L 2 que consiste em exatamente um$L_1 = \{ a^{2^k} \}$$k$$L_1$$L_1$$L_1$$L_1$
$L_2$deBruijn-Sequence of length . Sabe-se que o tamanho de uma gramática menor para L 2 é o pior caso, ou seja, O ( $n$$L_2$, então a diferença para o menor autômato paraL2é simplesmente um fator logarítmico, a proposição 1 em$O\left( \frac{n}{\log n} \right)$$L_2$

• D. Hucke, M. Lohrey, E. Noeth Construindo gramáticas de pequenas árvores e pequenos circuitos para fórmulas , a aparecer no FSTTCS 2014

Um limite inferior ou superior geral não trivial contraria esses resultados, pois o que é verdadeiro para a interseção de idiomas deve ser verdadeiro para a interseção de 1 idioma.$n$$1$

Deixe-me segundo o julgamento de Michael, esta é realmente uma pergunta interessante. A idéia principal de Michael pode ser combinada com um resultado da literatura, fornecendo assim um limite inferior semelhante com uma prova rigorosa.

Vou me referir aos limites do tamanho do CFG em termos do número total de símbolos alfabéticos nas expressões regulares. Seja esse número indicado por k . (Como observou john_leo, não encontraremos limites úteis em termos do número de expressões regulares que participam da interseção.)$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)$

Referências:

• V. Arvind, Pushkar S.Joglekar, Srikanth Srinivasan. Circuitos aritméticos e o produto Hadamard de polinômios , FSTTCS 2009, vol. 4 de LIPIcs, pp. 25-36

• Martin Lange; Leiß, Hans (2009). " Para CNF ou não para CNF? Uma versão eficiente e apresentável do algoritmo CYK ". Informatica Didactica 8.