Lecture: Algebraic Automata Theory
Winter Term 2017/18 in Braunschweig
News
- January 16
-
The will be no lecture on January 17. The next lecture will be on January 22.
- January 11
-
There will be no lecture on January 15.
- January 05
-
There will be no lectures and tutorials in the week of January 08.
- October 16
-
The room for the Monday lecture has changed from IZ 358 to PK 3.1
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 PK 3.1.
-
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
The exercise sheets will be made available here.
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
- introduction of two initially unrelated language classes: the rational and the
recognizable languages (Rat and Rec), for arbitrary, or at least finitely
generated monoids
- according to Kleene's Theorem, Rat and Rec coincide on finitely
generated free monoids, hence one can work in Rec to solve classical
problems in Rat (Schützenberger et. al.; syntactic monoids)
- Rec is intimitely connected to the theory of 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 has to consider profinite equations (Reiterman's theorem)
- (perhaps, time permitting) the charactrization of lattices of languages,
i.e., classes of languages closed under finite unions and intersections.
Lecture Notes
Script
The script will evolve parallel with the lectures. There are two
versions, one in classical
notation and one in RPN. Moreover, here is a
list of changes copared with the
previous version.
Literature
The lectures will mainly be based upon the following book, available
on the WEB:
