Statut de la conjecture de Cerny?

19

Un DFA a un mot de synchronisation s'il existe une chaîne qui envoie n'importe quel état du DFA à un seul état. Dans «La conjecture de Cerny pour les automates apériodiques» de AN Trahtman (Mathématiques discrètes et informatique théorique vol. 9: 2, 2007, pp. 3-10), il écrit:

Cerny a conjecturé en 1964 que chaque DFA synchronisable à n états possède au plus un mot de synchronisation de longueur .(n−1)2

Il a également écrit: "dans le cas où le graphique sous-jacent du DFA apériodique est fortement connecté, cette limite supérieure a été récemment améliorée par Volkov qui a réduit l'estimation à .n(n+1)/6

  1. Quelqu'un connaît-il l'état actuel de la conjecture de Cerny?

  2. Et dans quel papier Volkov a obtenu le résultat n (n + 1) / 6?

Merci pour tout pointeur ou lien.

fl.formal-languages automata-theory open-problem synchronization scaaahu
la source
Après avoir posté la question, j'ai fait une recherche et trouvé la réponse à ma deuxième question, dans laquelle le papier Volkov a obtenu le résultat n (n + 1) / 6? La réponse est «Synchronisation des automates préservant une chaîne d'ordres partiels», notes de cours en informatique, 2007, volume 4783/2007, 27-37, DOI: 10.1007 / 978-3-540-76336-9_5
scaaahu,
8
vous pouvez modifier la question pour refléter cela.
Suresh Venkat

Réponses:

19

Trakhtman a une bibliographie sur le problème, qui est apparemment tenue à jour; donc je suppose que la question de Černý reste en suspens jusqu'à aujourd'hui. La même chose est indiquée dans la récente enquête de Volkov (LATA 2008) liée à l'article de Wikipédia cité dans la question. Vous y trouverez des pointeurs vers des résultats partiels, par exemple, pour quelles sous-classes de langues régulières la conjecture est connue pour être vraie. Encore plus récent est un document de recherche d'Ananichev, Gusev et Volkov (MFCS 2010) sur un sujet connexe, où ils confirment que la conjecture de Černý est toujours ouverte maintenant (au moins en mai 2010).

Hermann Gruber
la source
2
En 2012, Trahtman a téléchargé un article sur arXiv, où il présente un effort pour résoudre la conjecture. C'était il y a plus d'un an. Y a-t-il des nouvelles sur l'exactitude de la preuve?
molnarg
2
Dans la section des commentaires sur la version actuelle (v7) de la préimpression arXiv, l'auteur déclare "13 pages, exemples, mauvaise version. La preuve de la conjecture de Černý est fausse": arxiv.org/abs/1202.4626
Hermann Gruber
3

voir ArXiv: 1405.2435 cs.FL "La longueur d'un mot de synchronisation minimal et la conjecture \ v {C} erny" avec l'histoire de l'étude https://arxiv.org/pdf/1405.2435.pdf

trahtman
la source
3
Il serait préférable de résumer les principales revendications du document - il s'agit autrement d'une réponse uniquement liée à un lien.
chi
Aggravé par le fait que le lien est rompu.
domotorp