Cerny 추측의 상태? 있습니다. AN Trahtman

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
  1. Cerny 추측의 현재 상태를 아는 사람이 있습니까?

  2. 그리고 어느 종이에서 Volkov가 결과 n (n + 1) / 6을 얻었습니까?

모든 포인터 또는 링크에 감사드립니다.



답변

Trakhtman은 문제에 대한 참고 문헌 을 가지고 있으며 , 이는 최신 상태로 유지됩니다. 그래서 나는 체 르네의 질문이 오늘까지 해결되지 않은 것으로 생각합니다. 질문에 인용 된 위키피디아 기사와 연결된 Volkov의 최근 조사 (LATA 2008)에서도 마찬가지입니다. 예를 들어, 정규 언어의 하위 클래스에 대한 추측이 맞는 것으로 알려진 일부 결과에 대한 포인터가 있습니다. 더 최근 에는 관련 주제에 관한 Ananichev, Gusev & Volkov (MFCS 2010) 의 연구 논문 이 있으며, 현재 체르니의 추측이 아직 열려 있다고 확인했다 (최소한 2010 년 5 월 현재).