Reste-t-il des problèmes en suspens à propos des DFA?

59

Après avoir étudié les automates à états finis (DFA) déterministes chez les étudiants de premier cycle, j’ai eu le sentiment qu’ils étaient extrêmement bien compris. Ma question est de savoir s'il y a quelque chose que nous ne comprenons toujours pas à leur sujet. Je ne parle pas de généralisations d'AFD, mais des AMD d'origine non modifiées que nous étudions au premier cycle.

C'est une question vague, mais j'espère que vous avez compris l'idée. Je veux comprendre s’il est juste de dire que nous comprenons parfaitement les DFA. Je parle donc vraiment de questions inhérentes aux DFA, et non de problèmes créés artificiellement pour ressembler à un problème de DFA. Permettez-moi de donner un exemple d'un tel problème. Soit L la langue vide si P = NP et une langue fixe non régulière si P n'est pas NP. L peut-il être accepté par un DFA? Cette question concerne les DFA, mais pas leur esprit. J'espère que mon propos est clair et que les gens ne me répondent pas de manière pédante.

En bref est-il juste de dire

Nous comprenons essentiellement complètement les DFA.

Je suis désolé s'il s'avérait qu'il s'agissait d'un vaste domaine de recherche dont je n'étais pas au courant et que je viens d'insulter toute une communauté de personnes.

Oie canadienne
la source
16
Le premier problème qui m'est parvenu est de savoir si la conjecture de Černý est vraie. en.wikipedia.org/wiki/Synchronizing_word et liafa.jussieu.fr/~jep/Problemes/Cerny.html Le billet de blog suivant pourrait également vous intéresser: rjlipton.wordpress.com/2009/08/17/…
Abuzer Yakaryilmaz
1
Est-ce que les problèmes ouverts concernant les NFA et les expressions régulières comptent?
Hsien-Chih Chang 張顯 之
1
@ Hsien-Chih: Soyons aussi restrictifs que possible dans l'interprétation de la question. J'avais supposé qu'il ne restait plus de problèmes en suspens, mais les réponses montrent que ce n'est pas vrai.
Oie canadienne
1
Les DFA et les expressions régulières sont équivalents. Les NFA et les DFA ont un pouvoir d'expression équivalent, bien qu'un NFA puisse compter beaucoup moins d'États que son DFA correspondant.
Chepner
6
@chepner Bien que DFA, NFA et regexen aient un pouvoir expressif équivalent, cela n'indique nullement que tout savoir sur l'un implique de tout savoir sur l'autre. Par exemple, savoir comment minimiser un DFA ne vous dit pas directement comment minimiser un NFA - ce qui est en fait un problème assez difficile !
Daniel Wagner

Réponses:

56

Voici un problème décrit dans le livre "Un deuxième cours sur les langages formels et la théorie des automates" de Shallit.

Soit et v deux mots distincts avec | u | = | v | = n . Quelle est la taille du plus petit DFA qui accepte u mais rejette v , ou vice versa?vousv|vous|=|v|=nvousv

Robson, dans son article intitulé " La séparation des chaînes avec petits automates " en 1989 a prouvé une limite supérieure . La limite inférieure la plus connue en Ω ( log n ) .O(n2/5(bûchen)3/5)Ω(bûchen)

Pour une enquête voir ceci .

Hsien-Chih Chang 之
la source
12
Dans ma récente conférence à la BCTCS 2014 à l'Université de Loughborough, j'offre 100 GBP pour tout progrès non négligeable sur ce problème. Oh, et il y a aussi d'autres problèmes en suspens! Voir cs.uwaterloo.ca/~shallit/Talks/bc4.pdf .
Jeffrey Shallit
1
Je vais accepter cela car c'était le premier, mais ce sont toutes d'excellentes réponses. Merci à tous et continuez!
Oie canadienne
Maintenant sur Wikipedia sous le nom en.wikipedia.org/wiki/Separating_words_problem
David Eppstein
41

Voici un problème de décision très simple à propos de DFA. Étant donné un DFA M, M accepte-t-il la représentation en base 2 d'au moins un nombre premier?

Actuellement, nous ne savons même pas si ce problème peut être résolu de manière récursive.

Si elle peut être résolue de manière récursive et si nous avions un algorithme, nous pourrions résoudre le problème ouvert de longue date, à savoir s'il existe des nombres premiers de Fermat (nombres premiers de la forme ) plus grands que le plus grand connu, 65537. (Parce que tout nombre premier avec une représentation en base 2 de la forme 1 0 + 1 doit être un nombre premier de Fermat.)22n+110+1

Jeffrey Shallit
la source
il y a d'autres conjectures en théorie des nombres qui se rapportent à des périodes de problème Erdos Divergence et tieing certaines formulations dans DFA semble possible dans d' autres cas aussi, un programme de recherche possible pour quelqu'un ...
VZN
Dois-je bien comprendre que si nous avions un algorithme pour ce problème, cela résoudrait aussi le problème de Sierpinski et le problème de Riesel? ( en.wikipedia.org/wiki/Sierpinski_number , en.wikipedia.org/wiki/Riesel_number )
sdcvvc
Oui, sdcvvc, c'est le cas.
Jeffrey Shallit
39

La conjecture de Černý est toujours ouverte et importante. Il est sur le point DFA qui ont un mot de synchronisation (un mot avec la propriété que deux exemplaires de l'automate a commencé dans les différents états finissent toujours dans le même état que l'autre traitement après la fois le mot), et demande si (pour -state automates) la longueur du mot le plus court est toujours au plus ( n - 1 ) 2 . Les meilleures limites prouvées sont de la forme O ( n 3 ) .n(n1)2O(n3)

David Eppstein
la source
Désolé, Abuzer Yakaryilmaz, n'a pas remarqué votre commentaire avant de poster ceci comme réponse. Mais je crois que cela mérite d'être une réponse et pas seulement un commentaire ...
David Eppstein
2
Pas de problème :) Je pense que le deuxième problème en suspens que j'ai lié est également très intéressant.
Abuzer Yakaryilmaz
7
Je sais que cette question est célèbre, mais existe-t-il une explication rapide de son importance? Que ferions - nous savoir si la limite est vraiment plutôt que n 3 / 6 ? (n-1)2n3/6
Sasho Nikolov
@SashoNikolov Il peut être d'un intérêt pratique de pouvoir réinitialiser un système sur un état connu sans avoir à l'observer (un satellite par exemple), en utilisant le moins d'actions possible.
Denis
Oui, j'ai d'abord appris ce problème grâce aux travaux de Natarajan sur la conception de composants de chaînes de montage qui forcent mécaniquement les pièces à être dans certaines orientations géométriques. Séquences de réinitialisation plus courtes (dans un automate représentant des étapes de réorientation potentielles) = lignes d'assemblage plus courtes.
David Eppstein
20

Je tiens à souligner un autre problème de recherche, qui concerne l’interaction de concepts très fondamentaux relatifs aux DFA.

Il est bien connu que tout NFA à n états peut être converti en un DFA équivalent ayant au plus états. C’est ce qui est le mieux possible dans le pire des cas, dans la mesure où il existe des langages normaux de complexité d’états non déterministe n (c’est-à-dire le nombre d’états dans un NFA minimal), mais de complexité d’état déterministe 2 n . Il existe également des exemples de familles de langues, dans lesquelles le non-déterminisme peut sauver un facteur quadratique, et des cas où le non-déterminisme ne permet pas de sauver des États du tout. Ainsi, une question naturelle est la suivante:2n2n

Problème de nombre magique

Existe-t-il, pour chaque compris entre n et 2 n , un langage régulier L n tel que l'écart entre la complexité d'états non déterministe et la complexité d'états déterministe est exactement α ?αn2nLnα

Si nous comprenons parfaitement la construction de l’ensemble des pouvoirs et la relation Myhill-Nerode d’un point de vue mathématique, je suppose que nous pourrons alors construire de tels langages pour chaque , ou bien spécifier les valeurs de α pour lesquelles cela est impossible (si de telles valeurs existent, elles sont appelées "nombres magiques").αα

On sait qu'il existe des nombres magiques pour la taille d'alphabet et, depuis 2009, qu'il n'y en a plus si la taille de l'alphabet est au moins de 3 . Mais si je ne me trompe pas, le cas des alphabets binaires est toujours ouvert.13

Galina Jirásková. Nombres magiques et alphabet ternaire. Dans: 13e Conférence internationale sur les développements de la théorie des langues (DLT 2009), volume 5583 de Notes de lecture en informatique, pages 300 à 311.

Hermann Gruber
la source
7
C'est un gros problème! Mais quiconque a inventé le terme "nombre magique" doit être abattu.
Jeffrey Shallit
20

Titre: Non-vide d'intersection pour deux DFA

Description: Étant donné deux DFA de et D 2 , est -ce qu'il existe une chaîne x telle que D 1 et D 2 acceptent tous deux x ?12X12X

Ouvert Problème: Peut - on résoudre non vide d'intersection pour deux de DFA dans temps?o(n2)

Si nous pouvions résoudre ce problème en temps δ <2, l'hypothèse temporelle exponentielle forte serait alors réfutée.O(nδ)δ

Explication: Décider de la vacuité d'intersection de langages normaux en un temps sous-quadratique

Cela pourrait vous être utile: http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

Passez une bonne journée! :)

Michael Wehar
la source
salut MW heureux vous avez remarqué cette question. récemment vous avez cité sur cette autre question re séparation P / L . Comme vous l'avez récemment prouvé, la question ci-dessus (limites supérieures de la complexité de la résolution du non-vide d'intersection de plusieurs DFA) est étroitement liée au (principal problème ouvert de la séparation) P / NL.
vzn
Merci beaucoup! Qui êtes-vous vzn? Je suis allé sur votre blog et ai regardé autour de moi, mais je ne pouvais pas le comprendre.
Michael Wehar
1
Remarque: la plus petite chaîne acceptée par et D 2 a une longueur Ω ( n 2 ) dans le pire des cas. 12Ω(n2)
Michael Wehar
12

Voici un problème ouvert entre DFA et la théorie de l'apprentissage automatique: les DFA peuvent-ils être appréhendés uniformément de manière aléatoire (transitions aléatoires et comportement d'acceptation / de rejet) dans le modèle PAC?

Remarque: nous pensons que les DFA arbitraires ne peuvent pas être appris en raison des résultats de la dureté cryptographique . Pour les DFA aléatoires, nous n’avons que les limites inférieures de la QS , qui ne sont pas aussi fortes.

Lev Reyzin
la source
12

Les automates à couverture minimale font partie des éléments associés. Étant donné un langage fini , on peut obtenir un minimum DFA pour L . Mais si nous assouplissons les exigences de DFA, nous pouvons en trouver de plus petites. Nous savons que le mot le plus long dans un langage fini L a une longueur l . Définissez DFCA comme un DFA qui accepte uniquement les mots en L ou éventuellement des mots plus longs que l . Cela peut DFCA a une taille plus petite que DFA pour L . En pratique, vérifier la longueur d'un mot n'a pas d'importance. Si nous avons un DFCA plus petit qui accepte les originaux, nous pouvons simplement rejeter les mots dont la longueur est supérieure à l . Il existe des recherches sur cette classe (introduites en 2001), et il existe par exemple unLLLlLlLl algorithmepour trouver un minimum de DFCA. Un algorithme de temps d'exécution optimal n'est pas encore connu. Nous pouvons également considérer d'autres aspects de DFA concernant DFCA.O(n2)

Saeed
la source
6

Combien de langues standard existe-t-il dont le DFA minimal a exactement états?n

Il me semble qu'une formule fermée devrait exister, mais aucune n'est connue. Certaines limites asymptotiques sont connues:

Sur le nombre de langues distinctes acceptées par les automates finis à étatsn . M Domaratzki, D Kisman, J Shallit.

Mikero
la source
C'est vraiment cool. Je pensais juste à cela l’autre jour et je ne savais pas que d’autres avaient travaillé là-dessus. Merci d'avoir partagé. :)
Michael Wehar
4
Pourquoi croyez-vous qu'il existe une formule fermée? Je pense que c'est très improbable.
Domotorp
Voir aussi cette question pour ce qui est connu de ce problème: Quel est le nombre de langues acceptées par un DFA de taille n
Hermann Gruber
2

Voici une question concernant DFA que je viens de lire avant, et elle est toujours ouverte à ma connaissance:

nΣ={0,1}FUNE(n)n|FUNE(n)|=n2n2n

X,yΣ*Kn(X,y)FUNE(n) Xy

Kn(X,y)Kn(X,y)poly(n,|X|,|y|)

Cette question a des implications pour l'apprentissage automatique .

Aryeh
la source
Quel est l'état actuel de la complexité du problème?
Ryan le
1
Jérémie Blocki a eu des résultats partiels; c'est l'état des connaissances pour autant que je sache: cs.cmu.edu/~jblocki/Slides/ComputationalComplexityofKn.pdf
Aryeh le
-3

("penser en dehors de la boîte" ...) il s'agit d'un problème quelque peu artificiel impliquant des DFA (je ne l'ai pas vu étudier ailleurs), mais il révèle un thème dans TCS selon lequel même de nombreux objets de calcul apparemment "simples" (comme les DFA) peuvent avoir des propriétés complexes , également un aspect / thème incorporé dans le théorème de Rices. (à certains égards, la "complexité" ultime est "indécidabilité", autrement dit la complétude de Turing.)

nXnXn

FUNEnFUNEFUNEnFUNEnFUNE, est également un RL (et un DFA).

Σ

le problème "existe-t-il un nFUNEnΣ*

Σ*n

maintenant, pour relier cela davantage à la question, bien que cela ne soit pas largement noté (considéré comme trivial par certains), de nombreux problèmes en suspens en TCS / mathématiques sont étroitement liés à l’indécidabilité dans la mesure où, compte tenu de l’oracle du problème, ils peuvent être ". résolu ".

par conséquent, dans un sens, en reliant tout cela en utilisant ce problème de base d'ADF indécidable, il y aura toujours des problèmes ouverts concernant les ADF, car il y aura toujours des problèmes "ouverts" concernant les ADF (tels que celui-ci) équivalents aux problèmes indécidables. . En fait, en utilisant le théorème de Rices à l'inverse de cette construction, on peut utiliser n'importe quelle propriété de calcul relativement "simple" mais non triviale dans TCS pour construire des problèmes indécidables.

[1] Problèmes de mots nécessitant un temps exponentiel / Stockmeyer & Meyer

[2] Meyer, AR et L. Stockmeyer. Le problème d'équivalence pour les expressions régulières avec quadrature nécessite un espace exponentiel. 13e symposium de l'IEEE sur la théorie des commutateurs et des automates, octobre 1972, p. 125-129.

[3] Introduction aux langages, aux automates et au calcul / Hopcroft / Ullman.

vzn
la source
2
Je pense que vous confondez les concepts "indécidable" et "ouvert".
Lev Reyzin
comme l'a reconnu, il est peu commun et / ou non conventionnel de dire le moins, mais je ne suis pas le seul à l'avoir épousée. voir, par exemple, cette citation de Michel dans cet article Problèmes de théorie des nombres dus à une concurrence occupée des castors . des sentiments similaires exprimaient également, à propos de la célèbre théorie des nombres ouverts, un problème simple dont l’indécidabilité est inconnue . voir aussi théorème automatisé prouvant vs indécidabilité
vzn
FUNEnΣ*n{1n|FUNEnΣ*}
FUNE