Anzahl der minimalen DFAs mit einer Größe von höchstens

Sei ein Alphabet der Größe und betrachte minimale DFAs, deren Größe durch höchstens . Es sei die Anzahl verschiedener solcher minimaler DFAs. $\Sigma$ $2$ $m$ $f(m)$

Können wir eine geschlossene Formel für ? $f(m)$

In Anbetracht dessen für Die Übergangsfunktion eines DFA mit einer Größe von höchstens ist ein Graph. Da der Knotengrad durch begrenzt ist , gibt es für jeden Knoten Möglichkeiten von Bogenpaaren (wie in den Kommentaren vorgeschlagen). In diesem Diagramm gibt es höchstens mögliche Auswahlmöglichkeiten für den Anfangszustand und höchstens mögliche Auswahlmöglichkeiten für Endzustandsmengen. Somit ist die maximale Anzahl von DFAs der Größe höchstens ist $|\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}$

Wir können auf ein beliebiges Alphabet verallgemeinern : Die Grenze wird zu . $\Sigma$ $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$

Aber wir haben hier beliebige DFAs begrenzt, und ich bin daran interessiert, die Anzahl der minimalen DFAs zu begrenzen. Es sieht also so aus, als ob diese Grenze enger sein könnte ... Hat jemand eine bessere Schätzung?

Ich würde mich, wenn möglich, über einige Artikel zu diesem Problem oder einen Beweis / ein Gegenbeispiel freuen.

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

Ich denke nicht, dass Ihre Obergrenze korrekt ist. Es sieht so aus, als ob es

, anstatt

. Betrachten Sie für jeden Knoten die beiden Bögen, die von diesem Knoten ausgehen. Es gibt

Möglichkeiten, wohin der erste Bogen geht, und

Möglichkeiten, wohin der zweite Bogen geht, also insgesamt

Möglichkeiten. Es gibt

Knoten, also erhalten wir

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öglichkeiten für die Menge der Bögen. Die Verallgemeinerung wäre

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

Hier ist ein Hinweis, der relevant sein kann: "ÜBER DIE ANZAHL DER UNTERSCHIEDLICHEN SPRACHEN, DIE VON ENDLICHEN AUTOMATEN MIT n STAATEN AKZEPTIERT WERDEN" - citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838

Michael Wehar

Vielen Dank an Sie beide, dass Sie meinen Fehler korrigiert und mir diesen Hinweis gegeben haben, der in der Tat relevant ist.

Luz

Antworten:

Nach Ishigami Y., Tani S. (1993) Die VC-Dimensionen endlicher Automaten mit n Zuständen, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , die VC-Dimension von Die Konzeptklasse von Zustands-DFAs über einem Alphabet der Größe ist Daraus folgt, dass es auf einem mindestens verschiedene Zustandsautomaten gibt $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$ -Briefalphabet. Die Obergrenze für die Anzahl solcher Automaten ergibt sich aus einem einfachen Zählargument (in der Veröffentlichung angegeben) und beträgt höchstens

2^{d}

$2^d$

Aryeh
quelle

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

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

m

$m$

Ich denke, dies zählt auch minimale DFAs, da die VC-Dimension repräsentationsunabhängig ist, zählt sie tatsächlich verschiedene Sprachen - was minimalen DFAs entspricht.

Aryeh

(m - 1)!

$(m-1)!$

(m - 1)!

$(m-1)!$

m^{m}

$m^m$

In der Tat, wenn Sie sich den Beweis von Thm ansehen. 3.2 In dem von mir verlinkten Artikel sehen Sie diesen genauen Ausdruck im Nenner.

Aryeh

(NB: Die in der akzeptierten Antwort angegebene Obergrenze ist besser oder gleich der hier angegebenen.)

In diesem Artikel wird eine Obergrenze vorgeschlagen, die in einem der vorherigen Kommentare angegeben ist: „ Zur Anzahl unterschiedlicher Sprachen, die von endlichen Automaten mit n Zuständen akzeptiert werden “ (2002, M. Domaratzki, D. Kisman, J. Shallit) .

In diesem Papier:

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

Wir interessieren uns für die Obergrenze für die $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
quelle