¿Existe una operación de división bien definida en autómatas finitos?

15

Antecedentes:

Dados dos autómatas finitos deterministas A y B, formamos el producto C dejando que los estados en C sean el producto cartesiano de los estados en A y los estados en B. Luego, elegimos las transiciones, el estado inicial y los estados finales para que el lenguaje sea aceptado por C es la intersección de los idiomas para A y B.

Preguntas:

(1) ¿Podemos "dividir" C por B para encontrar A? ¿Es A incluso único, hasta el isomorfismo? Nos interesan los diagramas de estado, no los idiomas aquí y abajo. Por lo tanto, no permitimos comprimir los diagramas de estado para reducir el número de estados.

(2) Si A es único, ¿existe un algoritmo eficiente para encontrarlo?

(3) ¿Cada autómata finito determinista tiene una factorización única en "números primos"? Una prima aquí significa un autómata que no se puede factorizar, es decir, escrito como un producto de 2 autómatas más pequeños.

  • Trabaja con @MichaelWehar
Whosyourjay
fuente
55
La descomposición clásica es la teoría de Krohn-Rhodes, mucho que ver.
2
Considere derivados de Brzozowski. en.wikipedia.org/wiki/Brzozowski_derivative
Vijay D
2
@halfTrucker La teoría de Krohn-Rhodes se ocupa del producto de la corona. El OP pregunta por el producto cartesiano.
scaaahu
2
Gracias @halfTrucker, ¡esto es realmente interesante! Como dice scaaahu, estoy buscando un producto cartesiano, pero su referencia sigue siendo excelente.
Whosyourjay

Respuestas:

8

Eche un vistazo a este documento MFCS 2013 , que estudia la composicionalidad en autómatas. Quizás te sirva de ayuda.

Shaull
fuente
2
+1 para el enlace. Citando la discusión del artículo, aunque el caso general aún está abierto , parece que el artículo solo explora el caso de permutación de autómatas. ¿Hay algún desarrollo más reciente para casos generales? Me refiero en el sentido de producto cartesiano? (La teoría de Krohn-Rhodes se ocupa del producto de la corona) Gracias.
scaaahu
3
No conozco ningún desarrollo reciente. Puedo decirle que no hubo trabajo de seguimiento directo a este documento. Pero esto puede servir como una indicación de que el problema no es fácil.
Shaull
4

Vamos a dar una forma obvia de recuperar un "factor" del autómata del producto. Si y A = A 1 × A 2 denota el autómata del producto, entonces si definimos π 1 ( ( q , q ) ) : = q es decir, simplemente falsificando acerca de A 2UNyo=(Qyo,δyo,q0 0yo,Fyo),yo=1,2UN=UN1×UN2

π1((q,q)): =q
UN2, o proyectando en el segundo componente, tenemos , también si queremos saber δ 1 ( q , x ) escogemos q Q 2 y calculamos en el autómata del producto π ( ( δ 1 ( q , x ) , δ 2 ( q , x ) ) = δ 1 ( qQ1=π(Q1×Q2)δ1(q,X)qQ2 , por lo tanto, también podemos recuperar la transición en A 1 .π((δ1(q,X),δ2(q,X))=δ1(q,X)UN1

Entonces, si sabemos que un autómata es un autómata cartesiano (o externo), podemos recuperar los factores fácilmente.

Pero supongo que esto no es lo que tienes en mente con respecto a tus otras preguntas. Aquí surgen dos preguntas (en lo siguiente, por isomorfismo de autómatas me refiero a isomorfo como gráfico de estado, es decir, sin tener en cuenta los estados iniciales o finales, ya que usted dijo que el lenguaje no es tanto una preocupación aquí):

1) Dado cualquier autómata que sea isomorfo a un autómata de producto (es decir, podría descomponerse de alguna manera) de algún número finito de autómatas, ¿es esta descomposición esencialmente única? (dado que los factores no pueden descomponerse más, porque de lo contrario obviamente no). Más presicely si para indescomponible autómatas A i , B j implica esto k = l y A iB π ( i ) para algunos reordenamiento

UN1×...×UNksi1×...×sil
UNyo,sijk=lUNyosiπ(yo) . Supongo que eso es cierto, pero todavía no tengo pruebas.π:{1,...k}{1,...k}

2) Dado cualquiera de los dos autómatas , ¿existe un tercer autómata C tal que A = B × C ?UN,siCUN=si×C

Es fácil derivar las condiciones necesarias para que ese sea el caso, pero no veo ningún criterio lo suficientemente fácil para que un autómata sea un factor de otro.

π1((δ1(q,X),δ2(q,X))=δ1(q,X)=δ1(π1(q,q),X)
qQ1,qQ2πUN1×UN2UN2

UN sisiUN

siUN

METROnorteMETROnorte

H. Straubing, P. Weil Una introducción a los autómatas finitos y su conexión con la lógica,

Sitio web del curso con mucha información.

Observación : También existe otra noción de " cociente ", consulte wikipedia: autómata de cociente , pero esta es solo una regla para colapsar estados y se utiliza en algoritmos de inferencia de aprendizaje / lenguaje o minimización de estado.

StefanH
fuente