Algebraic Methods in Formal Language Theory

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:

Wednesdays, 16-18 (see timetable for exercise dates)

room SR 9 on

3rd floor of building E2.4

Literature

• https://www.infomath-bib.de/tmp/vorlesungen/info-advanced_algebraic-methods-in-formal-language-theory.html
• Lecture Notes by Jean-Éric Pin