Algoritmo de intersección DFA para casos especiales

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:

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.

$[2]$

$\text{NC}^3$$\oplus$

$[1]$$\{0,1\}$$u$$v$$u$$v$

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.

$K$$K=2$

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

$[3]$

$x_2 \lor x_3 \lor x_5$

$\hskip2in$

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.