Sylabus
1. Vlastnosti podmonoidů volných monoidů. Definice kódu. Řád pologrupy. F-pologrupy.
2. Homomorfismy. Rovnice a její řešení. Systém rovnic a jejich ekvivalentní podsystémy. Věta o kompaktnosti ( "Ehrenfeuchtova hypotéza").
3. Testovací množiny. Existence konečné testovací množiny. Ekvivalence s větou o kompaktnosti.
4. Postův problém (PCP) a jeho varianty. Binární ekvivalenční množiny a jejich struktura. Problém regularity ekvivalenčních množin.
Anotace
Přednáška je úvodem do kombinatorických vlastností volnych monoidů
(resp. pologrup). Zabývá se především strukturou podmonoidů, homomorfismy a řešením rovnic. Z pokročilejších partií je věnován prostor ekvivalenčním množinám. Přednáška je doprovázena formalizací v důakzovém asistentu Isabelle/HOL.