Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Stéphane Le Roux and Matthias Fuegger.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Séminaires passés

Completeness proofs for Kleene algebra

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

 Damien Pous
Date
Le mardi 15 janvier 2019 à 11:00
Lieu
Pavillon des Jardins
Orateur
Damien Pous (ENS Lyon)

Kleene algebra form a complete axiomatisation for regular expressions containments. This result was proved independently by Kozen and by Boffa and Krob in the early 90s. We will overview recent developments on such axiomatisation results, based on work with Amina Doumane, Anupam Das, and Paul Brunet. First we will present a new proof of completeness for Kleene algebra based on circular proof systems: sequent calculi where proofs are graphs rather than trees. Then we will discuss a natural extension of regular expressions, with an explicit intersection operator. This operator requires us to move from languages of words to languages of graphs ; we obtained a complete axiomatisation using an appropriate notion of graph automata.


À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

mar. 29 janvier
mar. 5 février
mar. 19 février

Les séminaires précédents