Cérny Vermutung C(n)<=n^3/3

Hallo:)

Ich bräuchte Hilfe bei diesem Beweis, weil ich hab bisher keine Ahnung, wie ich das zeigen soll:

Gegeben sei ein DFA A=(Q,∑,δ), wobei der Startzustand und Endzustand irrelevant sind.

δ: Q x∑ -> Q

p= δ(q,w)<=> p=qw

Ein Reset-Wort ist ein w aus ∑* mit |Q*w|= 1

P*w={q ∈ Q| ∃p∈ P: q=p*w}

A heißt synchronisierbar <=> ∃Reset-Wort w

C(n)={ |w| | w ist ein kürzestes Reset-Wort für ein A=(Q,∑,δ) mit |Q|=n}

Dabei wurde durch Herrn Cérny gezeigt: C(n)> (n-1)^2 offen ist noch die Gleichheit.

Ich soll jetzt zeigen:

C(n)<= n^3/3

Ich hoff einfach auf Ansätze und wäre sehr dankbar für Hilfe:)

Noch eine hilfreiche Quelle:

0 Antworten