Difference between revisions of "Flt25"
Radu iosif (Talk | contribs) |
Radu iosif (Talk | contribs) |
||
| Line 23: | Line 23: | ||
'''Bibliography''': | '''Bibliography''': | ||
| − | Mikołaj Bojańczyk. [https://arxiv.org/pdf/2008.11635 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] | + | * Mikołaj Bojańczyk. [https://arxiv.org/pdf/2008.11635 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. [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] |
* H. Comon, M. Dauchet, R. Gilleron, C. Loeding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi. [http://tata.gforge.inria.fr/ Tree Automata: Theory and Applications] | * H. Comon, M. Dauchet, R. Gilleron, C. Loeding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi. [http://tata.gforge.inria.fr/ Tree Automata: Theory and Applications] | ||
| − | 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] |
| − | Bruno Courcelle. [https://www.labri.fr/perso/courcell/Textes1/MSOL05(1991).pdf The monadic second-order logic of graphs V: on closing the gap between definability and recognizability] | + | * Bruno Courcelle. [https://www.labri.fr/perso/courcell/Textes1/MSOL05(1991).pdf The monadic second-order logic of graphs V: on closing the gap between definability and recognizability] |
| − | Bruno Courcelle and Joost Engelfriet. [https://www.researchgate.net/publication/220544439_A_Logical_Characterization_of_the_Sets_of_Hypergraphs_Defined_by_Hyperedge_Replacement_Grammars A Logical Characterization of the Sets of Hypergraphs Defined by Hyperedge Replacement Grammars] | + | * Bruno Courcelle and Joost Engelfriet. [https://www.researchgate.net/publication/220544439_A_Logical_Characterization_of_the_Sets_of_Hypergraphs_Defined_by_Hyperedge_Replacement_Grammars A Logical Characterization of the Sets of Hypergraphs Defined by Hyperedge Replacement Grammars] |
Revision as of 12:28, 28 March 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
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
- H. Comon, M. Dauchet, R. Gilleron, C. Loeding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi. Tree Automata: Theory and Applications
- 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
