Status der Cerny-Vermutung?

19

Ein DFA verfügt über ein Synchronisationswort, wenn eine Zeichenfolge vorhanden ist, die einen beliebigen Status des DFA an einen einzelnen Status sendet. In "The Cerny Conjecture for Aperiodic Automata" von AN Trahtman (Diskrete Mathematik und Theoretische Informatik, Band 9: 2, 2007, S. 3-10) schrieb er:

1964 vermutete Cerny, dass jeder mit n Zuständen synchronisierbare DFA ein Synchronisationswort mit einer Länge von höchstens .(n−1)2

Er schrieb auch: "Wenn der zugrunde liegende Graph des aperiodischen DFA stark verknüpft ist, wurde diese Obergrenze kürzlich von Volkov verbessert, der die Schätzung auf reduziert hat .n(n+1)/6

  1. Kennt jemand den aktuellen Stand der Cerny-Vermutung?

  2. Und in welchem ​​Papier erhielt Volkov das Ergebnis n (n + 1) / 6?

Vielen Dank für jeden Hinweis oder Link.

fl.formal-languages automata-theory open-problem synchronization scaaahu
quelle
Nachdem ich die Frage gestellt hatte, machte ich eine Suche und fand die Antwort auf meine zweite Frage. In welcher Arbeit erhielt Volkov das Ergebnis n (n + 1) / 6? Die Antwort ist 'Synchronisieren von Automata Die Erhaltung einer Kette von Teilaufträge' Lecture Notes in Computer Science, 2007, Band 4783/2007, 27-37, DOI: 10.1007 / 978-3-540-76336-9_5
scaaahu
8
Sie können die Frage bearbeiten, um dies widerzuspiegeln.
Suresh Venkat

Antworten:

19

Trakhtman hat eine Bibliographie zu diesem Problem, die offenbar auf dem neuesten Stand gehalten wird. Ich nehme an, die Frage von Černý ist bis heute ungelöst. Dasselbe wird in Wolkows jüngster Umfrage (LATA 2008) festgestellt, die mit dem in der Frage zitierten Wikipedia-Artikel verknüpft ist. Dort finden Sie Hinweise auf einige Teilergebnisse, zum Beispiel, für welche Unterklassen regulärer Sprachen die Vermutung als wahr bekannt ist. Noch aktueller ist ein Forschungsbericht von Ananichev, Gusev & Volkov (MFCS 2010) zu einem verwandten Thema, in dem bestätigt wird, dass die Vermutung von Černý noch offen ist (zumindest ab Mai 2010).

Hermann Gruber
quelle
2
Im Jahr 2012 hat Trahtman ein Paper zu arXiv hochgeladen , in dem er einen Versuch vorstellt, die Vermutung zu lösen. Das war vor mehr als einem Jahr. Gibt es Neuigkeiten zur Richtigkeit des Beweises?
Molnarg
2
Im Kommentarbereich zur aktuellen Version (v7) des Vorabdrucks von arXiv gibt der Autor "13 Seiten, Beispiele, falsche Version. Der Beweis der Černý-Vermutung ist falsch" an: arxiv.org/abs/1202.4626
Hermann Gruber
3

siehe ArXiv: 1405.2435 cs.FL "Die Länge eines minimalen Synchronisationsworts und die \ v {C} erny-Vermutung" mit der Geschichte der Studie https://arxiv.org/pdf/1405.2435.pdf

Trahtman
quelle
3
Es wäre besser, die Hauptansprüche des Papiers zusammenzufassen - dies ist ansonsten eine Antwort nur auf Links.
Chi
Erschwerend kommt hinzu, dass die Verbindung unterbrochen ist.
Domotorp