SubjectsSubjects(version: 835)
Course, academic year 2018/2019
   Login via CAS
Combinatorics on Words - NMAG444
Title in English: Kombinatorika na slovech
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2016
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: English
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
Annotation -
Last update: T_KA (14.05.2013)

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.
Literature - Czech
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.

Requirements to the exam
Last update: T_KA (14.05.2013)

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.

Syllabus -
Last update: T_KA (14.05.2013)

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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html