Hay un bonito papel de la Enumeración de los Autómatas Finitos por Frank Harary y Ed Palmer, que presenta una fórmula $a(n,k,m)$ para el número de autómatas finitos con $n$ estados, $k$ símbolos de entrada y $m$ salida de símbolos. Se afirma en el Corolario $3$ \begin{align*} a(n,k,m)=\frac{1}{n!k!m!}\sum_{H_1} I(\alpha,\beta,\alpha)I(\alpha,\beta,\gamma) \end{align*} donde la suma es sobre todas las permutaciones en $H_1=S_n^{S_n\times S_k}\times S_m^{S_n\times S_k}$ de la forma $\{[(\alpha,\beta);\alpha^{-1}],[(\alpha,\beta);\gamma]\}$ con \begin{align*} I(\alpha,\beta,\gamma)=\prod_{p=1}^n\prod_{q=1}^k\left[\sum_{s|[p,q]}sj_s(\gamma)\right]^{j_p(\alpha)j_q(\beta)\langle p,q\rangle} \end{align*}
Aquí, los autores indican con $[p,q]:=\operatorname{lcm}(p,q), \langle p,q\rangle:=\operatorname{gcd}(p,q)$ $j_p(\alpha)$ indica el número de ciclos de la permutación $\alpha$ con una longitud de $p$.
El caso especial $n=k,m=1$ es ya analizados y calculados para los valores pequeños de a $n$ en este MSE post, sobre todo con enfoque a $n=4$.
Pregunta: tal vez alguien podría proporcionar algunos cálculos para el caso general, para valores pequeños de a $n,k,m$?
Respuesta
¿Demasiados anuncios?
Scott Burns
Puntos
371
A continuación se presentan las tablas para $a(N,K,M)$ para los valores de $\le 5$ donde
$N = $ número de estados, $K = $ número de entradas, $M = $ número de salidas.
Tenga en cuenta que si arreglamos $N$ $K$ y deje $M$ de aumento, esto a la larga se vuelve independiente de $M$. Una vez $M$ es lo suficientemente grande para cubrir cualquier posible equivalencia en los bordes del estado transtion gráfico, no hay ganancia de aumento.
Por lo tanto, dos preguntas interesantes:
¿Cuál es la terminal de $M$ por cada elección de $(N,K)$? I. e. calcular $$ M^*(N,K) := m^*: un(N,K,m) = a(N,K,m^*)\ \ \ \ forall \ m>m^* $$ ¿Cuáles son los valores de $a(N,K,M^*(N,K))$?
+-----+---+------+------------+-----------------+-----------------+-----------------+
| M=2 | | K | | | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | | 1 | 2 | 3 | 4 | 5 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| N | 1 | 1 | 2 | 2 | 3 | 3 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 2 | 6 | 44 | 226 | 1036 | 4006 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 3 | 22 | 2038 | 142336 | 7775708 | 341906882 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 4 | 114 | 176936 | 238882846 | 244698934716 | 200649261017386 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 5 | 538 | 20943790 | 694540531869 | 1.35E+015 | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | | | | | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| M=3 | | K | | | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | | 1 | 2 | 3 | 4 | 5 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| N | 1 | 1 | 2 | 3 | 4 | 5 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 2 | 6 | 75 | 775 | 7124 | 55668 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 3 | 29 | 7623 | 1804128 | 329641077 | 48317584819 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 4 | 190 | 1501516 | 10322146155 | 53512221536494 | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 5 | 1289 | 401371270 | 101367856946674 | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | | | | | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| M=4 | | K | | | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | | 1 | 2 | 3 | 4 | 5 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| N | 1 | 1 | 2 | 3 | 5 | 6 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 2 | 6 | 81 | 1183 | 17320 | 223743 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 3 | 29 | 11676 | 6064606 | 2593640209 | 897009602752 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 4 | 209 | 3831148 | 81573276196 | 248097408553 | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 5 | 1605 | 1790644262 | | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | | | | | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| M=5 | | K | | | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | | 1 | 2 | 3 | 4 | 5 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| N | 1 | 1 | 2 | 3 | 5 | 7 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 2 | 6 | 81 | 1283 | 23718 | 427097 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 3 | 29 | 12621 | 9875766 | 7694431189 | 5108729338005 |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 4 | 209 | 5269634 | 242293771832 | 167930305528968 | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
| | 5 | 1652 | 3522483774 | | | |
+-----+---+------+------------+-----------------+-----------------+-----------------+
