2016


Retour à la vue des calendrier
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.
Mardi 31 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Counting connected graphs with large excess
Description: Élie de Panafieu We enumerate the connected graphs that contain a linear number of edges with respect to the number of vertices. So far, only first term of the asymptotics and a bound on the error were known (Bender Canfield McKay 1995, Pittel Wormald 2005, van der Hofstad Spencer2006). We present a proof based on analytic combinatorics, i.e. generating function manipulations, and derive the complete asymptotic expansion.
Lundi 20 Juin
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Towards narrative generation of spatial experiences in service robots
Description: Jorge Garcia Flores We propose a first approximation to the generation of narrative
experiences by a service robot. The goal of such narratives is to
communicate in a brief, structured and natural way what the robot
recently experienced while solving a task. We structure the narrative's
elements into blocks guided by the spatial areas the robot visited. We
also include a mechanism to mention failures, and template-based natural
language generation. At this state of our research we include movement,
manipulation and visual events. We evaluate our approach comparing the
generated narratives with descriptions produced by humans after having
followed the same robot's trajectory and performed the same robot's
activities. We use the ROUGUE-L automatic evaluation metric and a survey
in order to measure the narrative quality of the robot's description.
Results show that while the robot generated narratives have close to
human completeness scores, they still lack of readability and fluency.