Les séminaires sont communs avec l'équipe Plume (ENS Lyon) et ont lieu en salle de séminaire, premier étage du bâtiment Le Chablais, sur le site du Bourget du Lac ou à l'ENS Lyon.

Prochain séminaire :

Jeudi 03 septembre 2015 à 10h A venir (A venir),
A venir

Résumé : (Masquer les résumés)
À venir

Le séminaire de l’équipe LIMD est sous la responsabilité de Xavier Provencal.
Options : Voir par date croissante . Masquer les résumés.
Autres années : 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, toutes ensemble.

Année 2015

Jeudi 24 septembre 2015 à 10h Paweł Sobociński (Southampton),
TBA

Résumé : (Masquer les résumés)
TBA

Jeudi 03 septembre 2015 à 10h A venir (A venir),
A venir

Résumé : (Masquer les résumés)
À venir

Jeudi 18 juin 2015 à 10h Blanche Buet (Université Lyon 1),
Approximation de surfaces par des varifolds discrets

Résumé : (Masquer les résumés)
Il existe de très nombreuses façons de représenter et discrétiser une courbe ou une surface, en raison notamment des applications envisagées et des modes d'acquisitions des données (nuages de points, approximations volumiques, triangulations...). Le but de cet exposé sera de présenter un cadre commun pour l'approximation des surfaces, dans l'esprit de la théorie géométrique de la mesure, à travers la notion de varifold discret. Ce cadre nous a notamment permis de dégager une notion de courbure moyenne discrète (à une échelle donnée) unifiée dont on présentera les propriétés de convergence et qu'on illustrera numériquement sur des nuages de points.

Jeudi 04 juin 2015 à 10h Svetlana Puzynina (Sobolev Institute of Mathematics et ENS Lyon),
Infinite self-shuffling words

Résumé : (Masquer les résumés)
In this talk we introduce and study a new property of infinite words: An infinite word x on an alphabet A is said to be it self-shuffling, if x admits factorizations: $x=prod_{i=1}^infty U_iV_i=prod_{i=1}^infty U_i=prod_{i=1}^infty V_i$ with $U_i,V_i in A^*$. In other words, there exists a shuffle of x with itself which reproduces x. This property of infinite words is shown to be an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic uniformly recurrent word contains a non self-shuffling word in its shift orbit closure. On the other hand, we build an infinite word such that no word in its shift orbit closure is self-shuffling. We prove that many important and well studied words are self-shuffling: This includes the Thue-Morse word and all Sturmian words (except those of the form aC where a ∈ {0,1} and C is a characteristic Sturmian word). We further establish a number of necessary conditions for a word to be self-shuffling, and show that certain other important words (including the paper-folding word and infinite Lyndon words) are not self-shuffling. One important feature of self-shuffling words is its morphic invariance: The morphic image of a self-shuffling word is again self-shuffling. This provides a useful tool for showing that one word is not the morphic image of another. In addition to its morphic invariance, this new notion has other unexpected applications: For instance, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic. Finally, we provide a positive answer to a recent question by T. Harju whether square-free self-shuffling words exist and discuss self-shufflings in a shift orbit closure. E. Charlier, T. Kamae, S. Puzynina, L. Q. Zamboni: Infinite self-shuffling words. J. Comb. Theory, Ser. A 128: 1-40 (2014) M. Müller, S. Puzynina, M. Rao: On Shuffling of Infinite Square-Free Words. Electr. J. Comb. 22(1): P1.55 (2015)

Jeudi 28 mai 2015 à 10h Colin Riba (ENS Lyon),
Fibrations of Tree Automata

Résumé : (Masquer les résumés)
We propose a notion of morphisms between tree automata based on game semantics. Morphisms are winning strategies on a synchronous restriction of the linear implication between acceptance games. This leads to split indexed categories, with substitution based on a suitable notion of synchronous tree function. By restricting to tree functions issued from maps on alphabets, this gives a fibration of tree automata. We then discuss the (fibrewise) monoidal structure issued from the synchronous product of automata. We also discuss how a variant of the usual projection operation on automata leads to an existential quantification in the fibered sense. Our notion of morphism is correct, in the sense that it respects language inclusion, and in a weaker sense also complete.

Jeudi 21 mai 2015 à 10h30, ENS Lyon Miquey Charguéraud et Salibra (Paris 7, Inria et Venise),
Séminaire Chocola

Jeudi 07 mai 2015 à 10h Hachem Hichri (Institut préparatoire aux études d’ingénieurs de Monastir),
Quelques résultats sur les nombres de Salem, les nombres de Pisot et les beta-nombres

Résumé disponible sous forme de fichier PDF.

Jeudi 30 avril 2015 à 10h Emmanuel Beffara (Université d'Aix-Marseille),
Vers l'unification des systèmes de types pour processus mobiles

Résumé : (Masquer les résumés)
Ce travail présente un cadre unificateur pour les systèmes de types pour les algèbres de processus. Le cœur du système fournit une correspondance précise entre des processus essentiellement fonctionnels et des démonstrations de logique linéaire; des fragments de ce système correspondent à des connections précédemment connues entre démonstrations et processus. On montre que l'ajout d'axiomes logiques peut étendre la classe des processus typables en échange de la perte de propriétés calculatoires comme l'absence de blocage ou la terminaison, ce qui permet de voir différents systèmes connus (types i/o, linéarité, contrôle) comme des instances d'un modèle général. Cette approche suggère des méthodes unifiées pour l'extension de systèmes de types avec de nouvelles propriétés tout en restant dans un cadre bien structuré, ce qui constitue un pas vers l'étude de la sémantique dénotationnelle des processus par des méthodes de théorie de la démonstration.

Jeudi 23 avril 2015 à 10h Nadia Lafrenière (UQAM et LAMA),
La bibliothèque de Tsetlin : Diverses approches pour les marches aléatoires sur les permutations

Résumé : (Masquer les résumés)
Dans cet exposé, nous étudierons différentes modélisations pour le mélange d'objets alignés (des livres, des cartes, des fichiers, etc.). En particulier, l'action qui correspond à piger un élément au hasard et à le remettre au début de la liste s'avère être un point de départ intéressant pour l'étude des marches aléatoires sur le groupe symétrique. Nous verrons que l'utilisation de techniques algébriques permet l'analyse de mélanges élaborés.

Jeudi 09 avril 2015 à 10h30, ENS Lyon TBA (TBA),
Séminaire Chocola

Jeudi 09 avril 2015 à 10h Robert French (Université de Bourgogne),
Définition probabiliste d'un segment de droite discrète et automates cellulaires

Résumé : (Masquer les résumés)
Cette présentation montrera un lien théorique entre les segments de droite discrète (DSS) et la théorie probabiliste des chemins possibles. Un DSS entre deux points est généralement défini comme la meilleure approximation discrète de la droite continue sous-jacente entre les deux points. Dans cet article, nous introduisons une autre définition qui fait écho à des approches dites de tous les chemins possibles de la physique des particules. Le cosmologiste George Ellis a récemment fait remarquer, ``Une particule prend tous les chemins qu'elle peut, et ce que nous voyons est la moyenne pondérée de toutes ces possibilités.'' Dans une veine similaire, nous définissons un segment de droite discrète entre deux points comme l'ensemble de pixels le plus rapproché de la moyenne pondérée de tous les chemins discrets possibles de longueur minimale entre les deux points. Cette définition est uniquement destinée à démontrer une relation théorique entre la théorie probabiliste des chemins discrets possibles et les DSSs. Elle n’a pas vocation à remplacer l’algorithme standard de Bresenham (1963) comme moyen pratique pour tracer les segments de droite dans le plan, mais de le justifier par une autre approche. Nous présentons également brièvement l’extension de cette définition dans l’espace à 3 dimensions. Nous présenterons également un nouvel algorithme récursif pour tracer un type de DSS présentant une meilleure autosimilarité que la DSS standard et qui est plus rapide que l'algorithme classique de Bresenham. Pour finir, nous implémenterons l’algorithme de tous les chemins possibles au moyen des automates cellulaires que nous appelons «Mants» (M-fourmis équipées de mémoires mais non réalistes). Il s’avère que le chemin qui est localement le plus probable entre la ``manthill'' et une source d'alimentation pour un individu de la colonie n’est, en général, pas identique à la trajectoire optimale pour la colonie dans son ensemble.

Jeudi 02 avril 2015 à 14h Tom Hirschowitz (LAMA),
Analytic functors on presheaf categories (travail en cours avec Richard Garner, Macquarie Uni, Sydney)

Résumé : (Masquer les résumés)
In denotational semantics, we have a few examples of notions which are easy to describe graphically (and generally informally), but whose algebraic axiomatisation is tedious, to say the least. Such examples include (in order of appearance) Lambek's polycategories, Girard's proof nets, and Lafont's interaction nets. The importance of algebraic axiomatisation of course resides in the induced notion of denotational model. In this work, we propose a generalisation of Joyal's analytic functors to certain presheaf categories, which we then use to directly derive algebraic axiomatisations from elementary graphical information. For concreteness, we instantiate our results on polycategories. The idea is that the pictures generally used to describe the standard operations on polycategories may be understood as a straightforward collection of finite presheaves on a certain category. Our notion of analytic functor then allows us to interpret this collection as an endofunctor on presheaves, which then freely generates a certain monad, whose algebras are precisely polycategories.

Jeudi 26 mars 2015 à 10h Pawel Gladki (Uniwersytet Śląski),
Hyperfields and their applications to Witt equivalence

Résumé : (Masquer les résumés)
In this talk we shall recall the notion of hyperfields, i.e. fields with multivalued addition, provide a collection of examples of hyperfields, and show how they can be used to characterize Witt equivalence of fields. We shall also investigate the Witt equivalence of certain types of fields in some more detail.

Jeudi 12 mars 2015 à 10h30, ENS Lyon TBA (TBA),
Séminaire Chocola

Jeudi 05 mars 2015 à 10h Rodolphe Lepigre et Christophe Raffalli (LAMA),
Mêler combinateurs, continuations et EBNF pour une analyse syntaxique efficace en OCaml

Résumé : (Masquer les résumés)
Partie I (Rodolphe Lepigre) : Le développement de Patoline (un nouveau système de composition de documents) nécessite un parseur extensible d'OCaml sans contrainte, notamment sur l'analyse lexicale. Nous présentons ici un environnement de développement léger pour l'analyse syntaxique, conçu en deux mois pendant l'été 2014 pour répondre à ce besoin. Le système propose une syntaxe intuitive de type BNF, sans récursion à gauche. Les parseurs sont traduits vers des expressions OCaml utilisant DeCaP, notre bibliothèque de combinateurs monadiques, et sont donc des expressions de première classe. Pour optimiser les combinateurs, nous utilisons des continuations et une méthode de prédiction des premiers caractères acceptés par une grammaire. Sur la grammaire d'OCaml, on obtient en moyenne une analyse cinq fois plus lente qu'avec le parseur d'origine et deux fois plus rapide qu'avec Camlp4. De plus, on dispose de combinateurs inspirés de la notion de continuation délimitée pour optimiser les grammaires. Notons que nous gérons aussi les grammaires ambigües. Partie II (Christophe Raffalli) : Parser combinators are popular among functional programmers because they can be used to define languages parameterised by other languages and benefit from the strong type systems of the host language. Parser combinators have the reputation of being slow... However, with a few improvement, they become no more than five to ten times slower than stack automaton. It is easy to translate a BNF-like syntax into calls to combinators while keeping there advantages. However one main drawback remains: left recursion is forbidden. Although left recursion can easily be eliminated from a context free grammar, the presence of parametrised grammars requires more: a fixpoint combinator compatible with left recursion.

Jeudi 26 février 2015 à 10h Andrea Frosini (Università degli Studi di Firenze),
Pattern avoiding polyominoes

Résumé : (Masquer les résumés)
The concept of pattern within a combinatorial structure is an essential notion in combinatorics, whose study has had many developments in various branches of discrete mathematics. Among them, the research on permutation patterns and pattern-avoiding permutations has become very active. Nowadays, these researches have being developed in several other directions, one of them concerning the definition and the study of an analogue concept in other combinatorial objects. Some recent studies are presented here, concerning patterns in bidimensional structure, and, specifically, inside polyominoes. After introducing polyomino classes, I present an original way of characterizing them by avoidance constraints (namely, with excluded submatrices) and I discuss how canonical such a description by submatrix-avoidance can be. I also provide some examples of polyomino classes defined by submatrix-avoidance, and I conclude with some hints for future research on the topic.

Jeudi 05 février 2015 à 10h30, ENS Lyon TBA (TBA),
Séminaire Chocola

Jeudi 29 janvier 2015 à 14h Jean-Louis Verger-Gaugry (LAMA),
Problème de Lehmer et fonctions zeta dynamiques limites

Résumé : (Masquer les résumés)
En 1933 Lehmer enonce le problème suivant : existe-t-il une constante c > 0 telle que la mesure de Mahler M(α) de tout nombre algébrique α non nul et différent d’une racine de l’unité vérifie M(α) ≥ 1 + c. La Conjecture de Lehmer affirme que oui (C. Smyth, ”Survey”, 2014). Pour la tester de nombreuses familles de nombres algébriques tendant vers 1 ont été considérées. Il s'agit d’un problème limite et de minoration de M (ou de la hauteur pour des courbes elliptiques ou des variétés Abéliennes). Un autre problème limite ouvert est de caractériser le premier dérivé de l'ensemble des nombres de Salem T. Une première conjecture de Boyd dit que la réunion S ∪ T des ensembles des nombres de Pisot et de Salem est fermé. Une deuxième conjecture de Boyd affirme que le premier dérivé de l'ensemble des nombres de Salem est l'ensemble des nombres de Pisot. A chaque nombre algébrique réel β > 1 on peut souvent associer trois fonctions zeta dynamiques : (i) la fonction zeta d’Artin-Mazur de la beta-transformation ζ_β(z), qui provient du système dynamique de numération de Rényi-Parry, la base ́étant β; (ii) pour un polynôme P de petit hauteur s’annulant sur β, la fonction zeta de Lefshetz ζ_{L,β,P}(z), qui provient d’un automorphisme du tore n-dimensionnel, où n = deg P, et (iii) la fonction zeta d’Artin-Mazur ζ{AM,β,P}(z), qui provient de la même action sur le tore n-dimensionnel. Si (β_i) est une suite convergente de nombres algebriques, une question fondamentale est de savoir si les fonctions zeta limites peuvent apporter des solutions ou un éclairage nouveau sur ces questions ; par exemple, caractériser la limite des ensembles de pôles des fonctions ζ_{β_i}(z) lorsque i tend vers l'infini. En effet, le contrôle de la hauteur peut donner lieu à des phénomènes d'équidistribution limite de conjugués sur le cercle unité (Bilu, Petsche, Pritsker). On prendra l'exemple d'une famille F de nombres de Perron, qui tendent vers 1, racines dominantes de trinômes de hauteur 1 non réciproques, et de petite mesure de Mahler. On montrera que les développements asymptotiques (de Poincaré) des pôles des fonctions ζ_{β_i}(z) permettent d'obtenir le développement asymptotique de la mesure de Mahler et de prouver directement que la conjecture de Lehmer est vraie pour la famille F.

Jeudi 22 janvier 2015 à 10h Pierre Hyvernat (LAMA),
Représentation des fonctions continues entre ``streams'' (& Co.) par des types de données

Résumé : (Masquer les résumés)
(Travail avec Peter Hancock) Brouwer savait déjà que les fonctions continues entre stream (avec la topologie produit habituelle) pouvaient être représentées par des arbres infinis. Peter Hancock a montré comment transformer ce ``théorème de représentation'' en théorie des types dépendant permettant de manipuler ces fonctions comme un type de données standard. Nous avons récemment pu généraliser ces idées à de nombreux types de données coinductifs en utilisant la notion de ``structure d'interaction'' (ou ``container indexé'' ou ``foncteur polynomial''). J'essaierais d'introduire les notions nécessaire au fur et à mesure : types dépendants, définitions inductives et coinductives, définitions inductive-récursives, etc.

Jeudi 15 janvier 2015 à 10h Xavier Urbain (ENSIIE/CNAM),
Un cadre pour la preuve formelle adapté aux réseaux de robots mobiles

Résumé : (Masquer les résumés)
Les réseaux de robots mobiles reçoivent depuis quelques années une attention croissante de la part de la communauté de l'algorithmique distribuée. Si l'utilisation d'essaims de robots coopérant dans l'exécution de diverses tâches est une perspective séduisante, l'analyse de la faisabilité de certaines tâches dans ce cadre émergent est extrêmement ardue, en particulier si certains robots présentent des comportements dits byzantins, c'est-à-dire arbitraires voire hostiles.

Pour obtentir des garanties formelles dans ce contexte, nous proposons un cadre mécanique formel fondé sur l'assistant à la preuve Coq et adapté aux réseaux de robots. Nous nous intéressons en particulier aux résultats d'impossibilité, fondamentaux en algorithmique distribuée en ce sens qu'ils établissent ce qui peut ou ne peut pas être réalisé et permettent de définir des bornes et, par là, l'optimalité de certaines solutions. Utiliser un assistant comme Coq travaillant à l'ordre supérieur nous permet d'exprimer aisément des quantifications sur les algorithmes, ceux-ci étant considérés comme des objets abstraits. Nous illustrons les possibilités offertes par notre développement en présentant les premières preuves formelles (et donc certifications) de certains résultats comme l'impossibilité de la convergence de robots amnésiques lorsqu'un tiers d'entre eux sont byzantins, ou encore l'impossibilité du rassemblement pour un nombre pair de robots évoluant dans R.

Le séminaire de l’équipe LIMD est sous la responsabilité de Xavier Provencal.
Options : Voir par date croissante . Masquer les résumés.
Autres années : 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, toutes ensemble.