Institut de Mathématiques de Marseille, UMR 7373




Rechercher


Accueil > Séminaires > Séminaires et Groupes de travail hebdomadaires > Logique et Interactions

Séminaire Logique et Interactions

par Lozingot Eric, Vaux Lionel - publié le , mis à jour le

Agenda

Séminaire

  • Jeudi 26 janvier 11:00-12:00 - Gabriel SCHERER - Northeastern University, Boston

    Deciding simply-typed equivalence with sums and the empty type

    Résumé : The simply-typed λ-calculus, with only function types, is strongly normalizing, and its program equivalence relation is decidable : unlike in more advanced type system with polymorphism or effects, the natural "syntactic" equivalence (βη-equivalence) corresponds to natural "semantic" equivalence (observational or contextual equivalence), and is decidable. Adding product types (pairs) is easy and preserves these properties, but sums (disjoint unions) are, surprisingly, harder. It is only in 1995 that Neil Ghani proved that the equivalence in presence of sums is decidable, and the situation in presence of the empty type (zero-ary sum) was unknown.
    We propose an equivalence algorithm for sums and the empty type that takes inspiration from a proof-theoretic technique, named "focusing",designed for proof search. The exposition will be introductory ; I will present the difficulties caused by sums and the empty type, present some of the existing approaches for sums in the literature, introduce focusing, and give a high-level intuition of our saturation-based algorithm and its termination argument.

    JPEG - 24.5 ko
    Gabriel SCHERER

    Lieu : Salle des séminaires 304-306 (3ème étage) - Institut de Mathématiques de Marseille (UMR 7373)
    Site Sud
    Campus de Luminy, Case 907
    13288 MARSEILLE Cedex 9

    Exporter cet événement

groupe de travail

Manifestation scientifique

Descriptif
Nature Séminaire et Groupe de travail
Intitulé Logique et interactions
Responsable Lionel Vaux
Équipe de rattachement Logique de la Programmation (LDP) du Groupe Arithmétique Géométrie Logique et Représentations (AGLR, ex-LUM)
Fréquence 1 à 2 séances par mois
Jour-Horaire Jeudi. 11h-12h30
Lieu Luminy, salle des séminaires 304-306 (accès)
Lien http://iml.univ-mrs.fr/ldp/seminaire/

Contact : lionel.vaux_AT_univ-amu.fr