DFA의 상태를 단일 상태로 보내는 문자열이 있으면 DFA에 동기화 단어 가 있습니다. AN Trahtman (Discrete Mathematics and Theorytical Computer Science vol. 9 : 2, 2007, pp.3-10)의 ‘비 주기적 오토마타에 대한 Cerny 추측’에서 그는 다음과 같이 썼다.
Cerny는 1964 년에 모든 n- 상태 동기화 가능 DFA는 최대 길이 의 동기화 단어를 소유한다고 추측했다
(엔−1)2
.
“비 주기적 DFA의 기본 그래프가 강하게 연결되어있는 경우,이 상한값은 최근 Volkov에 의해 개선되어 추정치를 였습니다.
엔(엔+1)/6-
Cerny 추측의 현재 상태를 아는 사람이 있습니까?
-
그리고 어느 종이에서 Volkov가 결과 n (n + 1) / 6을 얻었습니까?
모든 포인터 또는 링크에 감사드립니다.
답변
Trakhtman은 문제에 대한 참고 문헌 을 가지고 있으며 , 이는 최신 상태로 유지됩니다. 그래서 나는 체 르네의 질문이 오늘까지 해결되지 않은 것으로 생각합니다. 질문에 인용 된 위키피디아 기사와 연결된 Volkov의 최근 조사 (LATA 2008)에서도 마찬가지입니다. 예를 들어, 정규 언어의 하위 클래스에 대한 추측이 맞는 것으로 알려진 일부 결과에 대한 포인터가 있습니다. 더 최근 에는 관련 주제에 관한 Ananichev, Gusev & Volkov (MFCS 2010) 의 연구 논문 이 있으며, 현재 체르니의 추측이 아직 열려 있다고 확인했다 (최소한 2010 년 5 월 현재).
답변
ArXiv 참조 : 1405.2435 cs.FL “최소한 동기화 단어의 길이와 \ v {C} erny 추측”연구의 이야기
https://arxiv.org/pdf/1405.2435.pdf