Nombre de DFA minimaux de taille au plus

Soit un alphabet de taille , et considérons des DFA minimaux dont la taille est limitée par au plus . Soit le nombre de différents DFA minimaux. $\Sigma$ $2$ $m$ $f(m)$

Peut-on trouver une formule sous forme fermée pour ? $f(m)$

Considérant que pour la fonction de transition d'un DFA de taille au plus est un graphe. Le degré des nœuds étant limité par , il existe pour chaque nœud possibilités de paires d'arcs (comme suggéré dans les commentaires). Dans ce graphique, il y a au plus choix possibles d'état initial et au plus choix possibles d'ensembles d'états finaux. Ainsi, le nombre maximum de DFA de taille au plus est $|\Sigma|=2$ $m$ $2$ $m^2$ $m$ $2^m$ $m$ . $f(m) \leq m^{2m}\cdot m\cdot2^m = 2^m\cdot m^{2m+1}$

On peut généraliser à un alphabet arbitraire : la borne devient . $\Sigma$ $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$

Mais nous avons limité ici les DFA arbitraires et je suis intéressé à limiter le nombre de DFA minimaux. Ainsi, il semble que cette limite pourrait être plus serrée ... Quelqu'un a-t-il une meilleure estimation?

J'apprécierais si possible, quelques papiers liés à ce problème ou une preuve / contre-exemple.

cc.complexity-theory automata-theory nondeterminism dfa Luz
la source

Je ne pense pas que votre limite supérieure soit correcte. Il semble que ce devrait être

, plutôt que

. Pour chaque nœud, considérez les deux arcs sortant de ce nœud; il y a

possibilités pour où va le premier arc, et

possibilités pour où va le deuxième arc, donc

possibilités au total. Il y a

nœuds, donc on obtient

f (m) \leq m \times 2^{m} \times m^{2 m}

$f(m) \le m \times 2^m \times m^{2m}$

f (m) \leq m \times 2^{m} \times 2^{2 m}

$f(m) \le m \times 2^m \times 2^{2m}$

m

$m$

m

$m$

m^{2}

$m^2$

m

$m$

possibilités pour l'ensemble d'arcs. La généralisation serait

(m^{2})^{m} = m^{2 m}

$(m^2)^m = m^{2m}$

f (m) \leq m \times 2^{m} \times m^{| Σ | m}

$f(m) \le m \times 2^m \times m^{|\Sigma| m}$

Voici une référence qui peut être pertinente: "SUR LE NOMBRE DE LANGUES DISTINCTES ACCEPTÉES PAR FINITE AUTOMATA AVEC N ÉTATS" - citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838

Michael Wehar

Merci à vous deux d'avoir corrigé mon erreur et de m'avoir donné cette référence qui est effectivement pertinente.

Luz

Réponses:

Selon Ishigami Y., Tani S. (1993) The VC-dimensions of finite automata with n states, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , the VC-dimension of la classe conceptuelle des DFA à états sur un alphabet de taille est Il s'ensuit qu'il existe au moins automates distincts à états sur un $n$ $k$

d = d (n, k) := (k - 1 + o (1)) n \log_{2} n .

$d=d(n,k) := (k-1+o(1))n\log_2 n.$

2^{d}

$2^d$

n

$n$

k

$k$ alphabet de lettres. La limite supérieure du nombre de ces automates découle d'un simple argument de comptage (donné dans l'article) et est au plus de

2^{d}

$2^d$

Aryeh
la source

m^{(| Σ | - 1 + o (1)) m}

$m^{(|\Sigma| - 1 + o(1)) m}$

m

$m$

Je pense que cela compte également des DFA minimaux, puisque la dimension VC est indépendante de la représentation, elle compte en fait des langages distincts - qui correspondent à des DFA minimaux.

Aryeh

(m - 1)!

$(m-1)!$

(m - 1)!

$(m-1)!$

m^{m}

$m^m$

En fait, si vous regardez la preuve de Thm. 3.2 dans l'article que j'ai lié, vous verrez cette expression exacte dans le dénominateur.

Aryeh

(NB: la borne supérieure donnée dans la réponse acceptée est meilleure ou égale à celle donnée ici)

Une limite supérieure est proposée dans cet article donné dans l'un des commentaires précédents: « Sur le nombre de langues distinctes acceptées par les automates finis à n états » (2002, M. Domaratzki, D. Kisman, J. Shallit) .

Dans cet article:

$f_{|\Sigma|}(m)$ $m$ ${|\Sigma|}$
$g_{|\Sigma|}(m)$ $m$ ${|\Sigma|}$

$g_{|\Sigma|}(m)$ $m$ $m$

$6$ $8$ $g_{|\Sigma|}(m) \leq \frac{2^m\cdot m^{|\Sigma|m}}{(m-1)!}$ $2^m\cdot m^{|\Sigma|m+1}$

$f_{|\Sigma|}(m)$

Luz
la source