Tietojenkäsittelytieteessä , tarkemmin sanottuna, determinististen äärellisten automaattien (DFA) teoriassa, synkronointisana (tai supistussekvenssi ) automaatin syöteaakkostossa kartoittaa kaikki sen tilat samaan tilaan [1] . Eli jos sana alkaa automaatin kaikkien tilojen joukosta, joka kulkee kaikkien suuntautuneiden kaarien läpi samalla nopeudella, kaikki polut päättyvät samanaikaisesti samaan tilaan. Jokaisella DFA:lla ei ole synkronointisanaa, esimerkiksi DFA:ta, jossa on kaksi tilaa ja kahden pituisia jaksoja, ei voida koskaan synkronoida.
Synkronointisanan pituuden arvioinnin ongelmalla on pitkä historia, ja useat kirjoittajat ovat esittäneet sen itsenäisesti, mutta siitä on tullut laajalti tunnettu Chernyn arveluina. Vuonna 1964 Jan Czerny [1] ehdotti, että (N - 1) 2 on terävä yläraja lyhimmän synkronointisanan pituudelle mille tahansa DFA:lle, jossa on N tilaa ja K moniväristä lähtevää reunaa kustakin kärjestä (DFA, jossa on täydellinen siirtymäkaavio). Cerny löysi vuonna 1964 automaattien luokan (jossa on N tilaa mille tahansa luonnolliselle N:lle), jonka lyhimmällä synkronointisanalla on tämä pituus. Tämän pituuden tunnetuin yläraja nykyään on (N 3 - N) / 6 ja kaukana alarajasta.
N-tilan DFA:lle K merkin aakkoston yli David Epsteinin algoritmi löytää synkronointisanan O (N 3 + n 2 k) ajalta ja O(n 2 ) [2] muistitilasta . Tämä artikkeli todistaa myös NP-täydellisyyden minimipituisen synkronointisanan löytämisessä.
Tien väritysongelma on ongelma säännöllisen suunnatun graafin reunojen värittämisessä K-symbolin syöteaakkoston symboleilla (väreillä) (jossa K on myös kunkin kärjen ulkoaste) synkronoidun DFA:n muodostamiseksi. Benjamin Weiss ja Roy Adler arvelivat vuonna 1970, että jokaisella vahvasti kytketyllä digraafilla, jolla on vakio kunkin kärjen ulkoastetta ja kaikkien syklien pituuksien suurin yhteinen jakaja yhtä suuri kuin yksi, on synkronoitava väritys [3] . Abram Trakhtman todisti heidän olettamuksensa vuonna 2007 [4] .