DFA имеет синхронизирующее слово, если есть строка, которая отправляет любое состояние DFA в одно состояние. В «Гипотезе Черни для апериодических автоматов» А. Н. Трахтмана («Дискретная математика и теоретическая информатика», том 9: 2, 2007, с. 3-10) он писал:
В 1964 году Черни предположил, что каждое синхронизируемое по N-состоянию DFA обладает словом синхронизации длиной не более .
Он также писал: «В случае, когда основной график апериодической ДФА сильно связан, эта верхняя граница была недавно улучшена Волковым, который сократил оценку до .
Кто-нибудь знает текущее состояние гипотезы Черного?
И в какой статье Волков получил результат n (n + 1) / 6?
Спасибо за любой указатель или ссылку.
Ответы:
У Трахтмана есть библиография по этой проблеме, которая, видимо, постоянно обновляется; поэтому я полагаю, что вопрос Черны остается нерешенным до сегодняшнего дня. То же самое говорится в недавнем опросе Волкова (LATA 2008), связанном со статьей в Википедии, процитированной в этом вопросе. Там вы найдете указатели на некоторые частичные результаты, например, для каких подклассов обычных языков гипотеза, как известно, верна. Еще более свежим является исследовательский документ Ananichev, Gusev & Volkov (MFCS 2010) на смежную тему, в котором они подтверждают, что гипотеза Черны до сих пор остается открытой (по крайней мере, по состоянию на май 2010 года).
источник
см. ArXiv: 1405.2435 cs.FL «Длина минимального синхронизирующего слова и ошибочная гипотеза \ v {C}» с историей изучения https://arxiv.org/pdf/1405.2435.pdf
источник