LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Laurent Doyen and Stefan Göller.

The seminar is open to public and does not require any form of registration.

Next Seminar

A Curry-Howard Approach to Tree Automata

Visit website for this news | Export event in iCalendar format

Date
Tuesday, June 13 2017 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
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.


Upcoming Seminars

TBA

Visit website for this news | Export event in iCalendar format

 Pablo  Arrighi
Date
Tuesday, June 20 2017 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
Pablo Arrighi (LIF, Université Aix-Marseille)


TBA

Visit website for this news | Export event in iCalendar format

 Thomas Wies
Date
Tuesday, June 27 2017 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
Thomas Wies (New York University)


TBA

Visit website for this news | Export event in iCalendar format

 Raul Fervari
Date
Tuesday, July 11 2017 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
Raul Fervari (University of Córdoba, Argentina)


TBA

Visit website for this news | Export event in iCalendar format

 Dietrich Kuske
Date
Tuesday, October 03 2017 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
Dietrich Kuske (TU Ilmenau)


About LSV

Agenda

Export agenda in iCalendar format | Past seminars

Tue, Jun 13
Tue, Jun 20
Tue, Jun 27
Tue, Jul 11
Tue, Oct 3

Past seminars