Institut de Mathématiques de Marseille, UMR 7373


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



  • Jeudi 7 juin 11:00-12:30 - Pierre VIAL - IRIF, Paris 7

    Representing permutations without permutations, or the expressive power of sequence types

    Résumé : An intersection type system with given features (strict or not, idempotent or not, relevant or not, rigid or not...) characterizing, e.g., a notion of normalization can be presented in various ways. Recent works by Asada, Ong and Tsukada have championed a rigid description of resources. Whereas in non-rigid paradigms (e.g., standard Taylor expansion or non-idempotent intersection types), bags of resources are multisets and invariant under permutation, in the rigid ones, permutations must be processed explicitly and can be allowed or disallowed. Rigidity enables a fine-grained control of reduction paths and their effects on, e.g., typing derivations. We previously introduced system S, featuring a sequential intersection : a sequence is a family of types indexed by a set of integers. However, one may wonder in what extent the absence of permutations causes a loss of expressivity w.r.t. reduction paths, compared to a usual multiset framework or a rigid one with permutations. Our main contribution is to prove that not only every non-idempotent derivation can be represented by a rigid, permutation-free derivation, but also that any dynamic behavior may be captured in this way. In other words, we prove that system S (sequential intersection) has full expressive power over multiset/ permutation-inclusive intersection. We do so in the most general setting, i.e. by considering coinductive type grammars, so that this work also applies in the study of the infinitary relational model.

    JPEG - 17 ko
    Pierre VIAL

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

    Exporter cet événement

groupe de travail

Manifestation scientifique

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)

Contact :