Registration for this course is open until Wednesday, 01.05.2024 23:59.

News

Currently, no news are available

Algebraic Methods in Formal Language Theory

This lecture explores some algebraic techniques that are used in the study of formal languages, mainly coming from monoid and semigroup theory. There will be a gentle introduction to the algebraic structures (what is a monoid/semigroup, the free monoid, presentations of monoids, Levi's lemma...) and also a discussion of some basic terminology in formal language theory, if necessary (automata, regular language, ...).

Then we will survey the roles algebraic definitions play in formal language theory: We will introduce syntactic and transition monoids and set out to prove Eilenberg's correspondence theorem, which establishes a connection between a regular (sub-) language and the monoids recognizing it. We will spend time discussing various applications of this theorem, by characterizing different subclasses of regular languages via their recognizing monoids.

If time permits, we will also study additional results like some theorems of Schützenberger and Reitermann.

The lecture will be as self-contained as possible, so no previous knowledge is required. However, if it turns out that the attending students already have an extensive background in either basic algebra and/or formal language theory, we might keep the introduction rather short to make the lecture more interesting.

Lecture:

Tuesdays, 10-12am c.t. in
room SR 6 (=2.17) on
2nd floor of building E2.4 (Maths building)

Exercises: t.b.d

Literature

Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.