Status przypuszczenia Cerny'ego?

DFA ma słowo synchronizujące, jeśli istnieje ciąg znaków, który wysyła dowolny stan DFA do jednego stanu. W „The Cerny Conjecture for Aperiodic Automata” AN Trahtmana (Discrete Mathematics and Theoretical Computer Science vol. 9: 2, 2007, s. 3–10) napisał:

Cerny przypuszczał w 1964 r., Że każdy DFA synchronizowany w stanie n ma najwyżej synchronizowane słowo długości .$(n-1)^2$

Napisał także: „w przypadku, gdy podstawowy wykres aperiodycznego DFA jest silnie połączony, górna granica została ostatnio poprawiona przez Volkova, który zmniejszył oszacowanie do .$n(n + 1)/6$

1. Czy ktoś zna obecny stan przypuszczeń Cerny?

2. A w jakiej pracy Wołkow uzyskał wynik n (n + 1) / 6?

Dzięki za dowolny wskaźnik lub link.

Trakhtman ma bibliografię problemu, która jest najwyraźniej na bieżąco; więc przypuszczam, że pytanie Černego pozostaje nierozwiązane do dziś. To samo stwierdzono w niedawnej ankiecie Wołkowa (LATA 2008), do której link znajduje się w artykule na Wikipedii cytowanym w pytaniu. Znajdziesz tam wskaźniki do częściowych wyników, na przykład dla których podklas zwykłych języków wiadomo, że przypuszczenie jest prawdziwe. Jeszcze bardziej aktualny jest artykuł badawczy Ananiczowa, Gusiewa i Wołkowa (MFCS 2010) na pokrewny temat, w którym potwierdzają oni, że domysł Černý jest nadal otwarty (przynajmniej od maja 2010 r.).

patrz ArXiv: 1405.2435 cs.FL „Długość minimalnego słowa synchronizującego i hipoteza \ v {C} erny” z historią badań https://arxiv.org/pdf/1405.2435.pdf