Número de DFAs mínimos de tamanho, no máximo,

Seja um alfabeto de tamanho e considere DFAs mínimos, cujo tamanho é limitado por no máximo . Seja o número de diferentes DFAs mínimos. $\Sigma$ $2$ $m$ $f(m)$

Podemos encontrar uma fórmula de forma fechada para ? $f(m)$

Considerando que para a função de transição de um DFA de tamanho no máximo é um gráfico. Como o grau dos nós é delimitado por , para cada nó existem possibilidades de pares de arcos (conforme sugerido nos comentários). Neste gráfico, existem no máximo opções possíveis de estado inicial e no máximo opções possíveis de conjuntos de estados finais. Assim, o número máximo de DFAs de tamanho no máximo é . $|\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 para um alfabeto arbitrário : o limite se torna . $\Sigma$ $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$

Mas limitamos aqui os DFAs arbitrários e estou interessado em limitar o número mínimo de DFAs. Assim, parece que esse limite poderia ser mais apertado ... Alguém tem uma estimativa melhor?

Eu apreciaria, se possível, alguns trabalhos relacionados a esse problema ou uma prova / contra-exemplo.

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

Não acho que seu limite superior esteja correto. Parece que deve ser , em vez de . Para cada nó, considere os dois arcos que saem desse nó; existem possibilidades para onde o primeiro arco vai, e possibilidades para onde o segundo arco vai, então possibilidades no total. Como existem nós, obtemos possibilidades para o conjunto de arcos. A generalização seria .

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

Aqui é uma referência que pode ser relevent: "sobre o número de DISTINCT línguas aceites pelo Autômatos Finitos com N estados" - citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838

Michael Wehar

Agradeço a vocês por corrigirem meu erro e me fornecerem essa referência que é de fato relevante.

Luz

Respostas:

De acordo com Ishigami Y., Tani S. (1993) As dimensões VC de autômatos finitos com n estados, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , a dimensão VC de a classe de conceito de DFAs de estados em um alfabeto de tamanho é Segue-se que existem pelo menos autômatos state distintos em um $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. O limite superior do número de tais autômatos segue de um argumento simples de contagem (fornecido no artigo) e é no máximo

2^{d}

$2^d$

Aryeh
fonte

Obrigado. Entendo pela sua resposta que existem

DFAs de estados (pelo menos e no máximo). Mas estou interessado em contar o mínimo de DFAs. Assim, o seu limite superior não contradiz o dado na minha resposta, certo?

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

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

m

$m$

Luz

Eu acho que isso também conta com DFAs mínimos, já que a dimensão VC é independente da representação, na verdade, está contando idiomas distintos - que correspondem a DFAs mínimos.

Aryeh 22/02

oh :( então seu limite está contradizendo meu ... desde meu tem um grande denominador

o que o torna muito abaixo seu ... como é que ??

(m - 1)!

$(m-1)!$

Luz

Não vejo bem a contradição - o denominador grande

ainda é inundado por

no numerador.

(m - 1)!

$(m-1)!$

m^{m}

$m^m$

Aryeh 22/02

De fato, se você olhar para a prova de Thm. 3.2 no artigo que vinculei, você verá a expressão exata no denominador.

Aryeh 22/02

(Nota: o limite superior indicado na resposta aceita é melhor ou igual ao indicado aqui)

Um limite superior é proposto neste artigo, dado em um dos comentários anteriores: “ Sobre o número de línguas distintas aceitas por autômatos finitos com n estados ” (2002, M. Domaratzki, D. Kisman, J. Shallit) .

Nesse papel:

o função fornece o número de DFAs mínimos não isomórficos distintos com estados- ao longo de um alfabeto de letras , $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
fonte