2014


Retour à la vue des calendrier
Mardi 16 Septembre
Heure: 12:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Lexicographical polytopes
Description: Michele Barbato Within a fixed integer box of R^n, the lexicographical polytopes are the convex hulls of the integer points that are lexicographically between two given integer points. We prove that, together with the bounds, the linear inequalities that arise naturally when characterizing those points suffice to describe these polytopes. As a consequence, this family of integer polytopes is closed by intersection.
Beside, we prove that lexicographical polytopes are precisely the superincreasing knapsacks described by Gupte. Our contribution is to provide significantly simpler and shorter proofs.
This is a joint work with Roland Grappe, Mathieu Lacroix and Clément Pira.
Mardi 23 Septembre
Heure: 12:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Vérification distribuée par exploration d'un espace de paramètres
Description: Camille Coti Dans cet exposé, je présenterai un travail effectué avec Étienne André et Sami Evangelista portant sur la parallélisation d'un algorithme de vérification par exploration d'un espace de paramètres dans le but d'établir un ensemble de contraintes.

Ces contraintes forment un pavage de cet espace de paramètres par des polyèdres irréguliers. La parallélisation de cette exploration ne peut alors pas s'effectuer en utilisant une décomposition de domaine classique, du fait du caractère irrégulier des polyèdres obtenus. Nous avons implémenté et évalué deux heuristiques de décomposition du calcul entre les processus parallèles et examiné leurs performances.

Ce travail a été présenté à la conférence EuroMPI/Asia 2014.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: soutenance de thèse
Description: Nguyen Nghia Hoang
Lundi 29 Septembre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Peuplement d'ontologies par des techniques de TAL
Description: Frédérik Bilhaut La société NOOPSIS, éditeur de logiciels de "text-mining" et "knowledge management" issu du laboratoire GREYC en 2008, vient présenter des expérimentations réalisées dans le domaine du "Knowledge Base Population" (KBP). Le cadre général de ces travaux est l'utilisation de modèles linguistiques et sémantiques permettant d'instancier automatiquement des bases de connaissances au format RDF du W3C. Nous nous intéresserons principalement au sujet de l'instanciation de ressources et de prédicats par la reconnaissance d'entités et la "tripletisation" de procès linguistiques. Les techniques de TAL employés impliquent la reconnaissance d'entités et surtout une analyse syntaxico-sémantique de différents phénomènes prédicatifs. Nous évoquerons également des problématiques connexes comme l'identification automatique de classes, ou encore des questions liées à la représentation des procès dans le modèle RDF. L'objectif de la rencontre est d'exposer des applications pratiques de ces méthodes et leurs modalités d'implémentation, d'identifier des pistes potentielles de collaboration, et si possible de discuter les pistes à suivre.
Mardi 30 Septembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Polynomials invariants on stranded graphs
Description: Joseph Ben Geloun Tutte polynomial is a 2-variable polynomial defined on a graph whichsatisfies a contraction/deletion recurrence relation. This polynomialgeneralizes into the so-called Bollobas-Riordan (4-variable) polynomial forribbon graphs which also satisfies a similar recurrence rule. In the recentPhysics literature, there exists a growing interest for a new category ofgraphs called rank d stranded graphs. Such graphs encompass simple andribbon graph structures and represent simplicial complexes in any dimensiond. I will introduce a genuine 7-variable polynomial on these graphstructures when restricted in rank 3 and when provided with a specificcoloring. The polynomial satisfies a new contraction/cut rule. The procedurecan be certainly extended in any rank.
Mardi 7 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Le langage asymptotique des courbes lisses
Description: Thierry Monteil Le tracé d'une courbe sur une grille produit une suite de pixels consécutifsqui peut être représentée par un mot sur l'alphabet {droite, haut, gauche,bas}. Ce codage établit un dictionnaire entre objets géométriques (oudifférentiels) et propriétés combinatoires sur les mots. Par exemple, lecodage des segments de droites correspond aux mots dits 1-équilibrés, quisont les facteurs finis des mots sturmiens.Une méthode classique pour analyser une courbe lisse discrétisée consiste àdécomposer son codage en mots 1-équilibrés maximaux, qui servent alors detangentes discrètes. Sans ajout d'hypothèses, les estimateurs de tangentesou de courbure associés ne convergent pas nécéssairement lorsque la maillede la grille tend vers zéro.Une raison possible est la suivante : certains mots non 1-équilibrés peuventapparaître dans le codage de courbes lisses pour des mailles arbitrairementfines.Let but de cet exposé est de décrire ce langage et voir ce qu'on peut luifaire dire.
Jeudi 9 Octobre
Heure: 16:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Unfolding-based Reachability Checking of Petri Nets
Description: César Rodríguez In model checking, a well known source of state-space explosion (SSE) is
the explicit representation of concurrent actions by their interleavings.
Partial-order reductions attempt to address this by constructing an
equivalent state space where irrelevant executions of the original are
discarded. A comparatively less well-known approach emerges from the use
of partial-order semantics, where the state space is instead represented by
a partial order where concurrent actions are simply left unordered. Petri
net unfoldings are arguably the most prominent verification technique
issued from this idea.

In this talk, three different semantics for Petri nets will be presented,
the last one of which will be the aforementioned unfolding semantics. We
will then see how unfoldings can be employed in practical verification and,
time permitting, how to improve the method to address additional sources of
SSE.
Lundi 13 Octobre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: (Digital) goodies from the ERC Wishing Well: BabelNet, Babelfy, video games with a purpose and the Wikipedia bitaxonomy
Description: Roberto Navigli Multilinguality is a key feature of today’s Web, and it is this feature that we leverage and exploit in our research work at the Sapienza University of Rome’s Linguistic Computing Laboratory, which I am going to overview and showcase in this talk.

I will start by presenting BabelNet 2.5 (http://babelnet.org), a very large multilingual encyclopedic dictionary and semantic network, which covers 50 languages and provides both lexicographic and encyclopedic knowledge for all the open-class parts of speech, thanks to the seamless integration of WordNet, Wikipedia, Wiktionary, OmegaWiki, Wikidata and the Open Multilingual WordNet.

Next, I will present Babelfy (http://babelfy.org), a unified approach that leverages BabelNet to perform word sense disambiguation and entity linking in arbitrary languages, with performance on both tasks on a par with, or surpassing, those of task-specific state-of-the-art supervised systems.

In the third part of the talk I will present two approaches to large-scale knowledge acquisition and validation: video games with a purpose, a novel, powerful paradigm for the large scale acquisition and validation of knowledge and data, and WiBi (http://wibitaxonomy.org), our approach to the construction of a Wikipedia bitaxonomy, that is, the largest and most accurate currently available taxonomy of Wikipedia pages and a taxonomy of categories, aligned to each other.

Bio:

Roberto Navigli is an Associate Professor in the Department of Computer Science of the Sapienza University of Rome. He was awarded the Marco Cadoli 2007 AI*IA Prize for the best doctoral thesis in Artificial Intelligence and the Marco Somalvico 2013 AI*IA Prize for the best young researcher in AI. He is the recipient of an ERC Starting Grant in computer science and informatics on multilingual word sense disambiguation (2011-2016) and a co-PI of a Google Focused Research Award on Natural Language Understanding.
His research lies in the field of Natural Language Processing (including word sense disambiguation and induction, ontology learning from scratch, large-scale knowledge acquisition, open information extraction and relation extraction).
He has served as an area chair of ACL, WWW, and *SEM, and a senior program committee member of IJCAI. Currently he is an Associate Editor of the Artificial Intelligence Journal, a member of the editorial board of the Journal of Natural Language Engineering, a guest editor of the Journal of Web Semantics, and a former editorial board member of Computational Linguistics.
Mardi 14 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Transcendence et algorithme de remplacement
Description: Gérard Duchamp
Mardi 21 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A general theory of Wilf-equivalence for Catalan structures
Description: Mathilde Bouvel It is a commonly observed phenomenon in enumerative combinatorics thatseveral combinatorial classes share the same enumeration. For any twoclasses which seem to have the same enumeration sequence, a naturalproblem is to prove that it is indeed the case, ideally with abijective proof that allows to map the structure of one class to thatof the other.Such coincidences of enumeration are called Wilf-equivalences in thecontext of pattern-avoiding permutation classes (the definition ofpattern-avoidance will be given during the talk). Wilf-equivalence hasbeen a popular topic in the research on pattern-avoiding permutations,from its beginnings in the seventies until now. It is fair to say thatmost of the works done so far are specific to given pairs ofequi-numerous classes, thus forming a sort of "case-by-case catalogue"of the known Wilf-equivalences.In this talk, we explore a different approach: we are interested indescribing all Wilf-equivalences between permutations classes definedby the avoidance of two patterns: 231 and an additional pattern p(w.l.o.g., we can assume that p itself avoids 231). We will explainthat this is one way of phrasing a seemingly more general (butactually equivalent) question: that of describing allWilf-equivalences between classes of Catalan objects subject to onefurther avoidance restriction. Such classes are denoted Av(A), A beinga Catalan object.Our results, to be presented in the talk, are the following.First, we define an equivalence relation ~ among Catalan objects. Ourmain result is that it refines Wilf-equivalence: if A ~ B, then Av(A)and Av(B) have the same enumeration. The proof is subdivided inseveral cases, and it is bijective in all cases but one. We furtherconjecture that the converse statement holds, i.e., that this relation~ coincides with Wilf-equivalence.Then, we show how to enumerate the number of equivalence classes for~, hereby providing an upper bound on the number of Wilf-equivalenceclasses.It is also interesting to study a special ~-equivalence class, whichcan be understood at a very fine level of details. Our results on this~-class (called the "main" one) unify and generalize several resultsof the literature on Wilf-equivalence.Finally, we explain how our bijective cases in the proof of the maintheorem can often be refined to provide comparison results between theenumerations of classes Av(A) and Av(B) when A and B are notequivalent for ~. A consequence is that the "main" ~-class correspondsto the largest possible enumeration sequence.This is a joint work with Michael Albert (University of Otago), and apreprint is available at arXiv:1407.8261.
Jeudi 23 Octobre
Heure: 15:30 - 16:30
Lieu: Salle A303
Résumé: The implementation of GPGPU for Model Checking Problems
Description: WU Zhimin In this presentation, I will introduce the implementation of GPGPU
techniques in model checking area. I target Nvidia GPU so firstly, the
latest CUDA Compute Architecture will be introduced, together with the key
points of GPU Program optimization. Then I will refer to some existing
research on GPU accelerated Model Checking Problems. Finally, I will
briefly introduce my research work. (This will be an informal presentation.)
Vendredi 24 Octobre
Heure: 10:30 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Construction de l'exponentielle libre en logique linéaire
Description: Luc Pellissier Groupe de travail sur une extension des méthodes introduites par Paul-André Melliès et Nicolas Tabareau pour calculer le comonoïde commutatif libre dans une catégorie avec produits (c.-à-d. un modèle de la logique linéaire multiplicative additive). On introduira les concepts nécessaires (PROPs, extensions de Kan, fins, etc.) et on expliquera sous quelles conditions on peut donner une formule close pour le calcul du comonoïde commutatif libre. On verra que ces conditions sont vérifiées dans tous les modèles connus de la logique linéaire, alors que les conditions originalement proposées par Melliès et Tabareau ne sont pas vérifiées par le modèle des espaces de finitude.
Mardi 28 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Graphes d'interaction et équations d'évolution
Description: Gérard Duchamp
Jeudi 30 Octobre
Heure: 15:30 - 16:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Modèles et paradigmes de programmation parallèle distribuée
Description: Camille Coti Dans cette présentation, qui sera plus un panorama qu'un séminaire de recherche, je présenterai quelques grands paradigmes de programmation parallèle distribuée à travers les modèles de mémoire distribuée et de communications inter-processus. Le but de mon exposé sera de présenter comment le caractère distribué des données est représenté et manipulé dans ces paradigmes de programmation afin de réfléchir à quelles techniques de programmation adopter selon les patterns d'accès aux données d'un programme séquentiel que l'on souhaite paralléliser. Je mettrai l'accent sur la mémoire distribuée, la mémoire partagée distribuée, les sacs de tâches, les communications implicites unilatérales et bilatérales, la parallélisation automatique par compilation.