2016


Retour à la vue des calendrier
Mardi 1 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Algèbre de Hopf cambrienne
Description: Grégory Châtel En 1998, Loday et Ronco décrivent une algèbre de Hopf combinatoire dont la base est indicée par des arbres binaires. Cette algèbre possède de nombreux liens avec divers résultats antérieurs. Son produit est en particulier lié aux intervalles du treillis de Tamari, structure d'ordre partiel dont les éléments sont des arbres binaires. En 2006, Reading définit la notion de treillis cambrien d'un groupes de Coxeter. Le treillis Cambrien généralise l'ordre de Tamari en utilisant des structures arborescentes qui généralisent les arbres binaires : les arbres cambriens. Une question naturelle se pose alors : est-il possible de généraliser l'algèbre de Hopf de Loday-Ronco aux arbres cambriens ? Dans cette présentation, j'expliquerai les résultats que nous avons obtenus avec Vincent Pilaud sur les arbres cambriens en type A.
Jeudi 3 Mars
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Parameter Synthesis for Parametric Interval Markov Chains
Description: Laure Petrucci Interval Markov Chains (IMCs) are the base of a classic probabilistic specification theory introduced by Larsen and Jonsson in 1991. They are also a popular abstraction for probabilistic systems. In this paper we study parameter synthesis for a parametric extension of Interval Markov Chains in which the endpoints of intervals may be replaced with parameters. In particular, we propose constructions for the synthesis of all parameter values ensuring several properties such as consistency and consistent reachability in both the existential and universal settings with respect to implementations. We also discuss how our constructions can be modified in order to synthesise all parameter values ensuring other typical properties. Joint work with Benoît Delahaye and Didier Lime
Vendredi 4 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Caractérisation impérative des algorithmes séquentiels en temps quelconque, primitif récursif et polynomial
Description: Yoann Marquer Les fonctions calculables ont été formalisées par différents modèles de calcul (récursion, lambda-calcul, machines de Turing) ayant le même comportement entrées-sortie : c'est la thèse de Church. Par exemple, une machine de Turing à un ruban peut simuler les résultats calculés par une machine à deux rubans. Pourtant, pour la reconnaissance de palindrome la machine à un seul ruban nécessite une complexité en temps supérieure. Ainsi, il faut étudier les étapes intermédiaires. Nous définissons donc une simulation pas à pas entre exécutions, utilisant uniquement des variables temporaires et une dilatation temporelle.


La thèse de Church concernait donc les fonctions, et il nous faut une nouvelle thèse pour les algorithmes. Nous avons choisi celle de Gurevich pour sa présentation axiomatique : un algorithme séquentiel est un objet vérifiant les trois postulats de temps séquentiel, d'états abstraits et d'exploration bornée. De plus, il a montré que les algorithmes séquentiels coïncident avec son modèle des Abstract State Machines. Nous dirons donc qu'un modèle de calcul est algorithmiquement complet s'il existe une simulation mutuelle d'exécutions entre lui et les ASMs.


Pour obtenir des résultats sur des modèles de calcul plus usuels, nous formalisons les langages impératifs par un système de transition. En étudiant leur sémantique opérationnelle pas à pas et en développant une notion de graphe d'exécution, nous montrons qu'une variante du langage While de Jones est algorithmiquement complète. Ce résultat étant à structures de données près, il correspond donc à une équivalence entre les structures de contrôle des ASMs et des langages impératifs. De plus, étant préoccupés par la faisabilité des algorithmes, nous montrons que les structures du premier ordre utilisées par Gurevich permettent bien d'implémenter les structures de données usuelles.


Notre soucis de la faisabilité nous a également conduit à étudier en terme de complexité implicite deux restrictions des ASMs : celles en temps primitif récursif (les opérations usuelles et terminales) et celles en temps polynomial (les exécutions réalistes). Nous montrons d'une part que si les structures de données sont également primitives récursives, alors une variante LoopC du langage Loop de Meyer et Ritchie est complète pour les algorithmes en temps primitif récursif. D'autre part, une restriction syntaxique LoopCstat de LoopC est complète pour les algorithmes en temps polynomial, sans restriction sur les structures de données et en caractérisant syntaxiquement le degré du polynôme.
Vendredi 11 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Interaction Graphs and Quantitative Semantics
Description: Thomas Seiller Interaction Graphs (IG) models were introduced as a generalisation of Girard’s Geometry of Interaction (GOI) constructions based on the interpretation of proofs as (finite, weigthed) graphs. Recent results use IG models to bring into vision a new relation between dynamic and denotational semantics.
The first contribution of this work is the definition of categories of triskells, which generalises both the bicategory of spans and the categories of matrices and arrays over a semiring (also known as categories of weighted relations). Secondly, it sheds light onto a new relationship between dynamic and quantitative denotational semantics for multiplicative linear logic (MLL), providing formal grounds to the claim that IG models are a quantitative generalisation of dynamic semantics, i.e. GOI and game semantics. Finally, this functor is shown to preserve not only the interpretation of proofs but also induced double-glueing refinements: it is shown to lift to a map from the double-glueing construction defining IG models to the double-glueing construction yielding coherence spaces. For this purpose, a very general notion of quantitative coherence spaces is introduced, and shown to model full linear logic.
Mardi 15 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Partitions d'entiers et groupes de Coxeter
Description: Mathias Pétréolle En 2009, Han a redécouvert et généralisé une identité due à Nekrasovet Okounkov, qui fait un lien entre d'un coté, les puissances de lafonction êta de Dedekind, et de l'autre les partages d'entiers et leurslongueurs d'équerres. Pour cela, il utilise la formule de Macdonald pourle système affine de racines de type A. Je montrerai comment, à l'aidede bijections, il est possible de démontrer des identités deNekrasov-Okounkov pour d'autres types de systèmes de racines (typeaffine C et D notamment), et je présenterai les nouvelles formules deséquerres qui en découlent.Dans une seconde partie, je présenterai la notion d'élémentscycliquement pleinement commutatifs dans les groupes de Coxeter, qui ontété introduits pour étudier une version cyclique d'un théorème deMatsumoto. Je montrerai ensuit comment, en utilisant la théorie desautomates finis, on peut démontrer que la série génératrice de ceséléments est une fraction rationnelle, quelque soit le groupe de Coxeterconsidéré.
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Treillis cambriens et treillis de Tamari : graphes dirigés et groupes de Coxeter
Description: François Viard
Vendredi 18 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Open Call-by-Value
Description: Giulio Guerrieri The elegant theory of the call-by-value lambda-calculus relies on
weak evaluation and closed terms, that are natural hypotheses in
the study of programming languages. To model proof assistants,
however, strong evaluation and open terms are required, and it is
well known that the operational semantics of call-by-value becomes
problematic in this case, as first pointed out by Paolini and Ronchi
della Rocca. Here we study the intermediate setting—that we call
Open Call-by-Value—of weak evaluation with open terms, on top
of which Grégoire and Leroy designed the abstract machine of Coq.
Various calculi for Open Call-by-Value already exist, coming from
logical, semantical, or implementative points of view, each one with
its pros and cons. This paper presents a detailed comparative study
of their operational semantics. First, we show that all calculi are
equivalent from a termination point of view, justifying the slogan
Open Call-by-Value. Second, we compare their equational theories.
Third, we present a detailed quantitative analysis of the time cost
model. Four, we introduce a new simple abstract machine, and
prove it a reasonable implementation of Open Call-by-Value with
respect to its cost model. Along the way, there emerges a sharp
deconstruction of call-by-value evaluation and of the complexity of
its implementations.

(Joint work with Beniamino Accattoli)
Lundi 21 Mars
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Apprentissage partiel de dépendances syntaxiques et application au transfert cross-lingue
Description: Ophélie Lacroix L'apprentissage supervisé est largement utilisé dans le domaine du TAL mais requiert l'exploitation de données correctement annotées. Nous nous intéressons en particulier au cas de l'analyse syntaxique en dépendances et montrons qu'il est possible d'apprendre un analyseur par transition à partir de données partiellement annotées.
Ce procédé est notamment profitable dans le cas du transfert d'annotations cross-lingue pour lequel les informations syntaxiques (les dépendances) sont projetées d'une langue source (bien dotée) à une langue cible (peu dotée) via des liens d'alignements. Les données partiellement annotées générées à partir de cette méthode permettent d'appre ndre des analyseurs en dépendances pour les langues ciblées. Cette méthode simple de transfert obtient des performances qui rivalisent avec celles de méthodes état-de-l'art récentes, tout en ayant un coût algorithmique moindre.
Mardi 22 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorial Optimization subject to PDE constraints
Description: Christoph Buchheim We investigate a class of optimal control problems where the control parameters are binary variables, which are supposed to be static and probably subject to combinatorial constraints. Additionally, the problem contains state constraints involving semi-linear elliptic partial differential equations (PDEs). As an example, the binary variables may correspond to the activation of given heat sources attached to a metal sheet, the optimization problem then consists in switching on the smallest number of heat sources such that the point-wise temperature of the metal sheet is in a specified range. Our main result is that each state is a concave function in the binary control vector. This allows us to define an outer approximation scheme in which we alternate between the solution of a non-linear PDE and an integer linear program. Using this approach, we can solve instances on up to 2000 binary variables to global optimality.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Calculer dans un automate cellulaire unidirectionnel réversible : vers l'indécidabilité de la périodicité?
Description: Martin Delacourt On s'intéresse au parallèle entre 2 problèmes sur des modèlesdistincts d'automates. D'une part, les automates de Mealy(transducteurs lettre à lettre complets) qui produisent dessemi-groupes engendrés par les transformations sur les mots infinisassociées aux états. En 2013, Gillibert a montré que le problème de lafinitude de ces semi-groupes était indécidable. En revanche laquestion est ouverte dans le cas où l'automate de Mealy produit un groupe. D'autre part, les automates cellulaires unidirectionnels pourlesquels la question de la décidabilité de la périodicité est ouverte.On peut montrer l'équivalence de ces problèmes. On fera un pas dans cette étude en montrant qu'il est possible desimuler du calcul Turing dans un automate cellulaire unidirectionnelréversible, rendant ainsi des problèmes de prédiction indécidablesainsi que la question de la périodicité partant d'une configuration finie.
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Lattice paths in 3D
Description: Axel Bacher
Vendredi 25 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: String diagrams for Proof nets
Description: Matteo Acclavio Sequentialization of MELL proof nets needs additional tools extern to interaction nets syntax: connectivity, switchings, boxes and jumps. In this talk we introduce string diagrams syntax for monoidal categories in order to present a model for proof nets (with the relative cut elimination) with a unique local sequentialization criterion for MLL with constants and an idea for a generalization of this result for MELL proof nets.
Mardi 29 Mars
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Regulated Grammars and Automata
Description: Alexander Meduna
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Lattice paths in 3D
Description: Axel Bacher
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Regulated Grammars and Automata
Description: Alexander Meduna
Mardi 5 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Tenseurs et physique combinatoire
Description: Sylvain Carrozza
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatoire des mots
Description: Svetlana Puzynina
Mardi 12 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Codes, cryptographie et combinatoire
Description: Valentin Suder
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Métriques extrémales et plongements de graphes
Description: Alfredo Hubard Dans cet exposé je présenterai des résultats dans l' intersection de lagéométrie Riemannienne et la topologie algorithmique. Plus précisément, jediscuterai des manières effectives de planariser une surface triangulée, desproblèmes de nombre de croisements, et de la "meilleure" métrique Riemanniennepour une surface. Si le temps le permet, je parlerai également des défis enhaute dimension et des connections avec les nombres de faces des complexessimpliciaux.
Mardi 19 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On Noncrossing Partitions for the Alternating Groups
Description: Henri Mühle The lattice of noncrossing set partitions of an n-set can beseen as a subgraph of the Cayley graph of the symmetric group S generated by all transpositions. We mimic thisconstruction for the alternating group A2n+1 generated byall 3-cycles. The resulting poset provides a rich new source ofcombinatorics coming from the alternating groups, which in some senseparallels the combinatorics behind the noncrossing set partitions. Wepresent some enumerative and bijective results, and suggest an extensionof this construction to all finite Coxeter groups. This is joint workwith Philippe Nadeau.
Vendredi 22 Avril
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: New Results on Morris's Observational Theory: the benefits of separating the inseparable
Description: Giulio Manzonetto We study the theory of contextual equivalence in the untyped lambda-calculus, generated by taking the normal forms as observables. Introduced by Morris in 1968, this is the original extensional lambda theory H+ of observational equivalence.
On the syntactic side, we show that this lambda-theory validates the omega-rule, thus settling a long-standing open problem. On the semantic side, we provide sufficient and necessary conditions for relational graph models to be fully abstract for H+. We show that a relational graph model captures Morris's observational pre-order exactly when it is extensional and lambda-König. Intuitively, a model is lambda-König when every lambda-definable tree has an infinite path which is witnessed by some element of the model.
Joint work with Flavien Breuvart, Domenico Ruoppolo & Andrew Polonsky
Vendredi 29 Avril
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: La hiérarchie du temps logarithmique
Description: Damiano Mazza Pendant le développement de travaux en cours avec Cynthia Kop et Jakob Simonsen j'ai eu l'occasion d'étudier un peu plus de près la classe de complexité LH, ou hiérarchie en temps logarithmique, qui est peut-être plus connue dans sa version non-uniforme sous le nom de AC^0 (circuits booléens avec fan-in arbitraire, de taille polynomiale et profondeur constante). Je vais vous parler un peu de cette hierarchie et plus en particulier de son niveau 0, appelé DLOGTIME, qui constitue probablement l'une des plus petites classes de complexité ayant un emploi non-trivial en complexité algorithmique.
Lundi 2 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Neoveille, état d'avancement du projet
Description: Emmanuel Cartier Neoveille est un projet financé par SPC qui vise à construire une plateforme de repérage, d'analyse et de suivi des néologismes sur gros corpus, en sept langues (français, portugais du Brésil, tchèque, grec, polonais, russe, chinois).
Nous rappellerons les objectifs globaux du projet avant d'évoquer les différents composants de la plateforme dans le détail : récupération automatique de corpus en sept langues; repérage automatique des néologismes de forme; indexation dans le moteur de recherche et d'analyse.
Finalement, nous évoquerons les pistes de travail à venir.
Lundi 9 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Motifs pour la caractérisation des genres textuels et des styles
Description: Dominique Legallois
Mardi 10 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Partially ordered sets
Description: Henri Mühle
Jeudi 12 Mai
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Agrégation souple et adaptative des graphes hétérogènes avec des attributs hétérogènes
Description: Amine Louati In the enterprise context, people need to exploit, interpret and mainly visualize dierent types of interactions between heterogeneous objects. Graph model is an appropriate way to represent those interactions. Nodes represent the individuals or objects and edges represent the relationships between them. However, extracted graphs are in general heterogeneous (i.e., composed of different node attributes and different relationship types) and large sized which makes it diffcult to visualize and to analyze easily. An adaptive aggregation operation is needed to have more understandable graphs in order to allow users discovering underlyin g information and hidden relationships between objects. Existing graph summarization approaches such as k-SNAP are carried out in homogeneous graphs where nodes are described by the same list of attributes that represent only one community. The aim o f this work is to propose a general tool for graph aggregation which addresses both homogeneous and heterogeneous graphs. To do that, we develop a new soft and adaptive approach to aggregate heterogeneous graphs using the definition of Rough Set Theory (RST) combined with Formal Concept Analysis (FCA), the well known K-Medoids and the hierarchical clustering methods. Aggregated graphs are produced according to user-selected node attributes and relationships. To evaluate the quality of the obtained summaries, we propose two quality measures that evaluate respectively the similarity and the separability of groups based on the notion of common neighbor nodes. Experimental results demonstrate that our approach is effective for its ability to produce a high quality solution with relevant interpretations.
Mardi 17 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Analytic combinatorics
Description: Bernhard Gittenberger
Mercredi 18 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Vers la conception formelle de systèmes d’édition collaborative consistants
Description: Hanifa Boucheneb Les systèmes d’édition collaborative permettent à un groupe d’utilisateurs de partager et modifier des objets (textes, images, d ocuments XML, etc.) via le Web. Pour une meilleure réactivité aux opérations d’édition, ces systèmes sont en général basés sur la réplication des données. Chaque utilisateur a donc sa propre copie (locale) de l’objet qu’il peut modifier. Les modifications (opérations) locales sont ensuite propagées et intégrées aux autres copies. Un des défis majeurs de ces systèmes est d’assurer la consistance des données répliquées. Ce séminaire présentera et discutera les principales approches d’intégration des modifications non locales, proposées dans littérature. Il considérera ensuite les approches basées sur la transformation des opérations (OT) et montrera comment utiliser les méthodes formelles (model-checking symbolique et synthèse de contrôleur) pour vérifier si une approche OT assure la consistance des données répliquées et synthétiser une approche OT qui assure la consistance des données répliquées.
Lundi 23 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Modèles neuronaux pour la traduction automatique
Description: Alexandre Allauzen Les modèles neuronaux occupent aujourd'hui dans le traitement
automatique des langues (TAL) une place importante car ils permettent
grâce à leur caractère continu des avancées significatives dans de
nombreux domaines applicatifs. Historiquement, les modèles de langue
neuronaux ont été une des premières réalisations marquantes, avec des
applications en reconnaissance automatique de la parole (RAP), puis à
d'autres tâches complexes de modélisation linguistique, comme par
exemple l'analyse syntaxique, l'estimation de similarité sémantique, les
modèles d'alignement de mots et en traduction automatique statistique.
L'exposé décrira les travaux menés au LIMSI-CNRS sur les réseaux
neuronaux appliqués principalement à la traduction automatique: les
modèles de langues n-grammes à grand vocabulaire, puis leur extension
aux modèles de traduction et leur apprentissage discriminant.
Mardi 24 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Physical models and Tracy-Widom
Description: Peter Nejjar
Mercredi 25 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On the reconstruction of trees from their U-polynomial.
Description: José Aliste-Prieto The U-polynomial of a graph was introduced by Noble and Welsh as a generalization of some invariants coming from Knot theory. It also generalizes the chromatic symmetric function of Stanley. In this talk, we will consider the problem of whether there exist non-isomorphic trees
with the same U-polynomial (or,equivalently, with the same chromatic symmetric function).

We will survey what is know about the U-polynomial and this problem. In particular, we will show how to recover some classic invariants from the U-polynomial and we exhibit several subclasses of trees for which a solution of this problem is known. FInally, we construct some non-isomorphic trees with "almost" the same U-polynomial, based on solutions of an old problem in Number theory due to Prouhet-Tarry-Escott.