Algoritmo de intersección DFA para casos especiales

9

Estoy interesado en algoritmos eficientes para la intersección de DFA para casos especiales. Es decir, cuando los DFA que se cruzan obedecen una determinada estructura y / o funcionan en un alfabeto limitado. ¿Hay alguna fuente donde pueda encontrar algoritmos en estos casos?

Para no hacer que la pregunta sea demasiado amplia, la siguiente estructura es de particular interés: todos los DFA que se cruzan operan en el alfabeto binario (0 | 1), también pueden usar símbolos de no importa. Además, todos los estados tienen una sola transición, a excepción de a lo sumo K estados especiales, que tienen solo dos transiciones (y estas transiciones son siempre 0 o 1, pero no me importa). K es un entero, menos de 10 para fines prácticos. Además, tienen un solo estado de aceptación. Además, se sabe que la intersección SIEMPRE es un DFA en forma de "tira", es decir, sin ramas como en la siguiente imagen:

ingrese la descripción de la imagen aquí

EDITAR: Quizás la descripción de la restricción en los DFA de entrada no es muy clara. Intentaré mejorarlo en este párrafo. Tiene como entrada T DFA. Cada uno de estos DFA funciona solo en el alfabeto binario. Cada uno de ellos tiene como máximo N estados. Para cada DFA, cada uno de sus estados es uno de los siguientes:

1) el estado de aceptación (es solo uno y no hay transición de él a ningún otro estado)

2) un estado con dos transiciones (0 y 1) al mismo estado objetivo (la mayoría de los estados es de este tipo)

3) un estado con dos transiciones (0 y 1) a diferentes estados objetivo (como máximo K de este tipo)

Se garantiza que solo hay un estado de aceptación y que hay como máximo K estados de tipo (3) en cada entrada de DFA. Asimismo se garantiza que la intersección DFA de todos los DFAs de entrada es una "tira" (como se describe arriba), de tamaño inferior a N .

EDIT2: Algunas restricciones adicionales, según lo solicitado por DW en los comentarios:

  • Los DFA de entrada son DAG.
  • Los DFA de entrada están "nivelados", siguiendo la definición de DW en los comentarios. Es decir, puede asignar diferentes enteros a cada estado de tal manera que cada transición pase de un entero u a un entero v , de modo que u + 1 = v .
  • El número de estados de aceptación para cada entrada de DFA, no exceda de K .

¿Algunas ideas? Gracias.

ale64bit
fuente
¿Cómo exactamente modelas "no me importa"? Parece que los autómatas no son deterministas, en cierto modo.
Shaull
@Shaull ¿Por qué debería hacer que el autómata no sea determinista? Eso puede suceder solo si hay otra transición desde el mismo estado, que se excluye explícitamente.
babou
1
¿Qué es a DFA in form of "strip", i.e., no branches? ¿Tiene alguna razón específica para creer que uno puede hacerlo mejor que el algoritmo estándar en su caso?
babou
1
Hola. Calcular la intersección real sería genial, ya que simplificaría muchas cosas, pero decidir el vacío también sería útil.
ale64bit
1
Acabo de encontrar un nuevo artículo sobre gráficos de intersección , ¿podría ser relevante parte de esta teoría? ¿podría ampliar su aplicación mencionada en su comentario en el chat teórico de informática ? e invitar a otros a continuar más discusiones allí.
vzn

Respuestas:

9

[2]

NC3


[1]{0,1}uvuv

  1. L-completo para un estado final en cada DFA,
  2. NL-complete para dos estados finales en cada DFA, y
  3. NP-complete para tres o más estados finales en cada DFA.

KK=2

Por lo tanto, no , no creo que haya un algoritmo eficiente para su problema.

[3]


x2x3x5

gadget de reducción

Tenga en cuenta que los autómatas son árboles (y, por lo tanto, DAG), están nivelados y tienen tres estados finales. En realidad, los tres estados finales podrían fusionarse en uno solo, si uno está satisfecho con los DAG. Además, solo dos estados tienen dos transiciones salientes (distintas).

  1. Michael Blondin Complexité raffinée du problème d'intersection d'automates, M.Sc. Tesis, Université de Montréal, 2012.
  2. Michael Blondin, Andreas Krebs y Pierre McKenzie. La complejidad de los autómatas finitos de intersección con pocos estados finales, Complejidad computacional (CC), 2014.
  3. Michael Wehar Resultados de dureza para la intersección sin vacío. ICALP, 2014.
Michael Blondin
fuente
2
¡Muchas gracias! Acepto tu respuesta La pregunta se originó en algunas pruebas prácticas en las que todo se redujo después de muchos pasos en la intersección de las soluciones de muchos DFA con estas características particulares. Sin embargo, observamos que aunque al final obtendríamos un DFA simple, el proceso nunca terminó debido a que los DFA intermedios (mientras se cruzaban secuencialmente) estaban creciendo enormemente en un número exponencial de estados. De ahí la pregunta de cómo obtener la respuesta sin pasar por los pasos intermedios "ingenuos".
ale64bit
1
Muchas gracias (y perdón por no estar claro, estoy por debajo de los novatos en esta área). Ahora hay algo que no entiendo. Usted menciona que "en forma de árbol" significa "ruta única desde la raíz a cualquier otro nodo". Pero, por ejemplo, en la imagen que publicó en la edición, ¿eso no sería un árbol (a menos que cuente las transiciones 0/1 como una sola etiqueta)?
ale64bit
1
Tienes razón, pero entiendo que permites transiciones de "no me importa". No es el caso?
Michael Blondin
2
Hola Michael. Gracias por la buena respuesta. Espero que todo esté bien. :)
Michael Wehar
2
@MichaelWehar En caso de que arregles k y c, mencionas que puedes resolver el problema "rápidamente". Pero no mencionas la complejidad del tiempo, solo la complejidad del espacio. ¿Qué significa exactamente "rápidamente" en ese contexto?
ale64bit