Pavel Martyugin

Sinkhronizatsiya Konechnykh Avtomatov: Otsenki Dliny I Vychislitel'noy Slozhnosti Pavel Martyugin Russian edition

Kniga posvyashchena issledovaniyu aktual'nogo napravleniya sovremennoy diskretnoy matematiki ? sinkhronizatsii determinirovannykh konechnykh avtomatov i obobshcheniyu ponyatiya sinkhronizatsii na chastichnye i nedeterminirovannye konechnye avtomaty. Determinirovannyy konechnyy avtomat nazyvaetsya sinkhroniziruemym, esli sushchestvuet slovo, pod deystviem kotorogo vse sostoyaniya avtomata otobrazhayutsya v odno i to zhe sostoyanie. Voprosy o tom, kak proverit' avtomat na sinkhronizuemost' i nayti kratchayshee slovo, sinkhronizirushchee dannyy avtomat, issleduyutsya uzhe bolee soroka let. V knige ustanavlivayutsya otsenki maksimal'noy dliny kratchayshikh sinkhroniziruyushchikh i berezhno sinkhroniziruyushchikh slov, a takzhe slozhnost' algoritmicheskikh zadach, svyazannykh s sinkhroniziruemost'yu i berezhnoy sinkhroniziruemost'yu. Krome togo, v rabote rassmatrivaetsya ponyatie dostizhimosti podmnozhestv v avtomatakh, kotoroe yavlyaetsya estestvennym obobshcheniem ponyatiya sinkhroniziruemosti na sluchay nedeterminirovannykh avtomatov.