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 Laurent Doyen and Stefan Göller.

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

Prochain séminaire

A Curry-Howard Approach to Tree Automata

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

Date
Le mardi 13 juin 2017 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Colin Riba (LIP, ENS Lyon)

This talk surveys a Curry-Howard perspective on Rabin's Tree Theorem, the decidability of Monadic Second-Order Logic (MSO) on infinite trees.

Rabin's Tree Theorem proceeds by effective translations of MSO-formulae to tree automata. The operations on tree automata used in these translations can be organized in a deduction system based on intuitionistic linear logic (ILL). We propose a computational interpretation of this deduction system along the lines of the Curry-Howard proofs-as-programs correspondence. Relying on the usual technology of game semantics, we interpret proofs as strategies in two-player games generalizing usual acceptance games of tree automata.

This realizability semantics satisfies an expected property of witness extraction from proofs of existential statements. It also allows to combine realizers produced as interpretations of proofs with strategies witnessing (non-)emptiness of tree automata, possibly obtained using external algorithms. Moreover, an adaptation of a usual construction for the simulation of alternating automata by non-deterministic ones satisfies the deduction rules of the "of course" exponential modality of ILL.


Séminaires à venir

TBA

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

 Pablo  Arrighi
Date
Le mardi 20 juin 2017 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Pablo Arrighi (LIF, Université Aix-Marseille)


TBA

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

 Thomas Wies
Date
Le mardi 27 juin 2017 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Thomas Wies (New York University)


TBA

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

 Raul Fervari
Date
Le mardi 11 juillet 2017 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Raul Fervari (University of Córdoba, Argentina)


TBA

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

 Dietrich Kuske
Date
Le mardi 03 octobre 2017 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Dietrich Kuske (TU Ilmenau)


À propos du LSV

Agenda des séminaires

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

mar. 13 juin
mar. 20 juin
mar. 27 juin
mar. 11 juillet
mar. 3 octobre

Les séminaires précédents