Intersección DFA en espacio subcuadratico?

25

La intersección de dos (mínimos) DFA con n estados se puede calcular utilizando O (n ² ) tiempo y espacio. Esto es óptimo en general, ya que el DFA resultante (mínimo) puede tener n ² estados. Sin embargo, si el DFA mínimo resultante tiene estados z, donde z = O (n), ¿se puede calcular en el espacio n ^2-eps , para algunos eps constantes> 0? Me interesaría tal resultado incluso para el caso especial donde los DFA de entrada son acíclicos.

automata-theory dfa Rasmus Pagh
fuente

3

Um ... si dos DFA de estado n son acíclicos, entonces cada uno simplemente acepta un conjunto finito de palabras de longitud como máximo n, en cuyo caso su intersección es solo la intersección de los dos gráficos de transición etiquetados, que tendrán n estados y se puede calcular en tiempo y espacio lineales. ¿O me estoy perdiendo algo?

Joshua Grochow

44

Sí, los DFA acíclicos aceptan solo un conjunto finito de palabras. Pero hay ejemplos de DFA acíclicos cuya intersección tiene un tamaño n ^ 2. Por ejemplo, piense en un DFA que acepte cadenas de la forma AABC (donde ABC son cadenas de longitud k), y uno que acepte cadenas de la forma ABCC.

Rasmus Pagh el

1

retagging: cs.cc es una designación arxiv, por lo que las etiquetas dadas no necesitan el prefijo cs.cc.

Suresh Venkat

15

La respuesta es sí sin ningún requisito sobre el tamaño del autómata. Se puede calcular en el espacio $O(\log^2 n)$ incluso para $k$ DFA donde $k$ es una constante.

Sea ( sean DFA. Se demuestra que, dada , el cálculo de la mínima DFA reconocimiento de puede hacerse en $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$ $i \in [k])$ $k$ $\langle A_1, \ldots, A_k \rangle$ $\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$ espacio. Primero probamos algunos resultados técnicos. $O(\log^2 n)$

Definición 1 : Sea dos estados, entonces iff , $q, r$ $q \equiv r$ $\forall w \in \Sigma^*$ $q . w \in F \Leftrightarrow r . w \in F$

Ahora consideramos el autómata dado por la construcción clásica de productos cartesianos. Deje que y sea estados de . $A$ $q = (q_1, \ldots, q_k)$ $r = (r_1, \ldots, r_k)$ $A$

Lema 1 : Decidir si está en NL. $q \equiv r$

Prueba (boceto): demostramos que probar la desigualdad está en NL y usamos NL = coNL. Adivina una palabra (una letra a la vez) tal que es un estado final y no lo es. Esto se puede lograr calculando en el espacio logarítmico para y usando el hecho de que es final iff $w \in \Sigma^*$ $q . w$ $r . w$ $q_i . w, r_i . w$ $i \in [k]$ $q$ $q_i \in F_i \, \forall i \in [k]$ $q \not\equiv r$ $w$

Lema 2 : Decidir si es (in) accesible está en NL. $q$

Prueba (boceto): Adivina (poli-tamaño) rutas de a ( ). $z_i$ $q_i$ $i \in [k]$

Definición 2 : Considere los estados de en orden lexicográfico. Defina como el primer estado accesible el primer estado accesible después de que no es equivalente a ningún estado anterior. Definimos como el único tal que . $A$ $s(1)$ $s(i)$ $s(i-1)$ $c(q)$ $i$ $q \equiv s(i)$

Lema 3 : se puede calcular en el espacio . $s(i)$ $O(\log^2 n)$

Prueba (boceto): la definición 2 produce un algoritmo. Usamos contadores para iterar sobre los estados. Deje y sea el estado actual. En cada estado, usamos el lema 2 para verificar si es accesible. Si es así, hacemos un bucle en todos los estados anteriores y verificamos si alguno de ellos es equivalente a . Si no hay ninguno, incrementamos y sacamos si . De lo contrario, almacenamos como y continuamos. Como solo almacenamos un número constante de contadores y nuestras pruebas pueden llevarse a cabo en $k$ $j \leftarrow 0$ $q$ $q$ $q$ $j$ $q$ $j = i$ $q$ $s(j)$ $\text{NL} \subseteq \text{DSPACE}(\log^2 n)$ , esto completa la prueba.

Corolario 1 : se puede calcular en el espacio . $c(q)$ $O(\log^2 n)$

Teorema : minimizar puede hacerse en el espacio . $A$ $O(\log^2 n)$

Prueba (boceto): Seaser el mayor tal que se defina (es decir, el número de clases de ). Damos un algoritmo que genera un autómata donde $1 \leq m \leq |Q_0| \cdots |Q_1|$ $i$ $s(i)$ $\equiv$ $A' = (Q', \Sigma, \delta', z', F')$

$Q' = \lbrace s(i) : i \in [m] \rbrace$ ;
$F' = \lbrace q \in Q' : q_i \in F_i \, \forall i \in [k] \rbrace$ ;
$z' = s(c(q))$ donde . $q = (z_0, \ldots, z_k)$

Ahora mostramos cómo calcular . Para cada , calcule y la salida de la transición . Por el lema 3 y el corolario 1, este algoritmo se ejecuta en el espacio . Se puede verificar que es mínimo y . $\delta'$ $i \in [m], a \in \Sigma$ $q \leftarrow s(i) . a$ $\left(s(i), a, s(c(q))\right)$ $O(\log^2 n)$ $A'$ $\text{L}(A') = \text{L}(A)$

Michael Blondin
fuente

3

Buen algoritmo! Aquí hay una forma ligeramente diferente de ver este algoritmo. Su núcleo es que la minimización del estado de cualquier DFA se puede hacer en tiempo polinómico y espacio . Después de eso, es fácil construir algunos DFA que representan la intersección en el espacio logarítmico (por lo tanto, en tiempo polinomial y espacio ), y podemos componer dos funciones computables en tiempo polinomial y espacio (de manera similar a componer dos reducciones de espacio logarítmico), produciendo todo el algoritmo en tiempo polinómico y espacio .

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

Tsuyoshi Ito

2

Acabo de ver esta respuesta ... No veo por qué el algoritmo se ejecuta simultáneamente en polytime y . Sí, , pero no se sabe si , es decir, podemos obtener un algoritmo que se ejecuta en polytime, y podemos obtener otro algoritmo que se ejecuta en el espacio , pero no sé cómo resolver los problemas de en polytime y el espacio con un solo algoritmo.

O (\log^{2} n)

$O(\log^2 n)$

N L \subseteq P \cap D S P A C E [\log^{2} n]

$NL \subseteq P \cap DSPACE[\log^2 n]$

N L \subseteq T I S P [n^{O (1)}, \log^{2} n]

$NL \subseteq TISP[n^{O(1)}, \log^2 n]$

O (\log^{2} n)

$O(\log^2 n)$

N L

$NL$

O (\log^{2} n)

$O(\log^2 n)$

Ryan Williams el

Tienes razón, yo tampoco sé cómo. Publiqué esto hace mucho tiempo, así que no estoy seguro de por qué lo escribí de esta manera, pero quizás quise decir "tiempo polinomial u O (log² n)". Lo editaré porque es engañoso. ¡Gracias!

Michael Blondin

14

Dick Lipton y sus colegas trabajaron recientemente en este problema, y Lipton escribió sobre él aquí:

http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

Parece que hacerlo mejor que O (n ^ 2) está abierto incluso para el caso muy especial de determinar si la intersección DFA define el lenguaje vacío.
El documento presenta consecuencias complejas que resultarían de un algoritmo mejorado que maneja no solo 2 DFA en la intersección, sino también números más grandes.

Andy Drucker
fuente

1

¿Y qué hay de los límites inferiores?

Marcos Villagra

1

Solo para aclarar las preguntas: estoy feliz de pasar O (n ^ 2) tiempo (o tal vez incluso n ^ O (1) tiempo) para mejorar el espacio limitado.

Rasmus Pagh

13

Si recibe k DFA (k es parte de la entrada) y desea saber si su intersección está vacía, este problema es PSPACE-complete en general:

Dexter Kozen: límites más bajos para sistemas de prueba natural FOCS 1977: 254-266

Quizás si estudias cuidadosamente esta prueba (y construcciones similares de Lipton y sus coautores), podrías encontrar algún tipo de espacio en el límite inferior incluso para k fijo.

Ryan Williams
fuente

Gracias por este puntero. Supongo que esto podría conducir a un límite inferior n ^ Omega (1) en el espacio adicional necesario, aparte de la entrada. Pero, ¿podría conducir a un espacio inferior superlineal?

Rasmus Pagh el

1

@ user124864 Dados DFA con estados cada uno, el autómata del producto tendrá estados. Ahora, hay dos trucos que puedes hacer para reducir su tamaño. El primero es que solo tiene en cuenta el componente accesible del gráfico del producto. En segundo lugar, podría minimizar el producto DFA. Al final del día, es difícil averiguar qué idioma reconoce este autómata del producto.

k

$k$

n

$n$

n^{k}

$n^k$

Michael Wehar

1

@ user124864 Incluso tratar de determinar si el producto DFA reconoce un lenguaje no vacío es difícil. Este es el problema de la intersección del no vacío. Por duro, quiero decir que es completo en un sentido fuerte.

X N L

$XNL$

Michael Wehar

1

@ user124864 Si puede resolverlo en menos de tiempo, obtendremos algoritmos más rápidos para problemas completos de PSPACE. No es solucionable en espacio binario no determinista. No se sabe si podemos resolverlo en menos de espacio binario determinista. No se sabe si podemos resolverlo en tiempo polinómico determinista simultáneo y espacio binario para cualquier función (hacerlo mejoraría el teorema de Savitch).

n^{k}

$n^k$

o (1) \cdot k \cdot \log (n)

$o(1) \cdot k \cdot \log(n)$

k^{2} \log^{2} (n)

$k^2 \log^2(n)$

f (k) \cdot \log^{2} (n)

$f(k) \cdot \log^2(n)$

f

$f$

Michael Wehar

1

@ user124864 Nota: tenemos los dos siguientes. (1) Vencer tiempo determinísticamente implica algoritmos deterministas más rápidos para problemas completos de PSPACE y (2) vencer tiempo de manera no determinista implica algoritmos no deterministas más rápidos para problemas completos de PSPACE.

n^{k}

$n^k$

n^{k}

$n^k$

Michael Wehar

7

Dados dos autómatas , aceptan lenguajes finitos (autómatas acíclicos), la complejidad del estado de está en (1) . Este resultado también es válido para los DFA unarios (no necesariamente acíclicos) (2) . Sin embargo, parece estar hablando del espacio requerido para calcular la intersección de dos autómatas. No veo cómo la construcción clásica que usa el producto cartesiano usa el espacio . Todo lo que necesita es un número constante de contadores de tamaño logarítmico. Cuando calcula la función de transición para el nuevo estado , solo tiene que escanear la entrada sin mirar ningún dato generado previamente. $A$ $B$ $L(A) \cap L(B)$ $\Theta(|A| \cdot |B|)$ $O(n^2)$ $(q,r)$

¿Tal vez desea generar el autómata mínimo? Si este es el caso, entonces no tengo idea de si se puede lograr. La complejidad del estado de la intersección para los idiomas finitos no parece alentadora. Sin embargo, los DFA unarios tienen la misma complejidad de estado y creo que se puede lograr con dichos autómatas. Al usar los resultados de (2) , puede obtener el tamaño exacto del autómata que reconoce la intersección. Este tamaño se describe por la longitud de la cola y el ciclo, por lo tanto, la función de transición se puede calcular fácilmente con muy poco espacio, ya que la estructura se describe completamente por esos dos tamaños. Entonces, todo lo que tiene que hacer es generar el conjunto de estados finales. Sea el número de estados en el autómata resultante, luego para todos , estado $n$ $1 \leq i \leq n$ $i$ es un estado final si y sólo si es aceptada por ambos y . Esta prueba se puede realizar con poco espacio. $a^i$ $A$ $B$

Michael Blondin
fuente

1

Sí, estoy interesado en el autómata mínimo, o al menos un autómata de tamaño similar. Gracias por los consejos a los DFA unarios. Sin embargo, esto no parece ayudar mucho para el caso general.

Rasmus Pagh el

Intersección DFA en espacio subcuadratico?

Respuestas: