Groupe de travail

Équipe thématique Automates et applications
Équipe thématique Théorie et algorithmique des graphes

Gestion des séances

Graphes et Logique


Jour, heure et lieu

Le mercredi à 13h30, salle 3052

Le calendrier des séances (format iCal).
Pour ajouter le calendrier des séances à votre agenda favori, souscrire au calendrier en indiquant ce lien.


Contact(s)

Hector Buffiere
Giannos Stamoulis

Ce groupe de travail a pour objectif d'échanger et de collaborer autour des problèmes liant théorie des modèles et théorie structurelle des graphes.

Il s’articule autour d’un séminaire mensuel de deux exposés et de réunions de travail hebdomadaires sur des questions de recherche.


Prochaine séance

Graphes et Logique
Mercredi 30 avril 2025, 13 heures 30, Salle 1021
Sylvain Schmitz (IRIF) Well quasi-orders and preservation theorems for First-Order Logic - Part II

Continuation of part I. I intend to cover
  1. applications of WQOs in algorithmic graph theory,
  2. a focus on classes of graphs that are well-quasi-ordered by the induced subgraph ordering, along with Pouzet’s Conjecture,
  3. the generalisation to preservation properties in first-order logic.


Séances passées


Année 2025

Graphes et Logique
Mercredi 26 mars 2025, 13 heures 30, salle 3052
Sylvain Schmitz; Giannos Stamoulis Well quasi-orders and preservation theorems for First-Order Logic; Some extensions of First-Order logic on graphs

This will be a gentle tutorial on mostly standard results about well-quasi-orders (wqo) in a context of graph theory and algorithmic meta-theorems. I intend to cover a few basics of wqo theory, their applications in algorithmic graph theory, a focus on classes of graphs that are well-quasi-ordered by the induced subgraph ordering, along with Pouzet's Conjecture, and finally the generalisation to preservation properties in first-order logic.

.

In this tutorial we present a landscape of extensions of first-order logic (on graphs) and we discuss their expressive power and algorithmic results related to them. These extensions involve either additional predicates expressing different types of connectivity or the quantification over vertex sets that are (in a sense) of simple structure.