Liczba minimalnych DFA wielkości co najwyżej ?

Niech będzie alfabetem wielkości i rozważmy minimalne DFA, których rozmiar jest ograniczony co najwyżej . Niech oznacza liczbę różnych takich minimalnych DFA. $\Sigma$ $2$ $m$ $f(m)$

Czy możemy znaleźć formułę zamkniętą dla ? $f(m)$

Biorąc pod uwagę, że dla funkcją przejścia DFA o wielkości co najwyżej jest wykres. Ponieważ stopień węzłów jest ograniczony przez , dla każdego węzła istnieją możliwości par łuków (jak sugerowano w komentarzach). Na tym wykresie istnieje co najwyżej możliwych wyborów stanu początkowego i co najwyżej możliwych wyborów zbiorów stanów końcowych. Zatem maksymalna liczba DFA wielkości co najwyżej wynosi . $|\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}$

Możemy uogólnić na dowolny alfabet : granica staje się . $\Sigma$ $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$

Ale ograniczyliśmy tutaj arbitralne DFA i jestem zainteresowany ograniczeniem liczby minimalnych DFA. Wygląda więc na to, że ta granica może być ściślejsza ... Czy ktoś ma lepsze oszacowanie?

Byłbym wdzięczny, jeśli to możliwe, niektóre dokumenty związane z tym problemem lub dowód / kontrprzykład.

cc.complexity-theory automata-theory nondeterminism dfa Luz
źródło

Nie sądzę, aby górna granica była prawidłowa. Wygląda na to, że powinno być

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

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

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

$f(m) \le m \times 2^m \times 2^{2m}$ . Dla każdego węzła rozważ dwa łuki prowadzące z tego węzła; tam są

m

$m$ możliwości, gdzie idzie pierwszy łuk, oraz

m

$m$ możliwości, gdzie idzie drugi łuk, więc

m^{2}

$m^2$ możliwości ogółem. Tam są

m

$m$ węzły, więc otrzymujemy

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

$(m^2)^m = m^{2m}$ możliwości dla zestawu łuków. Uogólnienie byłoby

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

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

Oto odniesienia, które mogą być dowiemy się z: „ON liczba różnych JĘZYKI akceptowane przez automaty skończone z n Zjednoczonych” - citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838

Michael Wehar

Dziękuję wam obojgu za naprawienie mojego błędu i przekazanie mi tej referencji, która jest rzeczywiście istotna.

Luz

Odpowiedzi:

Według Ishigami Y., Tani S. (1993) Wymiary VC skończonych automatów ze stanami n, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , wymiar VC klasa koncepcyjna $n$ -state DFA ponad alfabet wielkości $k$ jest

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

$d=d(n,k) := (k-1+o(1))n\log_2 n.$ Wynika z tego, że są przynajmniej

2^{d}

$2^d$ odrębny

n

$n$ -state automaty na

k

$k$ alfabet. Górna granica liczby takich automatów wynika z prostego argumentu liczenia (podanego w artykule) i jest co najwyżej

2^{d}

$2^d$ .

Aryeh
źródło

Dzięki. Rozumiem z twojej odpowiedzi, że są

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

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

m

$m$ - podaje DFA (przynajmniej i najwyżej). Ale jestem zainteresowany liczeniem minimalnych DFA. Zatem twoja górna granica nie jest sprzeczna z tą podaną w mojej odpowiedzi, prawda?

Luz

Myślę, że to także liczy minimalne DFA, ponieważ wymiar VC jest niezależny od reprezentacji, w rzeczywistości liczy różne języki - które odpowiadają minimalnym DFA.

Aryeh

oh :( wtedy twoja granica jest sprzeczna z moją ... ponieważ moja ma duży mianownik

(m - 1)!

$(m-1)!$ co sprawia, że jest znacznie poniżej twojego ... dlaczego?

Luz

Nie do końca widzę sprzeczność - duży mianownik

(m - 1)!

$(m-1)!$ jest wciąż zalany

m^{m}

$m^m$ w liczniku.

Aryeh

W rzeczywistości, jeśli spojrzysz na dowód Thm. 3.2 w dokumencie, który podłączyłem, zobaczysz dokładnie to wyrażenie w mianowniku.

Aryeh

(Uwaga: górna granica podana w zaakceptowanej odpowiedzi jest lepsza lub równa tej podanej tutaj)

Górna granica jest zaproponowana w tym artykule podanym w jednym z poprzednich komentarzy: „ O liczbie różnych języków akceptowanych przez automaty skończone z n stanami ” (2002, M. Domaratzki, D. Kisman, J. Shallit) .

W tym papierze:

$f_{|\Sigma|}(m)$ funkcja zapewnia liczbę wyraźnych nieizomorficznych minimalnych DFA z $m$ -states ponad ${|\Sigma|}$ alfabet ,
$g_{|\Sigma|}(m)$ funkcja podaje liczbę różnych języków akceptowanych przez DFA $m$ stwierdza nad ${|\Sigma|}$ alfabet .

Interesuje nas górna granica dla $g_{|\Sigma|}(m)$ funkcja, ponieważ moje pytanie zapytać o górną granicę liczby minimalnych DFAS z co najwyżej $m$ stwierdza (i nie do końca $m$ ).

Co rozumiem ze strony $6$ poniżej Twierdzenia $8$ czy to $g_{|\Sigma|}(m) \leq \frac{2^m\cdot m^{|\Sigma|m}}{(m-1)!}$ która jest lepsza niż ta podana w moim pytaniu (tj $2^m\cdot m^{|\Sigma|m+1}$ ). To częściowo odpowiada na moje pytanie.

Ale gazeta twierdzi, że ta górna granica jest trywialna i można ją poprawić. Jednak poprawa dotyczy tylko $f_{|\Sigma|}(m)$ (o ile rozumiem).

Luz
źródło