Synchronizacja słowa

Ten rysunek przedstawia DFA z ośmioma stanami i dwoma symbolami wejściowymi, czerwonym i niebieskim. Słowo niebiesko-czerwony-czerwony-niebieski-czerwony-czerwony-niebieski-czerwony-czerwony jest słowem synchronizującym, które wysyła wszystkie stany do stanu żółtego; słowo blue-blue-red-blue-blue-red-blue-blue-red to kolejne słowo synchronizujące, które wysyła wszystkie stany do stanu zielonego.

W informatyce , a dokładniej w teorii deterministycznych automatów skończonych (DFA), słowo synchronizujące lub sekwencja resetowania to słowo w alfabecie wejściowym DFA, które wysyła dowolny stan DFA do jednego i tego samego stanu. Oznacza to, że jeśli zespół kopii DFA jest uruchamiany w różnych stanach i wszystkie kopie przetwarzają słowo synchronizujące, wszystkie zakończą się w tym samym stanie. Nie każdy DFA ma słowo synchronizujące; na przykład DFA z dwoma stanami, jeden dla słów o parzystej długości, a drugi dla słów o nieparzystej długości, nigdy nie może być zsynchronizowany.

Istnienie

Biorąc pod uwagę DFA, problem określenia, czy ma on słowo synchronizujące, można rozwiązać w czasie wielomianowym za pomocą twierdzenia Jána Černego. Proste podejście uwzględnia zestaw mocy stanów DFA i buduje skierowany wykres, w którym węzły należą do zestawu mocy, a skierowana krawędź opisuje działanie funkcji przejścia. Ścieżka od węzła wszystkich stanów do stanu pojedynczego pokazuje istnienie słowa synchronizującego. Ten algorytm jest wykładniczy w liczbie stanów. Algorytm wielomianowy powstaje jednak dzięki twierdzeniu Černego, które wykorzystuje podstrukturę problemu i pokazuje, że słowo synchronizujące istnieje wtedy i tylko wtedy, gdy każda para stanów ma słowo synchronizujące.

Długość

Nierozwiązany problem z matematyki :

Jeśli DFA ze $stanami ma słowo synchronizujące, czy musi mieć co$ długość ${\ displaystyle (n-1) ^ {2}}$ ?

(więcej nierozwiązanych problemów z matematyki)

Problem szacowania długości synchronizujących się słów ma długą historię i był stawiany niezależnie przez kilku autorów, ale powszechnie znany jest jako hipoteza Černego . W 1969 roku Ján Černý przypuszczał, że ( n - 1) ² jest górną granicą długości najkrótszego słowa synchronizującego dla dowolnego kompletnego DFA w stanie n (DFA z pełnym wykresem przejścia stanu ). Jeśli to prawda, byłoby ciasno: w swoim artykule z 1964 r. Černý przedstawił klasę automatów (indeksowanych liczbą n stanów), dla których najkrótsze słowa resetowania mają taką długość. Najlepsza znana górna granica to 0,1654 n ³ , daleko od dolnej granicy. Dla n -stanowych DFA w k -literowym alfabecie wejściowym algorytm Davida Eppsteina znajduje słowo synchronizujące o długości co najwyżej 11 n ^3/48 + O ( n ² ) i działa w złożoności czasowej O ( n ³ + kn ² ). Ten algorytm nie zawsze znajduje najkrótsze możliwe słowo synchronizujące dla danego automatu; jak pokazuje również Eppstein, problem znalezienia najkrótszego słowa synchronizującego jest NP-zupełny . Jednak dla specjalnej klasy automatów, w których wszystkie przejścia stanów zachowują cykliczny porządek stanów, opisuje inny algorytm z czasem O( kn ² ), który zawsze znajduje najkrótsze słowo synchronizujące, dowodzi, że te automaty zawsze mają słowo synchronizujące długości co najwyżej ( n − 1) ² (granica podana w przypuszczeniu Černego) i pokazuje przykłady automatów o tej szczególnej formie, których najkrótsze słowo synchronizujące ma długość dokładnie ( n − 1) ² .

Kolorowanie dróg

Problem kolorowania dróg to problem etykietowania krawędzi regularnego grafu skierowanego symbolami k -literowego alfabetu wejściowego (gdzie k jest stopniem zewnętrznym każdego wierzchołka) w celu utworzenia synchronizowalnego DFA. W 1970 roku Benjamin Weiss i Roy Adler przypuszczali , że każdy silnie połączony i aperiodyczny digraf regularny można oznaczyć w ten sposób; ich przypuszczenie zostało udowodnione w 2007 roku przez Abrahama Trahtmana .

Powiązane: Półgrupy transformacyjne

Półgrupa transformacji jest synchronizowana, jeśli zawiera element o randze 1, to znaczy element, którego obraz ma liczność 1. DFA odpowiada półgrupie transformacji z wyróżnionym zespołem generatorów.

Dalsza lektura

Rystsov, IC (2004), „Przypuszczenie Černego: retrospektywy i perspektywy”, Proc. praca. Automaty synchronizujące, Turku (WSA 2004) .
Jürgensen, H. (2008), "Synchronizacja", informacja i obliczenia , 206 (9–10): 1033–1044, doi : 10.1016/j.ic.2008.03.005
Volkov, Mikhail V. (2008), „Synchronizacja automatów i hipoteza Černego”, Proc. 2. Międzynarodowy konf. Teoria i zastosowania języka i automatów (LATA 2008) (PDF) , LNCS, obj. 5196, Springer-Verlag, s. 11–27