Status das conjecturas de Cerny?

19

Um DFA possui uma palavra de sincronização se houver uma sequência que envie qualquer estado do DFA para um único estado. Em 'The Cerny Conjecture for Aperiodic Automata ”de AN Trahtman (Matemática Discreta e Ciência da Computação Teórica, vol. 9: 2, 2007, pp.3-10), ele escreveu:

Cerny conjeturou em 1964 que todo DFA sincronizável em estado n possui no máximo uma palavra de duração sincronizada .(n-1 1)2

Ele também escreveu: "no caso em que o gráfico subjacente do DFA aperiódico está fortemente conectado, esse limite superior foi recentemente aprimorado por Volkov, que reduziu a estimativa para .n(n+1 1)/6

  1. Alguém sabe o status atual das conjecturas de Cerny?

  2. E em qual trabalho Volkov obteve o resultado n (n + 1) / 6?

Obrigado por qualquer ponteiro ou link.

scaaahu
fonte
Depois de postar a pergunta, fiz uma pesquisa e encontrei a resposta da minha segunda pergunta, em que artigo Volkov obteve o resultado n (n + 1) / 6? A resposta é 'Sincronizando autômatos preservando uma cadeia de ordens parciais', notas de aula em ciência da computação, 2007, volume 4783/2007, 27-37, DOI: 10.1007 / 978-3-540-76336-9_5
scaaahu
8
você pode editar a pergunta para refletir isso.
Suresh Venkat

Respostas:

19

Trakhtman tem uma bibliografia sobre o problema, que aparentemente é mantido atualizado; então suponho que a pergunta de Černý permaneça não resolvida até hoje. O mesmo é afirmado na pesquisa recente de Volkov (LATA 2008), vinculada ao artigo da wikipedia citado na pergunta. Lá você encontra indicadores para alguns resultados parciais, por exemplo, para quais subclasses de linguagens regulares a conjectura é conhecida como verdadeira. Ainda mais recente é um trabalho de pesquisa de Ananichev, Gusev & Volkov (MFCS 2010) sobre um tópico relacionado, onde eles confirmam que a conjectura de Černý ainda está aberta agora (pelo menos a partir de maio de 2010).

Hermann Gruber
fonte
2
Em 2012, Trahtman enviou um artigo para o arXiv, onde apresenta um esforço para resolver a conjectura. Isso foi há mais de um ano atrás. Há notícias sobre a exatidão da prova?
molnarg
2
Na seção de comentários da versão atual (v7) da pré-impressão arXiv, o autor declara "13 páginas, exemplos, versão incorreta. A prova da conjectura Černý está errada": arxiv.org/abs/1202.4626
Hermann Gruber
3

consulte ArXiv: 1405.2435 cs.FL "O comprimento de uma palavra mínima de sincronização e a conjectura \ v {C} erny" com a história do estudo https://arxiv.org/pdf/1405.2435.pdf

trahtman
fonte
3
Seria melhor resumir a (s) principal (s) reivindicação (ões) do artigo - caso contrário, essa é uma resposta apenas de link.
chi
Piorado pelo fato de o link estar quebrado.
domotorp 6/04