Algorithme d'intersection DFA pour les cas spéciaux

Je suis intéressé par des algorithmes efficaces pour l'intersection DFA pour des cas spéciaux. A savoir, lorsque les DFA se croisent obéissent à une certaine structure et / ou opèrent sur un alphabet limité. Y a-t-il une source où je peux trouver des algorithmes de tels cas?

Afin de ne pas rendre la question trop large, la structure suivante présente un intérêt particulier: tous les DFA à intersecter fonctionnent dans l'alphabet binaire (0 | 1), ils peuvent également utiliser des symboles indifférents. De plus, tous les états n'ont qu'une seule transition à l'exception d'au plus K états spéciaux, qui n'ont que deux transitions (et ces transitions sont toujours 0 ou 1, mais peu importe). K est un entier inférieur à 10 pour des raisons pratiques. En outre, ils ont un seul État acceptant. De plus, il est connu que l'intersection est TOUJOURS un DFA sous forme de "bande", c'est-à-dire sans branches comme dans l'image suivante:

EDIT: La description de la contrainte sur les DFA d'entrée n'est peut-être pas très claire. Je vais essayer de l'améliorer dans ce paragraphe. Vous avez en entrée T DFA. Chacun de ces DFA fonctionne uniquement sur l'alphabet binaire. Chacun d'eux a au plus N états. Pour chaque DFA, chacun de ses états est l'un des suivants:

1) l'état acceptant (il n'en est qu'un et il n'y a pas de transition de celui-ci vers un autre état)

2) un état avec deux transitions (0 et 1) vers le même état cible (la majorité des états est de ce type)

3) un état avec deux transitions (0 et 1) vers différents états cibles (tout au plus K de ce type)

Il est garanti qu'il n'y a qu'un seul état acceptant et qu'il y a au plus K états de type (3) dans chaque DFA d'entrée. Il est également garanti que l'intersection de tous les DFA DFA d'entrée est une « bande » (comme décrit ci - dessus), de taille inférieure à N .

EDIT2: Quelques contraintes supplémentaires, comme demandé par DW dans les commentaires:

• Les DFA en entrée sont des DAG.
• Les DFA d'entrée sont "nivelés", suivant la définition DW dans les commentaires. A savoir, vous pouvez affecter différents entiers à chaque état de telle manière que chaque transition passe d'un entier u à un entier v , tel que u + 1 = v .
• Le nombre d'états acceptant pour chaque entrée DFA, ne dépasse pas K .

Des idées? Merci.

Oui , il y a des cas de problème d'insertion de non vide DFA qui sont à l'intérieur de P. Ma thèse de maîtrise est consacrée à cette question, mais malheureusement elle est en français. Cependant, la plupart des résultats sont apparus ici dans .$[2]$

Lorsque l'alphabet est unaire, le problème est L-complet lorsque chaque DFA a au plus deux états finaux, et NP-complet sinon. La plupart des autres cas sont des restrictions sur les monoïdes de transition des automates. Par exemple, pour les monoïdes de transition du groupe abélien, le problème est dans lorsque chaque DFA a au plus un état final, et NP-complet sinon; pour les monoïdes de transition élémentaires à 2 groupes, le problème est L-complet lorsque chaque DFA a au plus deux états finaux, et NP-complet sinon.$\text{NC}^3$$\oplus$

Permettez-moi maintenant de répondre à votre question plus précise, qui ne peut être trouvée que dans . Supposons que l'on vous donne des DFA travaillant sur et ayant la forme d'arbres, c'est-à-dire qu'il existe un état (état initial) tel que pour chaque état il existe un chemin unique de à . Ensuite, décider du non vide de l'intersection est:$[1]$$\{0,1\}$$u$$v$$u$$v$

1. L-complet pour un état final dans chaque DFA,
2. NL-complet pour deux états finaux dans chaque DFA, et
3. NP-complet pour trois états finaux ou plus dans chaque DFA.

Les résultats de dureté restent valables même si vous "fourchez" respectivement 0, 1 ou 2 fois (c'est votre ). Maintenant, si vos DFA sont des graphiques acycliques dirigés au lieu d'arbres, alors le problème est NP-complet même avec un état final dans chaque DFA et ; la réduction est assez simple et provient de Monotone 1-in-3 3-SAT.$K$$K=2$

Par conséquent, non , je ne pense pas qu'il existe un algorithme efficace pour votre problème.

Maintenant, si le nombre d'automates est fixe, vous voudrez peut-être discuter avec Michael Wehar qui a récemment publié .$[3]$

EDIT: Depuis OP a édité sa question, permettez-moi de clarifier ma réponse avec ses nouvelles exigences. Considérez le problème NP-complet Monotone 1-en-3 3-SAT où vous obtenez une formule en 3-CNF sans négation, et où vous devez déterminer s'il existe une affectation qui rend exactement une variable vraie dans chaque clause. Vous pouvez réduire ce problème au problème d'intersection de non vide comme suit. Par exemple, pour la clause , vous construisez l'automate suivant:$x_2 \lor x_3 \lor x_5$

$\hskip2in$

Notez que les automates sont des arbres (et donc des DAG), sont nivelés et ont trois états finaux. En fait, les trois états finaux peuvent être fusionnés en un seul, si l'on est satisfait des DAG. De plus, seuls deux États ont deux transitions sortantes (distinctes).

1. Michael Blondin. Complexité raffinée du problème d'intersection d'automates, M.Sc. thèse, Université de Montréal, 2012.
2. Michael Blondin, Andreas Krebs et Pierre McKenzie. The Complexity of Intersecting Finite Automata Have Few Final States, Computational Complexity (CC), 2014.
3. Michael Wehar. Résultats de dureté pour le non-vide d'intersection. ICALP, 2014.