În informatică , mai precis, în teoria automatelor finite deterministe (DFA), cuvântul de sincronizare (sau secvența de contracție ) din alfabetul de intrare al automatului mapează toate stările sale la aceeași stare [1] . Adică, dacă un cuvânt începe pe ansamblul tuturor stărilor automatului, trecând prin toate arcele orientate cu aceeași viteză, toate căile se vor termina simultan în aceeași stare. Nu fiecare DFA are un cuvânt de sincronizare, de exemplu, un DFA cu două stări și cicluri de lungime doi nu pot fi niciodată sincronizate.
Problema estimării lungimii unui cuvânt sincronizat are o istorie lungă și a fost pusă independent de mai mulți autori, dar a devenit cunoscută pe scară largă sub numele de conjectura Cherny. În 1964, Jan Czerny [1] a sugerat că (N - 1) 2 este o limită superioară ascuțită a lungimii celui mai scurt cuvânt de sincronizare pentru orice DFA cu N stări și K muchii de ieșire multicolore de la fiecare vârf (un DFA cu un graficul de tranziție complet). Cerny, în 1964, a găsit o clasă de automate (cu numărul N de stări pentru orice N natural) al căror cuvânt de sincronizare cel mai scurt are această lungime. Cea mai cunoscută limită superioară pentru această lungime astăzi este (N 3 - N) / 6 și departe de limita inferioară.
Pentru un DFA cu stări N peste un alfabet de K caractere, algoritmul lui David Epstein găsește cuvântul de sincronizare în O (N 3 + n 2 k) timp și O(n 2 ) [2] spațiu de memorie . Această lucrare demonstrează, de asemenea, NP-completitudinea găsirii unui cuvânt sincronizat de lungime minimă.
Problema colorării drumului este problema colorării marginilor unui grafic direcționat obișnuit cu simbolurile (culorile) unui alfabet de intrare de simboluri K (unde K este, de asemenea, gradul exterior al fiecărui vârf) pentru a forma un DFA sincronizat. Benjamin Weiss și Roy Adler au presupus în 1970 că orice digraf puternic conectat cu un grad de exterior constant al fiecărui vârf și un cel mai mare divizor comun al lungimii tuturor ciclurilor egal cu unu are o colorare de sincronizare [3] . Conjectura lor a fost dovedită în 2007 de Abram Trakhtman [4] .