Lecture: Algebraic Automata Theory
Winter Term 2018/19 in Braunschweig
News
Organisation
-
The lecture will be given by Dr. Jürgen Koslowski.
-
Entry in the list of lectures:
Lecture,
Exercises.
-
The date and room for the lecture are:
-
Monday, 15:00 - 16:30 in IZ
305.
-
Wednesday, 09:45 - 11:15 in IZ 358.
-
The date and room for the exercise classes are:
- Thursday, 13:15 - 14:45 in IZ 358.
Exercises
-
Exercise sheet 0, 2018-10-18
-
Exercise sheet 1, 2018-10-25
-
Exercise sheet 2, 2018-11-01
-
Exercise sheet 3, 2018-11-08
-
Exercise sheet 4, 2018-11-15
-
Exercise sheet 5, 2018-11-22
-
Exercise sheet 6, 2018-11-29
-
Exercise sheet 7, 2018-12-10
-
Exercise sheet 8, 2019-01-17
-
Exercise sheet 9, 2019-01-24
Module
Sucessfully finishing the module consists of two parts:
- Prüfungsleistung: Oral exam after the lecture period.
- perhaps: Studienleistung: Get at least 60% of all points on your submitted solutions of the exercise sheets.
Contents
- Overview over the "arena" we will be working in; problems concerning
regular languages and their subclasses may become more accessible by
shifting the focus from subsets of free monoids (i.e., formal
languages) to subsets of arbitrary monoids.
- Category theory is introduced to (0) view each monoid as a
category (with one object) and (1) analyze the (algebraic) category
of all monoids, and to distinguish it from the categories of
semigroups and of monoids with 0. In particular, the theory of
monads and of distributive laws will be presented.
- Introduction of two initially unrelated classes of subsets of
arbitrary monoids: the rational sets and the recognizable sets (Rat and
Rec). Rat admits an elegant description by means of monads, and
categorical methods help in the analysis of closure
properties of Rat, resp., Rec.
- According to Kleene's Theorem, on finitely generated free
monoids Rat and Rec coincide with the well-known regular languages.
This can be exploited to solve problems concerning classes of
regular languages (Schützenberger et. al.; syntactic monoids).
- Schützenberger's proof is not categorical in nature, one version
relies on so-called Green's relations instead. Hence it is
difficult to generalize to other classical problems concerning
certain classes of regular languages.
- Rec is intimitely connected to the class of all finite monoids,
moreover "nice" subclasses of finite monoids correspond to "nice"
subclasses of recognizable languages, so-called "pseudo-varieties" (Eilenberg).
- While varieties of arbitrary monoids, i.e., classes of monoids closed
under homomorphic images (H), sub-monoids (S) and potentially
infinite products (P), have a simpe description in terms of
equations in the signature for monoids (Birkhoff 1935), this no
longer works when only closure under finite
products (F) is required as for pseudo-varieties of finite monoids
- Instead, one can consider "profinite equations" (Reiterman's theorem)
- Classical problems about certain subclasses of regular
languages can now be tackled by identifying them as being recognized
by suitable quasivarieties of finite monoids.
Script
The script will be revised in parallel with the lectures. There are two
versions, one in classical
notation and one in RPN.
Literature
The lectures will to some extent be based upon the following book, available
on the WEB:
