Mikhail Berlinkov

Teoriya Sinkhroniziruemosti: Approksimatsiya Dlin Sinkhroniziruyushchikh Slov Dlya Konechnykh Avtomatov Mikhail Berlinkov Russian edition

Kniga posvyashchena issledovaniyu osnovnykh voprosov teorii sinkhroniziruemykh avtomatov. Avtomat nazyvaetsya sinkhroniziruemym, esli on obladaet slovom, deystvie kotorogo perevodit avtomat v nekotoroe sostoyanie vne zavisimosti ot iskhodnogo sostoyaniya. Sootvetstvuyushchee slovo nazyvaetsya sinkhroniziruemym. Dannoe ponyatie yavlyaetsya ochen' estestvennym, tak kak sootvetstvuet svoystvam ustoychivosti i upravlyaemosti dlya diskretnykh sistem, a sama teoriya aktivno izuchaetsya uzhe bolee 40 let. Pervaya chast' knigi posvyashchena osnovnoy otkrytoy teoreticheskoy probleme - dokazatel'stvu kvadratichnoy (ot chisla sostoyaniy avtomata) otsenki na dliny sinkhroniziruyushchikh slov. V chastnosti, oprovergnuty vydvinutye izvestnymi uchenymi gipotezy, spravedlivost' kotorykh byla podtverzhdena imi dlya chastnykh sluchaev i vlekla by reshenie problemy v obshchem sluchae. Na osnove idey, svyaazannykh s oproverzheniem etikh gipotez, v knige dokazana kvadratichnaya otsenka dlya klassa odnoklasternykh avtomatov. Vtoraya chast' knigi posvyashchena osnovnym voprosam, imeyushchim prakticheskuyu znachimost' v dannoy oblasti: izuchena algoritmicheskaya slozhnost' zadach approkismatsii dlin sinkhroniziruyushchikh slov, a takzhe zadach vychisleniya optimal'nykh raskrasok grafov.