Teoriq sinhroniziruemosti

Kniga poswqschena issledowaniü osnownyh woprosow teorii sinhroniziruemyh awtomatow. Awtomat nazywaetsq sinhroniziruemym, esli on obladaet slowom, dejstwie kotorogo perewodit awtomat w nekotoroe sostoqnie wne zawisimosti ot ishodnogo sostoqniq. Sootwetstwuüschee slowo nazywaetsq sinhroniziruemym. Dannoe ponqtie qwlqetsq ochen' estestwennym, tak kak sootwetstwuet swojstwam ustojchiwosti i uprawlqemosti dlq diskretnyh sistem, a sama teoriq aktiwno izuchaetsq uzhe bolee 40 let. Perwaq chast' knigi poswqschena osnownoj otkrytoj teoreticheskoj probleme - dokazatel'stwu kwadratichnoj (ot chisla sostoqnij awtomata) ocenki na dliny sinhroniziruüschih slow. V chastnosti, oprowergnuty wydwinutye izwestnymi uchenymi gipotezy, sprawedliwost' kotoryh byla podtwerzhdena imi dlq chastnyh sluchaew i wlekla by reshenie problemy w obschem sluchae. Na osnowe idej, swqazannyh s oprowerzheniem ätih gipotez, w knige dokazana kwadratichnaq ocenka dlq klassa odnoklasternyh awtomatow. Vtoraq chast' knigi poswqschena osnownym woprosam, imeüschim prakticheskuü znachimost' w dannoj oblasti: izuchena algoritmicheskaq slozhnost' zadach approkismacii dlin sinhroniziruüschih slow, a takzhe zadach wychisleniq optimal'nyh raskrasok grafow.