Limite inferior para NFA aceitando idioma de 3 letras

Relacionado a uma pergunta recente ( limites no tamanho do menor NFA para L_k-distinct ) Noam Nisan solicitou um método para fornecer um limite inferior melhor para o tamanho de um NFA do que o obtido nos limites da complexidade da comunicação. O que se segue é uma versão especial desse problema.

Suponha que seja um idioma sobre algum alfabeto de letras cujas palavras tenham comprimento . Indique o tamanho do menor NFA que aceita por . Defina uma matriz como se e, caso contrário, . Indique o número mínimo de sub-matrizes (submatriz que contém apenas ) cobrindo todos os na matriz por . (So é a complexidade de comunicação não determinística de$L$$n$$3$$L$$NFA(L)$$n\times n^2$$M$$M(a;bc)=1$$abc\in L$$0$$1$$1$$1$$M$$COV(M)$$\log(COV(M))$$M$.) É fácil ver que . Se definirmos de maneira semelhante uma matriz como N ( a b ; c ) = 1 se a b c ∈ L e, caso contrário , 0 , também teremos N F A ( L ) ≥ C O V ( N ) .$NFA(L)\ge COV(M)$$N$$N(ab;c)=1$$abc\in L$$0$$NFA(L)\ge COV(N)$

Existe um $L$ para o qual $NFA(L)>COV(M)+COV(N)?$

Por que função de $COV(M)$ e $COV(N)$ podemos ligar o limite superior $NFA(L)?$

Os limites ...

Nós temos, de facto, N F A ( L ) ≥ C O v ( M ) + C O v ( N ) , ver Teorema 4 em (Gruber & Holzer 2006). Para um limite superior, temos 2 C o v ( M ) + C o v ( N ) ≥ D F A ( L ) ≥ N F A ( L ) , consulte o Teorema 11 no mesmo artigo. $NFA(L) \ge Cov(M) + Cov(N)$$2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$

... não pode ser substancialmente melhorado

Pode haver uma diferença subexponencial entre C o v ( M ) + C o v ( N ) e N F A ( L ) . O exemplo a seguir, e a prova da lacuna, é uma adaptação de um exemplo semelhante que ilustra as limitações dos protocolos de duas partes para provar limites mais baixos na complexidade do estado não determinístico de (Hromkovič et al. 2009):$Cov(M)+Cov(N)$$NFA(L)$

Nós usamos o alfabeto [ n ] = {1 , 2 , … , n} . Seja L = $[n]= \{\,1,2,\ldots,n\,\}$x y z ∈ [ n ] 3 ∣ x = y ∨ x ≠ z} .$L=\{\,xyz\in [n]^3 \mid x=y \vee x\neq z \,\}$

Primeiro cuidamos de C o v ( M ) . Observe que, se w = x y z com y = z , então w ∈ G : no caso de x = y , w ∈ L e no caso de x ≠ y , temos também x ≠ z e, assim, w ∈ L . Além disso, se w tiver a forma x y z com y ≠ z , então$Cov(M)$$w=xyz$$y=z$$w \in L$$x=y$$w\in L$$x\neq y$$x\neq z$$w\in L$$w$$xyz$$y\neq z$w ∈ L sse x ≠ z . Então, podemos escrever L = L ′ ∪ L ″ , come.$w\in L$$x\neq z$$L = L'\cup L''$L ′ = { x y z ∈ [ n ] 3 ∣ y = z } L ″ = $L'=\{xyz\in [n]^3 \mid y=z\}$$L''=\{\,xyz\in [n]^3 \mid y\neq z \wedge x \neq z \,\}$

Agora considere os gráficos bipartidos com , , , bem como com , , e . Em seguida, uma cobertura de borda biclique para o gráfico dá origem a uma cobertura de com submatrizes monocromáticas,G ′ = ( U ′ , V ′ , E ′ ) U ′ = [ n ] V ′ = { y z ∈ [ n ] 2 ∣ y = z } E ′ = U ′ × V ′ G ″ = ( U ″ , V ″ , E ″ ) U ″ = [ $G' = (U',V',E')$$U'=[n]$$V'= \{yz \in [n]^2 \mid y=z\}$$E' = U' \times V'$$G'' = (U'',V'',E'')$] V ″ = { y z ∈ [ n ] 2 ∣ y ≠ z } E ″ = { ( x , y z ) ∣ x ≠ z } G = ( U ′ ∪ U ″ , V ′ ∪ V ″ , E ′ ∪ E ″ ) G M $U''=[n]$$V''= \{ yz \in [n]^2 \mid y\neq z\}$$E'' = \{(x,yz) \mid x\neq z\}$$G = (U' \cup U'',V' \cup V'', E'\cup E'')$$G$$M$$1$

Um truque simples de kernelização para calcular uma cobertura de borda biclique para é colocar os vértices gêmeos de em classes de equivalência. Em seguida, fazemos o mesmo no gráfico resultante para os vértices gêmeos de . Vértices duplos são aqueles com vizinhança idêntica. Esta etapa não altera o número mínimo de bicliques necessárias para cobrir todas as arestas no respectivo gráfico.G ′ U ′ V $G'$$U'$$V'$

A etapa de kernelização comporta em um gráfico com dois vértices e uma única aresta. Assim, as arestas de podem ser cobertas com um único biclique. A aplicação da etapa de kernelização a produz um gráfico de coroa em vértices, cuja dimensão bipartida (o número mínimo de capa de aresta biclique) é conhecida como , em que é a função inversa do coeficiente binomial médio ( De Caen et al., 1981). Observe que . Assim, a dimensão bipartida de é , que é idêntica a .G ′ G ′ G ″ 2 n σ ( n ) σ σ ( n ) = O ( log n ) G 1 + σ ( n ) C o v ( M $G'$$G'$$G''$$2n$$\sigma(n)$$\sigma$$\sigma(n)=O(\log n)$$G$$1+\sigma(n)$$Cov(M)$

Agora considere . Observe que, se com , então . Se , então iff . Então, podemos escrever com e . Quase o mesmo argumento acima fornece .C O v ( N ) w = x y z x = y w ∈ L x ≠ y x ∈ L x ≠ z L = L ‴ ∪ L ⁗ L ‴ = { x y z ∈ [ n ] 3 | x = y } L ⁗ = { x y z ∈ [ n $Cov(N)$$w=xyz$$x=y$$w \in L$$x\neq y$$x\in L$$x\neq z$$L = L''' \cup L''''$$L'''=\{xyz\in [n]^3 \mid x=y\}$3 ∣ x ≠ y ∧ x ≠ z } C o v ( N ) = 1 + σ ( n $L''''= \{xyz\in [n]^3 \mid x\neq y \wedge x\neq z\}$$Cov(N)=1+\sigma(n)$

Mantém-se a dar um limite inferior para a complexidade estado não-determinístico de . Observe que contém todas as palavras do formato com . Para cada palavra corrigir um cálculo aceitar de um mínimo NFA aceitando . Deixe denotar o estado atingido após a leitura do prefixo e deixe denotar o estado atingido após a leitura do prefixo da palavra de entrada . Todos os pares devem ser diferentes. Por uma questão de contradição, assuma por algunsG G x x x x ∈ [ N ] x x x L p x x q x x x x x x ( p x , q x ) ( p x , q x ) = ( p y , q y ) x ≠ y x y x p x = q x x q y$L$$L$$xxx$$x\in[n]$$xxx$$L$$p_x$$x$$q_x$$xx$$xxx$$(p_x,q_x)$$(p_x,q_x)=(p_y,q_y)$$x\neq y$. Em seguida, podemos construir um cálculo na entrada , de modo que o NFA esteja no estado após a leitura do prefixo , e no estado após a leitura do prefixo . Mas a corda não está em . Para o conjunto de estados do NFA, isso mostra que . Assim, para grande , obtemos uma separação subexponencial entre e(a complexidade do estado não determinístico de ).$xyx$$p_x=q_x$$x$q x x y x y x L Q | Q | 2 ≥ n n C o v ( M ) + C o v ( N ) | Q | $q_y=q_x$$xy$$xyx$$L$$Q$$|Q|^2 \ge n$$n$$Cov(M)+Cov(N)$$|Q|$$L$

Referências

• Dominique de Caen, David A. Gregory, Norman J. Pullman: A classificação booleana de matrizes zero-um, em: Cadogan, Charles C. (ed.), 3ª Conferência do Caribe em Combinatória e Computação, Departamento de Matemática, Universidade do Índias Ocidentais, pp. 169–173 (1981)

• Hermann Gruber e Markus Holzer. Encontrar limites mais baixos para a complexidade do estado não determinístico é difícil . Relatório TR06-027, Colóquio Eletrônico sobre Complexidade Computacional (ECCC), março de 2006. Versão curta apareceu em: Oscar H. Ibarra e Zhe Dang, editores, 10ª Conferência Internacional sobre Desenvolvimentos em Teoria da Linguagem (DLT 2006), Santa Barbara (CA) , EUA, volume 4036 de LNCS, páginas 363-374. Springer, junho de 2006.

• Juraj Hromkovic, Holger Petersen, Georg Schnitger: Nos limites da técnica de complexidade da comunicação para provar limites mais baixos no tamanho mínimo de NFAs . Theor. Comput. Sci. 410 (30-32): 2972-2981 (2009)