Flt25

Lecturer: Radu Iosif

Contents: Formal language theory studies the finite representation of infinite sets of objects (e.g., words, trees, graphs). These representations can be either descriptive, specifying logical properties of their members (e.g. planar or hamiltonian graphs), or constructive, describing how the members of the set are built. In particular, constructive representations come with algebras that fix the class of objects and the operations considered. Then, recognizable sets are defined in terms of congruence relations over the algebra, with a finite number of equivalence classes.

The goal of this course is to introduce the student to the connection between logical definability (using first-order and monadic second-order logics) and recognisability (by automata, semigroups and algebras). This connection is the cornerstone of formal language theory, because it provides robust characterisations of the classes of sets that can be represented finitely on a computer.

Prerequisites: basic notions of boolean logic and discrete mathematics (sets, relations, orders, functions); see preliminaries for an introduction to the basic notions required by this course. Basic notions of automata theory and first/second-order logic could be useful and can be found here

Level: PhD and Master 1-2

Schedule: Wednesdays between 14h00 and 16h00 (Paris time, GMT+1), from March 19th to April 9th in Room 206 (2nd floor of IMAG building)

• Mar 19, 2025 02:00 PM slides
• Mar 26, 2025 02:00 PM slides
• Apr 2, 2025 02:00 PM slides
• Apr 9, 2025 02:00 PM

Bibliography:

Mikołaj Bojańczyk. Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic

Jean-Éric Pin. Mathematical Foundations of Automata Theory

Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs