단어 동기화
Synchronizing word
컴퓨터 과학에서 더 정확히 말하면, 결정론적 유한 자동자(DFA) 이론에서, 동기화하는 단어 또는 리셋 시퀀스는 DFA의 입력 알파벳에 있는 단어로, DFA의 어떤 상태도 하나의 동일한 상태로 보낸다.[1]즉, DFA 사본의 앙상블이 각각 다른 주에서 시작되어 모든 사본들이 동기화 단어를 처리하면 모두 같은 상태로 끝난다는 것이다.모든 DFA가 동기화 단어를 가지고 있는 것은 아니다. 예를 들어, 짝수 길이의 단어와 홀수 길이의 단어 두 개의 상태를 가진 DFA는 결코 동기화할 수 없다.
존재
DFA를 부여하면, 얀 체르난에 의한 정리를 이용하여 다항 시간[2] 내에 동시어 유무를 판정하는 문제를 해결할 수 있다.간단한 접근방식은 DFA의 상태 집합을 고려하고, 노드가 전원 집합에 속하는 방향 그래프를 작성하며, 방향 에지는 전환 기능의 작용을 설명한다.모든 상태의 노드에서 싱글톤 상태까지의 경로는 동기화 단어의 존재를 보여준다.이 알고리즘은 상태 수가 기하급수적이다.그러나 다항 알고리즘은 문제의 하부 구조를 악용하는 체르누스의 정리 때문에 발생하며, 각 상태 쌍이 동기화 단어를 갖는 경우에만 동기화 단어가 존재함을 보여준다.
길이
n 
단어 동기화 길이를 추정하는 문제는 오랜 역사를 가지고 있으며 여러 저자가 독자적으로 제기하였지만 흔히 체르누스 추측이라고 알려져 있다.1969년, 얀 체르누스는 (n - 1)이 2n-state complete DFA(완전한 상태 전이 그래프를 가진 DFA)에 대한 최단 동기화 단어의 길이에 대한 상한이라고 추측했다.[3]만약 이것이 사실이라면, 그것은 빠듯할 것이다: 체르노는 1964년 논문에서 가장 짧은 리셋 단어의 길이가 이 길이를 갖는 오토마타(n개 주 수로 색인화됨)의 부류를 보여주었다.[4]알려진 최고 상한은 (n-n 3 )/6으로, 하한과는 거리가 멀다.[5]k 문자 입력 알파벳을 통한 n-state DFA의 경우, 데이비드 엡스타인의 알고리즘은 최대 11n3/48 + O(n2)에서 동기화하는 길이의 단어를 찾아내고 시간 복잡도 O(n3+kn2)로 실행된다.이 알고리즘은 항상 주어진 자동화에 대해 가능한 최단 동기화 단어를 찾는 것은 아니다. 엡스타인 또한 알 수 있듯이, 최단 동기화 단어를 찾는 문제는 NP-완전하다.하지만, 오토 머터 모든 상태 변환은 각국의 순환 질서를 보존하고 특별한 클래스에 대해 그는 이러한 오토 머터 항상 가장(n− 1)2(이 튀어 Černý의 추측에 주어진)에서, 그리고 전 남편 긴synchronizing 말이 있어 증명하는 것 시간 O(kn2)은 항상 짧은 동기 말 발견과 함께 다른 알고리즘에 대해 설명합니다.h가장 짧은 동기화 단어의 길이가 정확하게 (n - 1)인 이 특별한 형태의 자동타 ibits의 예.2[2]
도로색소
도로 채색 문제는 동기화할 수 있는 DFA를 형성하기 위해 k자 입력 알파벳 기호(여기서 k는 각 정점의 도)로 일반 방향 그래프의 가장자리에 라벨을 붙이는 문제다.1970년 벤자민 와이스와 로이 애들러에 의해 강하게 연결되어 있고 주기적인 일반 디그람은 이런 식으로 라벨을 붙일 수 있다고 추측되었다; 그들의 추측은 Avraham Trahtman에 의해 2007년에 증명되었다.[6][7]
관련:변환 세미그룹
변환 세미그룹은 순위 1의 요소, 즉 이미지가 카디널리티 1인 요소를 포함하는 경우 동기화되고 있다.[8]DFA는 고유 생성기가 설정된 변환 세미그룹에 해당한다.
참조
- ^ 아브라함 트라크트만:오토마타 동기화, 알고리즘, 세니 추측2010년 5월 15일 접속.
- ^ a b Eppstein, David (1990), "Reset Sequences for Monotonic Automata" (PDF), SIAM Journal on Computing, 19 (3): 500–510, doi:10.1137/0219033.
- ^ Volkov, Mikhail V. (2008), "Synchronizing Automata and the Černý Conjecture", Proc. 2nd Int'l. Conf. Language and Automata Theory and Applications (LATA 2008), LNCS, vol. 5196, Springer-Verlag, pp. 11–27, doi:10.1007/978-3-540-88282-4_4; 특히 페이지 19를 보다.
- ^ Černý, Ján (1964), "Poznámka k homogénnym experimentom s konečnými automatmi" (PDF), Matematicko-fyzikálny časopis Slovenskej Akadémie Vied, 14: 208–216 (슬로바키아에서).
- ^ 핀, J.-E.(1983년),"두 조합 문제 오토 머터 이론에서 발생하는에"(PDF), 것이 Combinatorial수학(Marseille-Luminy, 1981년), North-Holland 수학입니다.스터드., 75vol., 암스테르담:끝에 North-Holland, 니코틴산. 535–548, doi:10.1016(08)73432-7, MR0841339, 보십시오 노트 프랑클, P.(1982년),"셋트 중 2가족을 위한 극치 문제", 유럽 저널 Combinatorics의, 3(2):125–127, doi:10.1016(82)80025-5, MR0670845여 개선을 가리킨다.
- ^ Adler, R. L.; Weiss, B. (1970), "Similarity of automorphisms of the torus", Memoirs of the American Mathematical Society, 98.
- ^ Trahtman, A. N. (2009), "The road coloring problem", Israel Journal of Mathematics, 172: 51–60, arXiv:0709.0099, doi:10.1007/s11856-009-0062-5, MR 2534238
- ^ Cameron, Peter (2013), Permutation groups and transformation semigroups (PDF).
추가 읽기
- Rystsov, I. C. (2004), "Černý's conjecture: retrospects and prospects", Proc. Worksh. Synchronizing Automata, Turku (WSA 2004).
- Jürgensen, H. (2008), "Synchronization", Information and Computation, 206 (9–10): 1033–1044, doi:10.1016/j.ic.2008.03.005
- Volkov, Mikhail V. (2008), "Synchronizing Automata and the Černý Conjecture", Proc. 2nd Int'l. Conf. Language and Automata Theory and Applications (LATA 2008) (PDF), LNCS, vol. 5196, Springer-Verlag, pp. 11–27
