V informatice , přesněji v teorii deterministických konečných automatů (DFA), synchronizační slovo (neboli kontrakce sekvence ) ve vstupní abecedě automatu mapuje všechny jeho stavy do stejného stavu [1] . To znamená, že pokud slovo začíná na souboru všech stavů automatu a prochází všemi orientovanými oblouky stejnou rychlostí, všechny cesty skončí současně ve stejném stavu. Ne každé DFA má synchronizační slovo, například DFA se dvěma stavy a cykly o délce dva nelze nikdy synchronizovat.
Problém odhadu délky synchronizačního slova má dlouhou historii a byl položen nezávisle několika autory, ale stal se široce známým jako Chernyho domněnka. V roce 1964 Jan Czerny [1] navrhl, že (N - 1) 2 je ostrá horní hranice délky nejkratšího synchronizačního slova pro libovolné DFA s N stavy a K vícebarevnými odchozími hranami z každého vrcholu (DFA s kompletní přechodový graf). Černý v roce 1964 našel třídu automatů (s počtem N stavů pro libovolné přirozené N), jejichž nejkratší synchronizační slovo má tuto délku. Nejznámější horní hranice pro tuto délku je dnes (N 3 - N) / 6 a daleko od dolní hranice.
Pro N-stavové DFA přes abecedu K znaků algoritmus Davida Epsteina najde synchronizační slovo v čase O (N 3 + n 2 k) a paměťovém prostoru O(n 2 ) [2] . Tento článek také dokazuje NP-úplnost nalezení synchronizačního slova minimální délky.
Problémem zbarvení silnice je problém obarvení hran pravidelného orientovaného grafu symboly (barvami) vstupní abecedy K symbolů (kde K je také přesah každého vrcholu) za účelem vytvoření synchronizovaného DFA. Benjamin Weiss a Roy Adler se v roce 1970 domnívali, že každý silně souvislý digraf s konstantním přesahem každého vrcholu a největším společným dělitelem délek všech cyklů rovným jedné má synchronizační zbarvení [3] . Jejich domněnku dokázal v roce 2007 Abram Trakhtman [4] .