Inom datavetenskap , närmare bestämt, i teorin om deterministiska finita automater (DFA), mappar synkroniseringsordet (eller kontraktionssekvensen ) i automatens inmatningsalfabet alla dess tillstånd till samma tillstånd [1] . Det vill säga, om ett ord börjar på ensemblen av alla tillstånd i automaten och passerar genom alla orienterade bågar med samma hastighet, kommer alla banor att sluta samtidigt i samma tillstånd. Inte varje DFA har ett synkord, till exempel kan en DFA med två tillstånd och cykler med längd två aldrig synkroniseras.
Problemet med att uppskatta längden på ett synkord har en lång historia och har framställts oberoende av flera författare, men har blivit allmänt känt som Cherny-förmodan. 1964 föreslog Jan Czerny [1] att (N - 1) 2 är en skarp övre gräns för längden av det kortaste synkordet för alla DFA med N tillstånd och K flerfärgade utgående kanter från varje vertex (en DFA med en komplett övergångsdiagram). Cerny, redan 1964, hittade en klass av automater (med antalet N tillstånd för alla naturliga N) vars kortaste synkroniseringsord har denna längd. Den mest kända övre gränsen för denna längd idag är (N 3 - N) / 6 och långt från den nedre gränsen.
För en DFA i N-tillstånd över ett alfabet med K tecken, hittar David Epsteins algoritm synkroniseringsordet i O (N 3 + n 2 k) tid och O(n 2 ) [2] minnesutrymme . Detta dokument bevisar också NP-fullständigheten för att hitta ett synkord med minsta längd.
Vägfärgningsproblemet är problemet med att färga kanterna på en vanlig riktad graf med symbolerna (färgerna) av ett inmatat alfabet av K-symboler (där K också är utgraden av varje vertex) för att bilda en synkroniserad DFA. Benjamin Weiss och Roy Adler förmodade 1970 att varje starkt sammankopplad digraf med en konstant utgrad av varje vertex och en största gemensamma divisor av längderna av alla cykler lika med en har en synkroniserande färgning [3] . Deras gissningar bevisades 2007 av Abram Trakhtman [4] .