DFA의 상태를 단일 상태로 보내는 문자열이 있으면 DFA에 동기화 단어 가 있습니다. AN Trahtman (Discrete Mathematics and Theorytical Computer Science vol. 9 : 2, 2007, pp.3-10)의 ‘비 주기적 오토마타에 대한 Cerny 추측’에서 그는 다음과 같이 썼다.

Cerny는 1964 년에 모든 n- 상태 동기화 가능 DFA는 최대 길이 의 동기화 단어를 소유한다고 추측했다
.( n – 1 )2

$(엔-1{)}^2$

$(n-1)^2$

“비 주기적 DFA의 기본 그래프가 강하게 연결되어있는 경우,이 상한값은 최근 Volkov에 의해 개선되어 추정치를 였습니다.n ( n + 1 ) / 6

$n(n + 1)/6$

1. Cerny 추측의 현재 상태를 아는 사람이 있습니까?

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

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

답변