Synchronizace slova - Synchronizing word

Synchronizaci slov v teorii synchronizovaných kódů viz Samosynchronizační kód § Synchronizace slova.
Tento výkres představuje DFA s osmi stavy a dvěma vstupními symboly, červenými a modrými. Slovo modrá-červená-červená-modrá-červená-červená-modrá-červená-červená je synchronizační slovo, které odesílá všechny stavy do žlutého stavu; slovo modrá-modrá-červená-modrá-modrá-červená-modrá-modrá-červená je další synchronizační slovo, které odesílá všechny stavy do zeleného stavu.

v počítačová věda, přesněji, v teorii deterministické konečné automaty (DFA), a synchronizace slova nebo resetovat sekvenci je slovo ve vstupní abecedě DFA, které odesílá jakýkoli stav DFA do jednoho a stejného stavu.[1] To znamená, že pokud je soubor kopií DFA každý spuštěn v různých stavech a všechny kopie zpracovávají synchronizační slovo stejnou rychlostí, všechny nakonec dosáhnou stejného stavu jako každý jiný ve stejnou dobu jako navzájem. Ne každý DFA má synchronizační slovo; například DFA se dvěma stavy, jedním pro slova sudé délky a druhým pro slova liché délky, nelze nikdy synchronizovat.

Existence

Vzhledem k DFA lze problém určení, zda má synchronizační slovo, vyřešit v polynomiální čas[2] pomocí věty podle Jána Černého. Jednoduchý přístup uvažuje o množině stavů DFA a vytváří směrovaný graf, kde uzly patří do množiny, a směrovaná hrana popisuje akci přechodové funkce. Cesta z uzlu všech stavů do stavu ojedinělých ukazuje existenci synchronizačního slova. Tento algoritmus je exponenciální v počtu států. Výsledkem je polynomiální algoritmus, který je dán černou větou, která využívá podstrukturu problému a ukazuje, že synchronizační slovo existuje právě tehdy, má-li synchronizační slovo každá dvojice stavů.

Délka

Question, Web Fundamentals.svgNevyřešený problém v matematice:
Pokud má DFA synchronizační slovo, musí mít maximálně jedno dlouhé ?
(více nevyřešených úloh z matematiky)

Problém odhadu délky synchronizace slov má dlouhou historii a byl položen nezávisle několika autory, ale je běžně známý jako Černý dohad. V roce 1964 Ján Černý domníval se, že (n − 1)2 je horní hranice pro délku nejkratšího synchronizačního slova pro libovolné n-state kompletní DFA (DFA s kompletní stavový přechodový graf ).[1][3][ověření se nezdařilo – viz diskuse] Pokud je to pravda, bylo by to těsné: ve své práci z roku 1964 Černý vystavil třídu automatů (indexovaných číslem n států), pro které mají nejkratší resetovací slova tuto délku. Nejlepší známá horní hranice je (n 3 - n) / 6, daleko od spodní hranice.[4] Pro n-státní DFA nad a k- abeceda pro zadávání písmen, algoritmus podle David Eppstein najde synchronizační slovo o délce maximálně 11n3/48 + Ó (n2) a běží dovnitř časová složitost Ó (n3+kn2). Tento algoritmus ne vždy najde nejkratší možné synchronizační slovo pro daný automat; jak také ukazuje Eppstein, problém hledání nejkratšího synchronizačního slova je NP-kompletní. Pro speciální třídu automatů, ve kterých všechny přechody stavů zachovávají cyklický řád států popisuje jiný algoritmus s časem O (kn2), který vždy najde nejkratší synchronizační slovo, dokazuje, že tyto automaty vždy mají maximálně synchronizační slovo délky (n − 1)2 (vazba uvedená v Černém domněnce) a vykazuje příklady automatů s tímto zvláštním tvarem, jehož nejkratší synchronizační slovo má délku přesně (n − 1)2.[2]

Silniční zbarvení

The problém zbarvení silnice je problém označování hran a pravidelný řízený graf se symboly a k- abeceda pro zadávání písmen (kde k je překonat každého vrcholu) za účelem vytvoření synchronizovatelné DFA. To bylo se domnívalo v roce 1970 Benjamin Weiss a Roy Adler že nějaké silně propojený a neperiodické takto lze označit běžný digraf; jejich domněnka byla v roce 2007 prokázána Avraham Trahtman.[5][6]

Související: Transformační poloskupiny

A transformační poloskupina je synchronizace pokud obsahuje prvek 1. úrovně, tj. prvek, jehož obraz má mohutnost 1.[7] DFA odpovídá transformační poloskupině s rozlišenou generátorovou sadou.

Reference

  1. ^ A b Avraham Trakhtman: Synchronizační automaty, algoritmy, Černý dohad. Zpřístupněno 15. května 2010.
  2. ^ A b Eppstein, David (1990), „Resetovat sekvence pro monotónní automaty“ (PDF), SIAM Journal on Computing, 19 (3): 500–510, doi:10.1137/0219033.
  3. ^ Černý, J. (1964), "Poznámka k homogénnym experimentům s konečnými automaty" (PDF), Matematicko-fyzikálny časopis Slovenskej Akadémie Vied, 14: 208–216 (ve slovenštině).
  4. ^ https://arxiv.org/abs/1104.2409v7 Trahtman si v jednu chvíli myslel, že prokázal lepší vazbu n (7n2+ 6n − 16) / 48, ale tento důkaz se ukázal jako nesprávný a papír byl stažen, takže nejznámější vázaný být (n ^ 3 - n) / 6
  5. ^ Adler, R.L .; Weiss, B. (1970), „Podobnost automorfismů torusu“, Monografie Americké matematické společnosti, 98.
  6. ^ Trahtman, A. N. (2009), „Problém zbarvení silnice“, Israel Journal of Mathematics, 172: 51–60, arXiv:0709.0099, doi:10.1007 / s11856-009-0062-5, PAN  2534238
  7. ^ Cameron, Peter (2013), Permutační skupiny a transformační poloskupiny (PDF).

Další čtení