Combien de DFA acceptent deux chaînes données?

Fixe un entier $n$ et un alphabet $\Sigma=\{0,1\}$ . Définissez $DFA(n)$ comme la collection de tous les automates à états finis sur $n$ états avec l'état de départ 1. Nous considérons tous les DFA (pas seulement ceux connectés, minimaux ou non dégénérés); ainsi $|DFA(n)| = n^{2n}2^n$ .

Considérons maintenant deux chaînes $x,y\in\Sigma^*$ et définissons $K(x,y)$ comme le nombre d'éléments de $DFA(n)$ qui acceptent à la fois $x$ et $y$ .

Question: Quelle est la complexité du calcul de $K(x,y)$ ?

Cette question a des implications pour l'apprentissage automatique .

Edit: Maintenant qu'il y a une récompense sur cette question, je suppose qu'un peu plus de précision dans la formulation est de mise. Pour $n\ge1$ , soit $DFA(n)$ la collection de $n^{2n}2^n$ automates, comme défini ci-dessus. Pour $x,y\in\{0,1\}^*$ , définissez $K_n(x,y)$ comme le nombre d'automates dans $DFA(n)$ qui acceptent les deux $x$ et $y$ . Question: $K_n(x,y)$ peut-il être calculé en temps $poly(n,|x|,|y|)$ ?

cc.complexity-theory fl.formal-languages automata-theory counting-complexity Aryeh
la source

Si vous corrigez un DFA sans fixer les états finaux, alors il mappe x et y au même état, auquel cas la seule contrainte est que l'état doit être final, ou il les mappe à deux états différents, auquel cas la seule contrainte est qu'ils doivent tous deux être définitifs. Ainsi, je reformulerais votre problème comme "combien de DFA mappent x et y à différents états?".

a3nm

Aryeh, pouvez-vous expliquer le nombre

n^{2 n} 2^{n}

$n^{2n} 2^n$ ? Je ne peux pas obtenir le facteur

2^{n}

$2^n$ . Ajouté: Oups, j'ai oublié de spécifier les états finaux. Quoi qu'il en soit, pour le bien des autres, voici comment se déroule le décompte. Pour chaque état, spécifiez où aller sur les entrées

0

$0$ et

1

$1$ ; cela représente

n^{2 n}

$n^{2n}$ . Spécifiez l'ensemble des états finaux; c'est

2^{n}

$2^n$ .

Srivatsan Narayanan

En effet, je me fiche de ce qui arrive aux chaînes autres que

. Je suppose que l'on a besoin d'un certain nombre de points pour commencer une prime?

x

$x$

y

$y$

Aryeh

Le plus petit automate qui accepte

a un seul état, donc je ne pense pas que ce soit terriblement informatif ...

x

$x$

y

$y$

Aryeh

Voici une idée: il suffit de connaître le nombre de DFA à

états qui se retrouvent dans le même état sur

. Soit ce nombre

le nombre total de DFA, c'est-à-dire

. Alors la réponse est

n

$n$

x

$x$

y

$y$

m

$m$

M

$M$

M = n^{2 n} 2^{n}

$M=n^{2n}2^{n}$

\frac{1}{2} m + \frac{1}{4} (M - m)

$\frac{1}{2}m + \frac{1}{4}(M-m)$

m

$m$

x

$x$

y

$y$

x = 0^{a}

$x=0^a$

b = 1^{b}

$b=1^b$

l

$l$

max {a, b}

$\max\{a,b\}$

0^{a}

$0^a$

1^{b}

$1^b$

m

$m$

Réponses:

La question est donc assez brève mais très intéressante. Je suppose que l'entrée est en unaire et et en binaire (ou nous avons des problèmes, comme l'a souligné la réponse de Kai). $n$ $x$ $y$

Tout d'abord, si vous souhaitez connaître approximativement , vous pouvez simplement générer quelques DFA aléatoires et cela vous donnera (whp) une bonne approximation. (Je me demande si cette classe de complexité a un nom.) $K(x,y)$

Alors connaître semble précisément être un problème difficile. Comme indiqué dans les commentaires de a3_nm et Kaveh, la question revient à déterminer le nombre d'automates pour lesquels et passent au même état. Je dénoterai la probabilité qu'ils passent au même état par . $K(x,y)$ $x$ $y$ $p$

Mise à jour: Certaines des choses que j'ai écrites ici n'étaient pas vraies, maintenant je les ai corrigées.

Il est facile de voir que . Nous avons l'égalité, si est tout 0 et est tout zéro sauf pour son dernier bit, qui est un 1. Y a-t-il d'autres cas? Je ne sais pas. Si par exemple est la chaîne vide et , alors . $p \ge 1/n$ $x$ $y$ $x$ $y=00$ $p= \frac{n+1}{(n-1)n}$

Pour simplifier le problème, j'ai même commencé à penser à ce qui se passe si et sont unaires. Si les deux sont au moins et que leur différence est divisible par, alors . Existe-t-il une formule simple pour la version unaire? $x$ $y$ $n$ $n!$ $p=1$

domotorp
la source

J'ai clarifié le problème - un algorithme

est souhaité (ou une réduction par rapport à un problème difficile connu). L'approximation d'échantillonnage est utilisée dans l'article où ce noyau est introduit: portal.acm.org/citation.cfm?id=1577108

p o l y (n, | x |, | y |)

$poly(n,|x|,|y|)$

Aryeh

Quant à la version unaire: il n'y a que de nombreux automates unaires à

états, je parierais donc qu'il existe un algorithme poly-temps pour calculer

dans ce cas.

n

$n$

K_{n} (x, y)

$K_n(x,y)$

Aryeh

En effet, vous avez absolument raison de dire que la version unaire est calculable. Je me demande encore à quel point la formule est simple pour un x et un y donnés.

domotorp

La réduction que vous avez utilisée est boguée: x et y peuvent être acceptés par les mêmes automates et se terminer dans des états complètement différents, en fait, ils ne peuvent partager que l'état de départ dans leurs chemins, ce qui est vrai pour toutes les chaînes.

amnn

@amnn: Cela fait trois ans que j'ai écrit ceci, mais le troisième paragraphe de ma réponse n'explique-t-il pas pourquoi je ne traite que de finir dans le même état?

domotorp

Je peux très bien manquer le point, mais vous avez déclaré que est fixe, donc tous les DFA de cette taille pourraient être considérés comme précalculés et stockés dans un format facilement simulable. Calculez comme suit: $n$ $K$

En entrée , où $x$ $y$ $x,y\in\Sigma^*$

stocker et $x$ $y$
initialiser le compteur à $c$ $0$
pour chacun de vos DFA $n^{2n} 2^n$
une. simulez-le sur les deux mots (cette étape est ) $\mathcal{O}(|xy|)$

b. incrémenter si les deux cycles de simulation acceptent $c$
sortie $c$

Au total, le calcul a une complexité linéaire. La réponse est assez différente pour . $K(n,x,y)$

Kai
la source

Il est clair que toutes les machines fonctionneront. Aryeh veut savoir s'il existe, peut-être, un algorithme de temps polynomial ou sinon un résultat de dureté.

Lev Reyzin

Strictement parlant, c'est le temps polynomial dans l'entrée, si n ne fait pas partie de l'entrée, c'est ce que Kai disait. Mais la question est clairement différente.

domotorp

Oh je vois. Je ne pense pas que c'est ce qu'il entend par «fixer

». Je pense que l'interprétation naturelle du problème est celle qui ne le banalise pas.

n

$n$

Lev Reyzin

D'accord, merci d'avoir signalé l'échappatoire, Kai. Il a été corrigé :)

Aryeh