Modulcode:	Inf-CombWords
Englische Bezeichnung:	Combinatorics on Words
Modulverantwortliche(r):	Prof. Dr. Dirk Nowotka
Turnus:	unregelmäßig (SS14 SS15 SS16 WS18/19 WS20/21 SS22 SS23)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 h lectures, 30 h exercises, 120 h self studies
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-WP (BSc Inf (21)) WI (BSc Inf (15)) MSc-Inf-Theo (MSc Inf (21)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21)) MSc-WInf-WP-Inf (MSc WInf (21)) TI (MSc Inf (15)) WI (MSc Inf (15)) WI (MSc WInf (15)) WI (MEd Inf) WPI (MEd Inf) IG (MSc Inf) TG (MSc Inf) MV (MSc Inf)
Lehrsprache:	Englisch
Voraussetzungen:

Kurzfassung:

This course is an extended introduction into the theory of combinatorics on words (aka strings or sequences). Connections to applications of string algorithms will be drawn in providing the combinatorial background to the course Algorithms on Sequences.

Lernziele:

A successful student of this course will have an in-depth knowledge combinatorial properties of sequential structures.

Lehrinhalte:

We consider advanced properties of periods in finite and infinite words, word equations, circular words, subword complexity, fixed point words and avoidability questions.

Weitere Voraussetzungen:

basic knowledge in mathematical algebra

Prüfungsleistung:

Oral exam over 30 minutes

Lehr- und Lernmethoden:

black board presentation; exercises

Verwendbarkeit:

Literatur:

• M. Lothaire: Combinatroics on Words, Addison-Wesley, 1983.
• M. Lothaire: Algebraic Combinatorics on Words, Cambridge University Press, 2002.
• M. Lothaire: Applied Combinatorics on Words, Cambridge University Press, 2005.
• J.-P. Allouche, J. Shallit: Automatics Sequences, Cambridge University Press, 2003.

Verweise:

Kommentar: