Kombinatorika na slovech

Předmět na Matematicko-fyzikální fakulta |

NMAG444

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.