# Theoretical Computer Science

## Lecture: Algebraic Automata Theory

### Winter Term 2018/19 in Braunschweig

#### 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.

#### 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: