Estado de la conjetura de Cerny?

19

Un DFA tiene una palabra de sincronización si hay una cadena que envía cualquier estado del DFA a un solo estado. En 'La conjetura de Cerny para autómatas aperiódicos ”por AN Trahtman (Matemática discreta y ciencias de la computación teórica vol. 9: 2, 2007, pp.3-10), escribió:

Cerny conjeturó en 1964 que cada DFA sincronizable de n estados posee una palabra de longitud de sincronización como máximo .(n−1)2

También escribió, "en el caso de que el gráfico subyacente del DFA aperiódico esté fuertemente conectado, este límite superior ha sido mejorado recientemente por Volkov, quien redujo la estimación a .n(n+1)/6

  1. ¿Alguien sabe el estado actual de la conjetura de Cerny?

  2. ¿Y en qué papel Volkov obtuvo el resultado n (n + 1) / 6?

Gracias por cualquier puntero o enlace.

fl.formal-languages automata-theory open-problem synchronization scaaahu
fuente
Después de publicar la pregunta, hice una búsqueda y encontré la respuesta de mi segunda pregunta, ¿en qué papel Volkov obtuvo el resultado n (n + 1) / 6? La respuesta es 'Sincronizar autómatas preservando una cadena de órdenes parciales' Notas de conferencia en Ciencias de la Computación, 2007, Volumen 4783/2007, 27-37, DOI: 10.1007 / 978-3-540-76336-9_5
scaaahu
8
puedes editar la pregunta para reflejar esto.
Suresh Venkat

Respuestas:

19

Trakhtman tiene una bibliografía sobre el problema, que aparentemente se mantiene actualizada; así que supongo que la pregunta de Černý sigue sin resolverse hasta hoy. Lo mismo se afirma en la encuesta reciente de Volkov (LATA 2008) vinculada desde el artículo de wikipedia citado en la pregunta. Allí encontrará punteros a algunos resultados parciales, por ejemplo, para qué subclases de lenguajes regulares se sabe que la conjetura es cierta. Aún más reciente es un trabajo de investigación de Ananichev, Gusev y Volkov (MFCS 2010) sobre un tema relacionado, donde confirman que la conjetura de Černý todavía está abierta ahora (al menos a partir de mayo de 2010).

Hermann Gruber
fuente
2
En 2012, Trahtman subió un artículo a arXiv, donde presenta un esfuerzo para resolver la conjetura. Esto fue hace más de un año. ¿Hay alguna noticia sobre la exactitud de la prueba?
molnarg
2
En la sección de comentarios sobre la versión actual (v7) de la preimpresión arXiv, el autor declara "13 páginas, ejemplos, versión incorrecta. La prueba de la conjetura de Černý es incorrecta": arxiv.org/abs/1202.4626
Hermann Gruber
3

ver ArXiv: 1405.2435 cs.FL "La longitud de una palabra de sincronización mínima y la conjetura \ v {C} erny" con la historia de estudio https://arxiv.org/pdf/1405.2435.pdf

trahtman
fuente
3
Sería mejor resumir los reclamos principales del documento; de lo contrario, esta es una respuesta de solo enlace.
chi
Empeorado por el hecho de que el enlace está roto.
domotorp