Syllabus
1. Properties of submonoids of free monoids. Code. Rank of subsemigroup. F-semigroups.
2. Morphisms. Equation and its solution. Systems of equations and equivalent subsystems. Compactness Theorem. ( "Ehrenfeucht's conjecture").
3. Test sets. Existence of a finite test set. Equivalence with the Compactness Theorem.
4. Post Correspondence Problem (PCP) and its modofications. Binary equality sets and their structure. Regular equality sets.
Annotation
The course introduces to combinatorial properties of free monoids
(semigroups resp.). It deals mainly with the structure of submonoids, with morphisms, and with solutions of equations. Some questions concerning equality sets represent a more advanced part of the lecture.
The course is complemented by formalization in the proof assistant Isabelle/HOL.