Séparation des mots avec des DFA aléatoires

15

L'un des problèmes ouverts intéressants concernant les DFA est répertorié dans Existe-t-il des problèmes ouverts concernant les DFA? est la taille d'un DFA requis pour séparer deux chaînes de longueur . Je suis curieux de savoir s'il existe des résultats sur la capacité d'un DFA aléatoire à séparer deux chaînes données (non aléatoires).n

Clairement, un DFA aléatoire avec suffisamment d'états sépare les chaînes avec une forte probabilité. Plus précisément, si , il est peu probable qu'un DFA aléatoire avec des états O ( n ) revisite le même état une fois qu'il atteint le premier endroit où u et v diffèrent, et sépare donc u et v .u,vΣnO(n)uvuv

Pouvons-nous faire mieux? Idéalement, ce qui est le plus petit st que DFA aléatoire f ( n ) les chaînes de états de longueur n avec une probabilité positive (ou peut - être la probabilité 1 / 2 )? Une brève recherche n'a pas donné beaucoup de résultats sur les propriétés des DFA aléatoires; tout ce que j'ai pu trouver était http://arxiv.org/abs/1311.6830 .f(n)f(n)n1/2

Geoffrey Irving
la source
La probabilité positive n'est pas une condition particulièrement utile ici, étant donné qu'il s'agit simplement d'une reformulation du problème ouvert. Une probabilité élevée pourrait encore être intéressante.
Geoffrey Irving
1
Que signifie «sépare»? Accepte l'un et rejette l'autre? Si oui, est-il évident que les états suffisent? O(n)
usul
Oui, séparer signifie accepter exactement un. Et vous avez raison: l'argument de séparation le plus trivial nécessite en fait des états (ce que j'ai écrit ci-dessus est faux), bien que je serais surpris si beaucoup moins ne suffisaient pas. O(n2)
Geoffrey Irving
1
Ne vous attendriez-vous pas à ce que les limites dépendent de la différence entre les mots? Il semble que les mots qui diffèrent par une seule lettre seraient plus difficiles à discriminer au hasard, car vous devez discriminer à cette transition, et des mots très différents seraient plus faciles. [Pour généraliser, vous pouvez oublier le préfixe commun le plus long (vous atteignez un état aléatoire à partir de cela); puis, des lettres différentes vous envoient soit dans le même état, soit dans des états différents; alors si les états sont différents, vous devez regarder la proba de la resynchronisation et rester synchronisé (recommence à dépendre des mots) ...]
a3nm
Oui, comme le problème ouvert, je m'intéresse aux mots les plus difficiles à discriminer. Les mots qui ne diffèrent qu'à quelques endroits peuvent déjà être séparés par états n ) , il est donc peu probable qu'ils soient le cas difficile. O(logn)
Geoffrey Irving

Réponses:

2

[Modifier: cette réponse ne fonctionne pas, voir les commentaires.]

C'est juste une idée informelle et je ne sais pas si ça aide, mais c'est trop long pour être donné en commentaire. De plus, je ne suis pas du tout familier avec les DFA aléatoires, alors j'ai peut-être une mauvaise intuition sur la façon dont vous devriez raisonner sur les probabilités, mais j'espère que cela n'est pas totalement inutile.

Je suppose que vos limites devraient dépendre de la différence entre et v ; s'ils ne le font pas, il me semble clair que le pire des cas sont des chaînes qui ne diffèrent que par leur premier caractère (des chaînes qui diffèrent d'un jeu à l'autre)uv de positions ont plus de chances d'être distinguées que les chaînes qui diffèrent à un ensemble Y X de positions , Je dirais, et mettre la différence le plus tôt possible vous donne la possibilité de resynchroniser).XYX

J'examinerai également la probabilité que les mots se distinguent, à savoir qu'ils atteignent des états différents. Je suppose que vous devrez alors vous adapter pour être accepté ou rejeté en fonction de la façon dont vos DFA aléatoires allouent les états finaux. Si chaque état a une probabilité 1/2 d'être final, alors lorsque les chaînes se retrouvent dans le même état, elles ne sont pas distinguées, et lorsqu'elles se retrouvent dans des états différents, elles ont une probabilité 1/2 d'être distinguées.

Je vais maintenant considérer le mot obtenu à partir de u et v comme suit: w i = 1 si u i = v i , et w i = 0 sinon. Je pense qu'il est clair que wwuvwi=1ui=viwi=0w est la seule chose intéressante à considérer à propos de et v .uv

Maintenant, définissons la probabilité que nous soyons au même état après avoir lu les préfixes de longueur i de u et v , et q ( i ) = 1 - p ( i ) la probabilité que nous ne le soyons pas.p(i)iuvq(i)=1p(i)

Je pense que nous avons lorsque w i + 1 est 1 . Intuitivement, nous sommes dans le même état après avoir lu i + 1 lettres soit lorsque nous étions dans le même état après avoir lu i , soit lorsque nous étions dans deux états différents (aléatoires), nous avons tracé deux transitions vers des états aléatoires, et ils sont arrivés à être le même. De même, nous avons p ( i + 1 ) = 1p(i+1)=p(i)+q(i)/nwi+11i+1i lorsque w i + 1 est 0 : vous dessinez deux états aléatoires, peu importe d'où vous êtes parti.p(i+1)=1/nwi+10

À partir de cela, je pense que vous pourriez calculer la probabilité d'être au même état après avoir lu etu .v

a3nm
la source
Malheureusement, il est loin d'être évident que soit la seule propriété intéressante de u et v . La façon la plus simple de voir cela est qu'il existe trivialement une probabilité non nulle de distinguer tout w non trivial de 0 n ; en effet, seuls deux états suffisent indépendamment de n . Cependant, comme indiqué dans arxiv.org/pdf/1103.4513.pdf , il existe des mots u , v de longueur n st no o ( log n ), l' état DFA peut les distinguer. Cela contredit vos formules pour p ( i )wuvw0nnu,vno(logn)p(i).
Geoffrey Irving
1
Pour clarifier, vos formules seraient correctes si les transitions DFA étaient une fonction aléatoire de l'index de chaîne; puisqu'elles sont indépendantes de l'indice, les probabilités sont corrélées de manière assez compliquée.
Geoffrey Irving
J'ai bien peur de ne pas avoir votre contre-exemple. Il y a prba, avec deux états, de distinguer 0 n et>00n , OK; et peut-être y a-t-il des mots de longueur n qui ne peuvent pas être différenciés avec les états o ( log n ) . Mais comment cela contredit-il mon affirmation selon laquelle w est la seule chose importante, ou mes formules pourw0nno(logn)wp(i)? En ce qui concerne les corrélations, je vois qu'il pourrait y avoir un problème du genre de celui que vous mentionnez, mais je ne comprends pas encore pourquoi il échoue exactement. Si vous passez deux fois dans le même état, il y a une corrélation, mais y a-t-il une raison de penser que cela influencerait dans une certaine direction en moyenne?
a3nm
Si , u et v sont distingués avec une probabilité positive. Cependant, pour un nombre suffisamment grand de n et un petit nombre d'états, nous savons que p ( n ) = 1 pour certains u et v . Puisque vos formules impliquent que si p ( i ) < 1 alors p ( i + 1 ) = p ( i ) + ( 1 - pp(n)<1uvnp(n)=1uvp(i)<1 , votre formule ne saisit pas le fait que certains u et v sont impossibles à distinguer. p(i+1)=p(i)+(1p(i))/n=p(i)(11/n)+1/n<1uv
Geoffrey Irving
Ah ... c'est vrai, je comprends. Si aucun petit DFA ne peut distinguer deux mots, aucun DFA aléatoire ne peut les distinguer non plus. Donc, en effet, il y a un problème avec mon approche, la probabilité devrait finalement tomber à zéro, à cause de ces corrélations, semble-t-il. Désolé d'avoir fourni une réponse incorrecte. q(i)
a3nm