Combinatorics on Words - NMAG444

• Title: Kombinatorika na slovech
• Guaranteed by: Department of Algebra (32-KA)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2016 to 2017
• Semester: summer
• E-Credits: 3
• Hours per week, examination: summer s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: English
• Teaching methods: full-time
• Teaching methods: full-time
• Note: course can be enrolled in outside the study plan
• Guarantor: doc. Mgr. Štěpán Holub, Ph.D.
• Class: M Mgr. MSTR; M Mgr. MSTR > Povinně volitelné
• Classification: Mathematics > Algebra
• Incompatibility : NALG083
• Interchangeability : NALG083
• Is interchangeable with: NALG083

Annotation

English

Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (22.09.2021)

The lecture 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.

Czech

Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (22.09.2021)

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.

Literature

Last update: T_KA (14.05.2013)

C. Choffrut and J. Karhumäki, Combinatorics on words, in: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), vol. I, Springer-Verlag, Berlin Heidelberg 1997, pp. 329-438.

T. Harju and J. Karhumäki, Morphisms, in: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), vol. I, Springer-Verlag, Berlin Heidelberg 1997, pp. 439-510.

M. Lothaire, Combinatorics on words, Addison-Wesley, Reading Masachusetts, 1983.

M. Lothaire, Algebraic Combinatorics on words, Cambridge University Press, 2002.

J. Berstel and D. Perrin, Theory of Codes, Academic Press, London 1985.

Syllabus

English

Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (22.09.2021)

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.

Literature:

C. Choffrut and J. Karhumäki, Combinatorics on words, in: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), vol. I, Springer-Verlag, Berlin Heidelberg 1997, pp. 329-438.

T. Harju and J. Karhumäki, Morphisms, in: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), vol. I, Springer-Verlag, Berlin Heidelberg 1997, pp. 439-510.

M. Lothaire, Combinatorics on words, Addison-Wesley, Reading Masachusetts, 1983.

M. Lothaire, Algebraic Combinatorics on words, Cambridge University Press, 2002.

J. Berstel and D. Perrin, Theory of Codes, Academic Press, London 1985.

Czech

Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (22.09.2021)

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.