A számítástechnikában , pontosabban a determinisztikus véges automaták (DFA) elméletében, az automata bemeneti ábécéjében lévő szinkronizáló szó (vagy összehúzó szekvencia ) az összes állapotát ugyanarra az állapotra képezi le [1] . Ez azt jelenti, hogy ha egy szó az automata összes állapotának együttesén kezdődik, és azonos sebességgel halad át az összes orientált íven, akkor az összes út egyidejűleg ugyanabban az állapotban végződik. Nem minden DFA-nak van szinkronizálási szava, például a két állapotú és kettő hosszúságú ciklusú DFA soha nem szinkronizálható.
A szinkronszó hosszának becslésének problémája hosszú múltra tekint vissza, és több szerző egymástól függetlenül is felvetette, de Cherny-sejtés néven vált széles körben ismertté. 1964-ben Jan Czerny [1] azt javasolta, hogy az (N - 1) 2 a legrövidebb szinkronszó hosszának éles felső korlátja bármely N állapotú DFA és K többszínű kimenő éllel minden csúcsból (egy DFA teljes átmeneti grafikon). Cerny még 1964-ben talált egy automataosztályt (amelynek N állapota van bármely természetes N-hez), amelynek a legrövidebb szinkronszava ilyen hosszúságú. Ennek a hossznak a legismertebb felső határa ma (N 3 - N) / 6, és messze van az alsó korláttól.
Egy K karakterből álló ábécé feletti N állapotú DFA esetén David Epstein algoritmusa megtalálja a szinkronszót O (N 3 + n 2 k) időben és O(n 2 ) [2] memóriatérben . Ez a cikk azt is bizonyítja , hogy a minimális hosszúságú szinkronszó megtalálásának NP-teljessége .
Az útszínezési probléma az a probléma, hogy egy szabályos irányított gráf éleit egy K szimbólumból álló bemeneti ábécé szimbólumaival (színeivel) színezzük (ahol K egyben az egyes csúcsok külső foka is), hogy szinkronizált DFA-t hozzunk létre. Benjamin Weiss és Roy Adler 1970-ben sejtette, hogy minden olyan erősen összefüggő digráfnak, amelynek minden csúcsa állandó kilépési foka van, és az összes ciklus hosszának eggyel egyenlő legnagyobb közös osztója van, szinkronizáló színezésű [3] . Sejtésüket 2007-ben igazolta Abram Trakhtman [4] .