I datalogi , mere præcist, i teorien om deterministiske endelige automater (DFA), kortlægger synkroniseringsordet (eller kontraktionssekvensen ) i automatens input-alfabet alle dets tilstande til den samme tilstand [1] . Det vil sige, at hvis et ord starter på ensemblet af alle automatens tilstande og passerer gennem alle orienterede buer med samme hastighed, vil alle stier ende samtidigt i samme tilstand. Ikke alle DFA har et synkroniseringsord, for eksempel kan en DFA med to tilstande og cyklusser af længde to aldrig synkroniseres.
Problemet med at estimere længden af et synkroniseringsord har en lang historie og er blevet stillet uafhængigt af flere forfattere, men er blevet almindeligt kendt som Cherny-formodningen. I 1964 foreslog Jan Czerny [1] , at (N - 1) 2 er en skarp øvre grænse for længden af det korteste synkroniseringsord for enhver DFA med N tilstande og K flerfarvede udgående kanter fra hvert toppunkt (en DFA med en komplet overgangsgraf). Cerny fandt tilbage i 1964 en klasse af automater (med antallet N af tilstande for ethvert naturligt N), hvis korteste synkroniseringsord har denne længde. Den bedst kendte øvre grænse for denne længde i dag er (N 3 - N) / 6 og langt fra den nedre grænse.
For en N-tilstand DFA over et alfabet på K tegn, finder David Epsteins algoritme synkroniseringsordet i O (N 3 + n 2 k) tid og O(n 2 ) [2] hukommelsesplads . Dette papir beviser også NP-fuldstændigheden af at finde et synkroniseringsord med minimum længde.
Vejfarveproblemet er problemet med at farve kanterne af en regulær rettet graf med symbolerne (farverne) af et input-alfabet af K-symboler (hvor K også er udgraden af hvert toppunkt) for at danne en synkroniseret DFA. Benjamin Weiss og Roy Adler formodede i 1970, at enhver stærkt forbundet digraf med en konstant udgrad af hvert vertex og en største fælles divisor af længderne af alle cyklusser lig med én har en synkroniserende farve [3] . Deres formodning blev bevist i 2007 af Abram Trakhtman [4] .