Existe-t-il une opération de division bien définie sur les automates finis?

Contexte:

Étant donné deux automates finis déterministes A et B, nous formons le produit C en laissant les états dans C être le produit cartésien des états dans A et des états dans B. Ensuite, nous choisissons les transitions, l'état initial et les états finaux de sorte que le langage accepté par C est l'intersection des langages pour A et B.

Des questions:

(1) Peut-on "diviser" C par B pour trouver A? A est-il même unique, jusqu'à l'isomorphisme? Nous nous soucions des diagrammes d'état, pas des langues ici et ci-dessous. Ainsi, nous ne permettons pas de compresser les diagrammes d'états pour réduire le nombre d'états.

(2) Si A est unique, existe-t-il un algorithme efficace pour le trouver?

(3) Est-ce que chaque automate fini déterministe a une factorisation unique en "nombres premiers". Un nombre premier signifie ici un automate qui ne peut pas être factorisé, c'est-à-dire écrit comme un produit de 2 automates plus petits.

Travailler avec @MichaelWehar

fl.formal-languages automata-theory dfa Whosyourjay
la source

La décomposition classique est la théorie de Krohn-Rhodes - beaucoup à regarder.

Considérez les dérivés de Brzozowski. en.wikipedia.org/wiki/Brzozowski_derivative

Vijay D

@halfTrucker La théorie de Krohn-Rhodes traite du produit de la couronne. L'OP pose des questions sur le produit cartésien.

scaaahu

Merci @halfTrucker, c'est vraiment intéressant! Comme le dit scaaahu, je recherche un produit cartésien, mais votre référence est toujours excellente.

Whosyourjay

Réponses:

Jetez un œil à cet article du MFCS 2013 , qui étudie la compositionnalité dans les automates. Peut-être que cela vous aidera.

Shaull
la source

+1 pour le lien. Citant la discussion de l'article, Bien que le cas général soit toujours ouvert , il semble que l'article explore uniquement le cas des automates de permutation. Y a-t-il des développements plus récents pour les cas généraux? Je veux dire dans le sens de produit cartésien? (La théorie de Krohn-Rhodes traite du produit de la couronne) Merci.

scaaahu

Je ne connais aucun développement récent. Je peux vous dire qu'il n'y a pas eu de suivi direct de ce document. Mais cela peut indiquer que le problème n'est en effet pas facile.

Shaull

Donnons un moyen évident de récupérer un "facteur" de l'automate produit. Si et désigne l'automate produit, alors si nous définissons c'est-à-dire juste oublier $\mathcal A_i = (Q_i, \delta_i, q_{0i}, F_i), i = 1,2$ $\mathcal A = \mathcal A_1 \times \mathcal A_2$

π_{1} ((q, q^{'})) : = q

$\pi_1( (q, q') ) := q$

A_{2}

$\mathcal A_2$ , ou projetant sur la deuxième composante, nous avons

, également si nous voulons savoir

choisir

et calculer dans l'automate produit

Q_{1} = π (Q_{1} \times Q_{2})

$Q_1 = \pi(Q_1\times Q_2)$

δ_{1} (q, x)

$\delta_1(q,x)$

q^{'} \in Q_{2}

$q' \in Q_2$

, on peut donc aussi récupérer la transition en

π ((δ_{1} (q, x), δ_{2} (q^{'}, x)) = δ_{1} (q, x)

$\pi((\delta_1(q,x), \delta_2(q', x)) = \delta_1(q,x)$

A_{1}

$\mathcal A_1$ .

Donc, si nous savons qu'un automate est un automate produit cartésien (ou externe), nous pouvons récupérer les facteurs facilement.

Mais je suppose que ce n'est pas ce que vous avez en tête concernant vos autres questions. Deux questions se posent ici (dans ce qui suit par isomorphisme d'automate, je veux dire isomorphe comme graphe d'état, c'est-à-dire sans égard aux états initial ou final, comme vous l'avez dit, le langage n'est pas tellement une préoccupation ici):

1) Étant donné un automate isomorphe à un automate produit (c'est-à-dire pouvant être décomposé d'une manière ou d'une autre) d'un nombre fini d'automates, cette décomposition est-elle essentiellement unique? (étant donné que les facteurs ne pouvaient pas être décomposés davantage, car sinon, évidemment pas). Plus précisément si pour les automates indécomposables cela implique et

{UNE}_{1} \times \dots \times {UNE}_{k} ≅ B_{1} \times \dots \times B_{l}

$\mathcal A_1 \times \ldots \times \mathcal A_k \cong \mathcal B_1 \times \ldots \times \mathcal B_l$

A_{i}, B_{j}

$\mathcal A_i, \mathcal B_j$

k = l

$k = l$

A_{i} ≅ B_{π (i)}

$\mathcal A_i \cong \mathcal B_{\pi(i)}$ pour une réorganisation

. Je suppose que c'est vrai, mais je n'ai pas encore de preuve.

π : {1, \dots k} \to {1, \dots k}

$\pi : \{1,\ldots k \}\to \{1,\ldots k \}$

2) Étant donné deux automates , existe-t-il un troisième automate tel que $\mathcal A, \mathcal B$ $\mathcal C$ $\mathcal A = \mathcal B \times \mathcal C$ .

Il est facile de dériver les conditions nécessaires pour que cela soit le cas, mais je ne vois pas de critères suffisants et faciles pour qu'un automate soit un facteur pour un autre.

π_{1} ((δ_{1} (q, X), δ_{2} (q^{'}, X)) = δ_{1} (q, X) = δ_{1} (π_{1} (q, q^{'}), X)

$\pi_1( (\delta_1(q, x), \delta_2(q', x)) = \delta_1(q,x) = \delta_1(\pi_1(q,q'), x)$

q \in Q_{1}, q^{'} \in Q_{2}

$q \in Q_1, q' \in Q_2$

π

$\pi$

A_{1} \times A_{2}

$\mathcal A_1 \times \mathcal A_2$

A_{2}

$\mathcal A_2$

$\mathcal A$ $\mathcal B$ $\mathcal B$ $\mathcal A$

$\mathcal B$ $\mathcal A$ .

$M$ $N$ $M$ $N$ . Et cette notion est largement utilisée, et compte tenu de la relation entre le DEA et les monoïdes finis étroitement liés à votre question sur la décomposition des automates. Si vous souhaitez en savoir plus, consultez ces ressources:

H. Straubing, P. Weil Une introduction aux automates finis et leur connexion à la logique,

Site Web du cours avec beaucoup d'informations.

Remarque : Il existe également une autre notion de " quotienting ", voir wikipedia: automate de quotient , mais ce n'est qu'une règle pour réduire les états et utilisée dans les algorithmes d'apprentissage / inférence de langage ou de minimisation d'état.

StefanH
la source