Mikołaj Bojańczyk

Finite algebras and connections with tree languages


This one of the courses at the Lipa Summer School.

Matt Valeriote

Finite algebras and connections with tree languages

Slides

In the 1980’s Hobby and McKenzie developed concepts and tools to analyze the local structure of finite algebras and the varieties (equationally defined classes of algebras) that they determine. The resulting collection of definitions and theorems is called Tame Congruence Theory and it has been used in a wide variety of investigations. In the first part of this tutorial I will present an overview of Tame Congruence Theory, including a description of the local structure of finite algebras that the theory provides, as well as a proof of Palfy’s Theorem characterizing the minimal algebras. I will also discuss some of the deep consequences of the theory that relate the local behaviour of finite algebras in a variety with the global behaviour of its members.

In the second part of the tutorial I will consider algebras as (regular) tree language recognizers and discuss some interesting connections between regular tree languages and finite algebras that are informed by Tame Congruence Theory.