Séparation des mots avec des DFA aléatoires

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 revisite le même état une fois qu'il atteint le premier endroit où et diffèrent, et sépare donc et . $u,v \in \Sigma^n$ $O(n)$ $u$ $v$ $u$ $v$

Pouvons-nous faire mieux? Idéalement, ce qui est le plus petit st que DFA aléatoire les chaînes de états de longueur avec une probabilité positive (ou peut - être la probabilité )? 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)$ $n$ $\ge 1/2$

dfa random-graphs 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

Que signifie «sépare»? Accepte l'un et rejette l'autre? Si oui, est-il évident que les états

suffisent?

O (n)

$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 (n^{2})

$O(n^2)$

Geoffrey Irving

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

, il est donc peu probable qu'ils soient le cas difficile.

O (\log n)

$O(\log n)$

Geoffrey Irving

[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 ; 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) $u$ $v$ de positions ont plus de chances d'être distinguées que les chaînes qui diffèrent à un ensemble de positions , Je dirais, et mettre la différence le plus tôt possible vous donne la possibilité de resynchroniser). $X$ $Y \subset X$

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 et comme suit: si , et sinon. Je pense qu'il est clair que $w$ $u$ $v$ $w_i = 1$ $u_i = v_i$ $w_i = 0$ $w$ est la seule chose intéressante à considérer à propos de et . $u$ $v$

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

Je pense que nous avons lorsque est . Intuitivement, nous sommes dans le même état après avoir lu lettres soit lorsque nous étions dans le même état après avoir lu , 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) = p(i) + q(i)/n$ $w_{i+1}$ $1$ $i+1$ $i$ lorsque est : vous dessinez deux états aléatoires, peu importe d'où vous êtes parti. $p(i+1) = 1/n$ $w_{i+1}$ $0$

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

a3nm
la source

Malheureusement, il est loin d'être évident que

soit la seule propriété intéressante de

. La façon la plus simple de voir cela est qu'il existe trivialement une probabilité non nulle de distinguer tout

non trivial de

; en effet, seuls deux états suffisent indépendamment de

. Cependant, comme indiqué dans arxiv.org/pdf/1103.4513.pdf , il existe des mots

de longueur

st no

état DFA peut les distinguer. Cela contredit vos formules pour

w

$w$

u

$u$

v

$v$

w

$w$

0^{n}

$0^n$

n

$n$

u, v

$u,v$

n

$n$

o (\log n)

$o(\log n)$

p (i)

$p(i)$ .

Geoffrey Irving

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

$>0$

0^{n}

$0^n$

, OK; et peut-être y a-t-il des mots de longueur

qui ne peuvent pas être différenciés avec

états

. Mais comment cela contredit-il mon affirmation selon laquelle

est la seule chose importante, ou mes formules pour

w \neq 0^{n}

$w \neq 0^n$

n

$n$

o (\log n)

$o(\log n)$

w

$w$

p (i)

$p(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

sont distingués avec une probabilité positive. Cependant, pour un nombre suffisamment grand de

et un petit nombre d'états, nous savons que

pour certains

. Puisque vos formules impliquent que si

alors

p (n) < 1

$p(n) < 1$

u

$u$

v

$v$

n

$n$

p (n) = 1

$p(n) = 1$

u

$u$

v

$v$

p (i) < 1

$p(i) < 1$

, votre formule ne saisit pas le fait que certains

sont impossibles à distinguer.

p (i + 1) = p (i) + (1 - p (i)) / n = p (i) (1 - 1 / n) + 1 / n < 1

$p(i+1) = p(i) + (1-p(i))/n = p(i)(1-1/n)+1/n < 1$

u

$u$

v

$v$

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)

$q(i)$

a3nm

Séparation des mots avec des DFA aléatoires

Réponses: