Kombinatorika na slovech - NMAG444

• Anglický název: Combinatorics on Words
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Další informace: https://dl1.cuni.cz/course/view.php?id=9694
• Poznámka: předmět je možno zapsat mimo plán
• Garant: doc. Mgr. Štěpán Holub, Ph.D.
• Vyučující: doc. Mgr. Štěpán Holub, Ph.D.
• Třída: M Mgr. MSTR; M Mgr. MSTR > Povinně volitelné
• Kategorizace předmětu: Matematika > Algebra
• Neslučitelnost : NALG083
• Záměnnost : NALG083
• Je záměnnost pro: NALG083

Anotace

čeština

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.

Poslední úprava: Holub Štěpán, doc. Mgr., Ph.D. (24.08.2023)

angličtina

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.

Poslední úprava: Holub Štěpán, doc. Mgr., Ph.D. (24.08.2023)

Podmínky zakončení předmětu

Předmět je zakončen ústní zkouškou.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (10.06.2019)

Literatura

čeština

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.

Poslední úprava: T_KA (14.05.2013)

angličtina

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.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.09.2021)

Požadavky ke zkoušce

čeština

Student si vylosuje otázku ze seznamu témat. Po písemné přípravě otázku ústně zodpoví.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (10.06.2019)

angličtina

The student will draw the exam question from a list of covered topics. The content of the question can be further specified if needed. The answer is oral after a written preparation.

Poslední úprava: Holub Štěpán, doc. Mgr., Ph.D. (14.02.2018)

Sylabus

čeština

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.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.09.2021)

angličtina

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.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.09.2021)

Vstupní požadavky

čeština

Základy obecné algebry.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (17.05.2019)

angličtina

Basics of general algebra.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (17.05.2019)