Předmět Kombinatorika na slovech (NMAG444)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NMAG444 - Kombinatorika na slovech, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
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.
Literatura
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.
Garant
doc. Štěpán Holub, Ph.D.