¿Número de DFA mínimos de tamaño como máximo

Deje que sea un alfabeto de tamaño , y considere los DFA mínimos cuyo tamaño está limitado como máximo por . Supongamos que denota el número de diferentes DFA mínimos de este tipo. $\Sigma$ $2$ $m$ $f(m)$

¿Podemos encontrar una fórmula de forma cerrada para ? $f(m)$

Teniendo en cuenta que para la función de transición de un DFA de tamaño como máximo es un gráfico. Dado que el grado de los nodos está limitado por , para cada nodo hay posibilidades de pares de arcos (como se sugiere en los comentarios). En este gráfico hay como máximo posibles elecciones de estado inicial y como máximo posibles elecciones de conjuntos de estados finales. Por lo tanto, el número máximo de DFA de tamaño como máximo es . $|\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}$

Podemos generalizar a un alfabeto arbitrario : el límite se convierte en . $\Sigma$ $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$

Pero limitamos aquí los DFA arbitrarios y estoy interesado en limitar el número de DFA mínimos. Por lo tanto, parece que este límite podría ser más estricto ... ¿Alguien tiene una mejor estimación?

Agradecería si es posible, algunos documentos relacionados con este problema o una prueba / contraejemplo.

cc.complexity-theory automata-theory nondeterminism dfa Luz
fuente

No creo que tu límite superior sea correcto. Parece que debería ser , en lugar de . Para cada nodo, considere los dos arcos que salen de ese nodo; hay posibilidades de dónde va el primer arco posibilidades de dónde va el segundo arco, por lo que posibilidades en total. Hay nodos, por lo que obtenemos posibilidades para el conjunto de arcos. La generalización sería .

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$

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

Aquí hay una referencia que puede ser relevante: "EN EL NÚMERO DE IDIOMAS DISTINTOS ACEPTADOS POR AUTOMÁTICOS FINITOS CON n ESTADOS" - citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838

Michael Wehar

Gracias a los dos por corregir mi error y darme esta referencia, que de hecho es relevante.

Luz

Respuestas:

Según Ishigami Y., Tani S. (1993) Las dimensiones VC de autómatas finitos con n estados, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , la dimensión VC de La clase de concepto de DFA -estatales sobre un alfabeto de tamaño es De ello se deduce que hay al menos autómatas distintos de estados en una $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$ Alfabeto de letras. El límite superior en el número de dichos autómatas se deriva de un argumento de conteo simple (dado en el documento), y es como máximo

2^{d}

$2^d$

Aria
fuente

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

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

m

$m$

Creo que esto también cuenta con DFA mínimos, ya que la dimensión VC es independiente de la representación, en realidad está contando lenguajes distintos , que corresponden a DFA mínimos.

Aryeh

(m - 1)!

$(m-1)!$

(m - 1)!

$(m-1)!$

m^{m}

$m^m$

De hecho, si nos fijamos en la prueba de Thm. 3.2 en el artículo que vinculé, verá esa expresión exacta en el denominador.

Aryeh

(NB: el límite superior dado en la respuesta aceptada es mejor o igual al dado aquí)

Se propone un límite superior en este documento en uno de los comentarios anteriores: " Sobre el número de idiomas distintos aceptados por autómatas finitos con n estados " (2002, M. Domaratzki, D. Kisman, J. Shallit) .

En este papel:

$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
fuente