Shablony, Izbegaemye Antitsepyami Slov, I Ikh Algebraicheskie Prilozheniya

Pervoy rabotoy po kombinatorike slov schitaetsya stat'ya Tue, v kotoroy on pokazyvaet, chto sushchestvuet beskonechnoe slovo nad trekhbukvennym alfavitom, ne soderzhashchee dvukh odinakovykh podryad idushchikh podslov. V sovremennoy terminologii govoritsya ob izbegaemosti kvadratov. Kombinatornyy podkhod okazalsya estestvennym dlya resheniya zadach dlya polugrupp i ikh mnogoobraziy, zadannykh tozhdestvami vida u=0, i napryamuyu svyazan s izbegaemost'yu shablona u. V dannoy rabote pokazyvaetsya, chto takie mnogoobraziya obladayut svoystvom reshetochnoy universal'nosti (ikh reshetka podmnogoobraziy dostatochno slozhna v tom smysle, chto v nee vkladyvaetsya reshetka podmnogoobraziy lyubykh algebr s ne bolee chem schetnym chislom operatsiy). Bolee togo, ponyatie izbegaemosti mozhno vvesti dlya tozhdestv proizvol'nogo vida i togda, kak pokazano v rabote, mozhno klassifitsirovat' reshetochno universal'nye mnogoobraziya polugrupp. Osnovnaya slozhnost' takogo podkhoda sostoit v tom, chtoby dokazat', chto kazhdyy izbegaemyy shablon (izbegaemoe tozhdestvo) obladaet dopolnitel'nym svoystvom izbegaemosti antitsepyami. Dokazatel'stvu poslednego fakta posvyashchena kombinatornaya chast' raboty.