Límite inferior para NFA que acepta lenguaje de 3 letras

8

Relacionado con una pregunta reciente ( Límites en el tamaño del NFA más pequeño para L_k-distinct ) Noam Nisan solicitó un método para proporcionar un límite inferior mejor para el tamaño de un NFA que el que obtenemos de los límites de complejidad de la comunicación. Lo que sigue es una versión especial de ese problema.

Supongamos que es un lenguaje sobre un alfabeto de letras cuyas palabras tienen una longitud de . Denote el tamaño del NFA más pequeño que acepta por . Defina una matriz como si y de lo contrario . Denote el número mínimo de submatrices (submatriz que contiene solo 's) que cubre todos los ' s en la matriz por . (So es la complejidad de comunicación no determinista deL Ln n3 3L LN F A ( L ) NFA(L)n × n 2n×n2 M MM ( a ; b c ) = 1 M(a;bc)=1a b c L abcL0 01 11 11 1M MC O V ( M ) COV(M)log ( C O V ( M ) ) log(COV(M))MM.) Es fácil ver que . Si definimos de manera similar una matriz como si y de lo contrario , entonces también tenemos .N F A ( L ) C O V ( M ) N N ( a b ; c ) = 1 a b c L 0 N F A ( L ) C O V ( N )NFA(L)COV(M)NN(ab;c)=1abcL0NFA(L)COV(N)

¿Hay una para la cualL N F A ( L ) > C O V ( M ) + C O V ( N ) ?LNFA(L)>COV(M)+COV(N)?

¿Con qué función de y podemos límite superiorC O V ( M ) C O V ( N ) N F A ( L ) ?COV(M)COV(N)NFA(L)?

domotorp
fuente

Respuestas:

12

Los límites ...

De hecho, tenemos N F A ( L ) C o v ( M ) + C o v ( N ) , ver Teorema 4 en (Gruber y Holzer 2006). Para un límite superior, tenemos 2 C o v ( M ) + C o v ( N )D F A ( L ) N F A ( L ) , vea el Teorema 11 en el mismo documento. NFA(L)Cov(M)+Cov(N)2Cov(M)+Cov(N)DFA(L)NFA(L)

... no se puede mejorar sustancialmente

Puede haber una brecha subexponencial entre C o v ( M ) + C o v ( N ) y N F A ( L ) . El siguiente ejemplo, y la prueba de la brecha, es una adaptación de un ejemplo similar que ilustra las limitaciones de los protocolos de dos partes para probar límites inferiores en la complejidad del estado no determinista de (Hromkovič et al. 2009):Cov(M)+Cov(N)NFA(L)

Usamos el alfabeto [ n ] = {1 , 2 , ... , n} . Deje L = {[ n ] = {1 , 2 , ... , n}x y z [ n ] 3x = y x z} .L={xyz[n]3x=yxz}

Primero nos ocupamos de C o v ( M ) . Observe que si w = x y z con y = z , entonces w L : en caso de que x = y , w L y en caso de x y , también tenemos x z y por lo tanto w L . Además, si w tiene la forma x y z con y z , entoncesCov(M)w=xyzy=zwLx=ywLxyxzwLwxyzyzw L iff x z . Entonces podemos escribir L = L L , con L = { x y z [ n ] 3y = z } y L = {wLxzL=LL′′L={xyz[n]3y=z}x y z [ n ] 3y z x z} .L′′={xyz[n]3yzxz}

Ahora considere los gráficos bipartitos G = ( U , V , E ) con U = [ n ] , V = { y z [ n ] 2y = z } , E = U × V , Así como G = ( U , V G=(U,V,E)U=[n]V={yz[n]2y=z}E=U×V, E ) con U = [ n ] , V = { y z [ n ] 2y z } , E = { ( x , y z ) x z } , y G = ( U U , V V ,G′′=(U′′,V′′,E′′)U′′=[n]V′′={yz[n]2yz}E′′={(x,yz)xz}E E ) . Luego, unacubierta de borde bicliquepara el gráfico G da lugar a una cubierta de M consubmatrices monocromáticas 1 , y viceversa (Teorema 21 en Gruber y Holzer 2006).G=(UU′′,VV′′,EE′′)GM1

Un simple truco de kernelization para calcular una cubierta de borde biclique para G ' es colocar los vértices gemelos desde U ' en clases de equivalencia. Luego hacemos lo mismo en el gráfico resultante para los vértices gemelos de V ' . Los vértices gemelos son aquellos con vecindad idéntica. Este paso no altera el número mínimo de bicliques necesarios para cubrir todos los bordes en el gráfico respectivo.GUV

El paso de kernelization colapsa G ' en un gráfico con dos vértices y un solo borde. Por lo tanto, los bordes de G ' pueden cubrirse con un solo biclique. Al aplicar el paso de kernelization a G ″ se obtiene un gráfico de corona en 2 n vértices, cuya dimensión bipartita (el número mínimo de cubierta del borde biclique) se sabe que es σ ( n ) , donde σ es la función inversa del coeficiente binomial medio (De Caen et al.1981). Observe que σ ( n ) = O ( log nGGG′′2nσ(n)σ) . Por lo tanto, la dimensión bipartita de G es 1 + σ ( n ) , que es idéntica a C o v ( M ) .σ(n)=O(logn)G1+σ(n)Cov(M)

Ahora considere C o v ( N ) . Observe que si w = x y z con x = y , a continuación, w L . Si x y , entonces x L iff x z . Entonces podemos escribir L = L L con L = { x y z [ n ] 3xCov(N)w=xyzx=ywLxyxLxzL=L′′′L′′′′= y } y L = { x y z [ n ] 3x y x z } . Casi el mismo argumento que el anterior produce C o v ( N ) = 1 + σ ( n ) .L′′′={xyz[n]3x=y}L′′′′={xyz[n]3xyxz}Cov(N)=1+σ(n)

Queda por dar una cota inferior de la complejidad del estado no determinista de L . Observe que L contiene todas las palabras de la forma x x x con x [ n ] . Para cada tal palabra x x x fijar una aceptación de cálculo de un NFA mínimo aceptar L . Supongamos que p x denota el estado alcanzado después de leer el prefijo x , y que q x denota el estado alcanzado después de leer el prefijo x x de la palabra de entrada x x x . Entonces todos los paresLLxxxx[n]xxxLpxxqxxxxxx( p x , q x ) debe ser diferente. En aras de la contradicción, suponga ( p x , q x ) = ( p y , q y ) para algunos x y . Entonces podemos construir un cálculo de aceptación en la entrada x y x , de modo que el NFA esté en estado p x = q x después de leer el prefijo x , y en estado q y = q x(px,qx)(px,qx)=(py,qy)xyxyxpx=qxxdespués de leer el prefijo x y . Pero la cadena x y x no está en L . Para el conjunto de estados Q de la NFA, esto muestra que | Q | 2n . Por lo tanto, para n grande , obtenemos una separación subexponencial entre C o v ( M ) + C o v ( N ) y | Q | (la complejidad del estado no determinista de L ).

Referencias

Hermann Gruber
fuente
1
¡Bien gracias! Ahora te he pagado;)
domotorp