Difference between revisions of "Flt25"
Radu iosif (Talk | contribs) |
Radu iosif (Talk | contribs) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 19: | Line 19: | ||
* Mar 18, 2026 02:00 PM [https://nts.imag.fr/images/8/83/Lecture2.pdf slides] | * Mar 18, 2026 02:00 PM [https://nts.imag.fr/images/8/83/Lecture2.pdf slides] | ||
* Mar 25, 2026 02:00 PM [https://nts.imag.fr/images/c/c0/Lecture3.pdf slides] | * Mar 25, 2026 02:00 PM [https://nts.imag.fr/images/c/c0/Lecture3.pdf slides] | ||
| − | * Apr 01, 2026 02:00 PM | + | * Apr 01, 2026 02:00 PM [https://nts.imag.fr/images/e/e5/Lecture4.pdf slides] |
'''Bibliography''': | '''Bibliography''': | ||
| Line 27: | Line 27: | ||
* Jean-Éric Pin. [https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf Mathematical Foundations of Automata Theory] | * Jean-Éric Pin. [https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf Mathematical Foundations of Automata Theory] | ||
| − | * | + | * Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi [http://tata.gforge.inria.fr/ Tree Automata: Theory and Applications] |
| + | |||
| + | * Bruno Courcelle and Joost Engelfriet. [https://www.labri.fr/perso/courcell/Book/TheBook.pdf Graph Structure and Monadic Second-Order Logic, a Language Theoretic Approach] | ||
* Bruno Courcelle. [https://www.sciencedirect.com/science/article/pii/089054019090043H The monadic second-order logic of graphs. I. Recognizable sets of finite graphs] | * Bruno Courcelle. [https://www.sciencedirect.com/science/article/pii/089054019090043H The monadic second-order logic of graphs. I. Recognizable sets of finite graphs] | ||
Latest revision as of 16:15, 1 April 2026
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) in Room 206 (2nd floor of IMAG building)
- Mar 11, 2026 02:00 PM slides
- Mar 18, 2026 02:00 PM slides
- Mar 25, 2026 02:00 PM slides
- Apr 01, 2026 02:00 PM slides
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
- Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi Tree Automata: Theory and Applications
- Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic, a Language Theoretic Approach
- Bruno Courcelle. The monadic second-order logic of graphs V: on closing the gap between definability and recognizability
- Bruno Courcelle and Joost Engelfriet. A Logical Characterization of the Sets of Hypergraphs Defined by Hyperedge Replacement Grammars
