Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > LIFO seminars (french)

Site en Français



Contact

LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2

Email: contact.lifo
Tel: +33 (0)2 38 41 99 29
Fax: +33 (0)2 38 41 71 37



LIFO seminars (french)


Accès par année : 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024

Sauf exception, les séminaires se déroulent le lundi de 14h à 15h, Salle de réunion 1, bâtiment IIIA (voir plan du campus).


07/12/2012 : Soutenance de thèse : Classification non supervisée : de la multiplicité des données à la multiplicité des analyses
Jacques-Henri Sublemontier (LIFO) Résumé
Attention : Débute à 13 h 30. Lieu : Salle des thèses, bâtiment S

28/11/2012 : Soutenance de thèse : Analyses sécuritaires de code de carte à puce sous attaques physiques simulées
Xavier Kauffmann (LIFO) Résumé
Attention : Lieu : Amphithéâtre Turquoise, ENSI de Bourges

26/11/2012 : On Granularity in Data-Parallel Programs Development
Virginia Niculescu (Babes-Bolyai University of Cluj-Napoca) Résumé

08/10/2012 : Detecting Errors in Computational Grammars of Natural Language
Claire Gardent (DR CNRS, LORIA Nancy) Résumé
Attention : Exposé en français

26/09/2012 : Soutenance d'HDR : Contributions à la résolution de contraintes du premier ordre
Khalil Djelloul (LIFO ) Résumé
Attention : Lieu : Amphi H, bâtiment 3IA

17/09/2012 : Generate, Test, and Aggregate - A Calculation-based Framework for Systematic Parallel Programming with MapReduce
Kento Emoto (The University of Tokyo ) Résumé

16/07/2012 : Model Checking régulier pour automate d'arbres à treillis
Valérie Murat (IRISA) Résumé

09/07/2012 : Automatic Refinement of Service Compositions
Umberto Costa (Universidade Federal do Rio Grande do Norte) Résumé

02/07/2012 : Asymptotic Modularity of some Graph Classes, ISAAC '11 (Algotel '12)
Mauricio Soto (LIFO) Résumé
Attention : Débute à 15 h.

25/06/2012 : Mimicking Nature via Self-Assembly
Matthew J. Patitz (University of Arkansas) Résumé

18/06/2012 : An operating system for safe execution of hard real-time and non real-time tasks
Matthieu Lemerre (CEA, LIST, Embedded Real Time Systems Laboratory, Gif-sur-Yvette, France) Résumé

11/06/2012 : On minimum $(K_q;k)$-stable graphs
Andrzej Zak (AGH University of Science and Technology ) Résumé

04/06/2012 : Codes identifiants dans les graphes adjoints
Aline Parreau (Institut Fourier, Université Joseph Fourier de Grenoble) Résumé

15/05/2012 : Similarité et fouille de données
Maria Rifqi (LIP 6) Résumé
Attention : Débute à 10 h 30.

11/05/2012 : A venir
Jean-Charles Lamirel (Université de Strasbourg) Résumé

19/04/2012 : Aspects fondamentaux et applications du problème SAT
Gilles Dequen (Université de Picardie) Résumé
Attention : Débute à 15 h.

19/04/2012 : Déduction automatique appliquée à l'analyse et la vérification de systèmes infinis
Laurent Vigneron (Université de Lorraine - LORIA) Résumé

18/04/2012 : CAPE: Checkpointing Aided Parallel Execution
Eric Renault (Institut Télécom / Télécom SudParis) Résumé

16/04/2012 : Direct Parsing of Discontinuous Constituents
Wolfgang Maier (Université Heinrich Heine de Düsseldorf) Résumé

16/04/2012 : Langages géométriques et polycubes
Hadrien Jeanne (Université de Rouen) Résumé
Attention : Débute à 15 h.

02/04/2012 : Méthodes pour l'estimation du temps de calcul d'un algorithme de branchement : de l'analyse standard à
Nicolas Bourgeois (ESSEC Business School) Résumé

02/04/2012 : Algorithmes paramétrés pour le consensus d'arbres phylogénétiques
Sylvain Guillemot (Iowa State University, Ames, USA) Résumé
Attention : Débute à 15 h.

26/03/2012 : Lattice polynomial functions and their use in qualitative decision making
Miguel Couceiro (Université Paris Dauphine) Résumé

26/03/2012 : Counting independent sets in claw-free graphs
Konstanty Szaniawski ( Warsaw University of Technology, Faculty of Mathematics and Information Science) Résumé
Attention : Débute à 15 h.

19/03/2012 : Complexité paramétrée, algorithmes de noyau et Conflict Packing
Anthony Perez (LIFO) Résumé

12/03/2012 : Modèles de calcul non initialisés
Emmanuel Jeandel (LIF/LIRMM) Résumé

12/03/2012 : Analysis of Microarray Gene Expression Data using Machine Learning Techniques
Marcilio de Sauto (Universidade Federal de Pernambuco, Recife, Brazil) Résumé
Attention : Débute à 15 h.

05/03/2012 : Maximum Metric Spanning Tree made Byzantine Tolerant
Swan Dubois (LIP6 - UPMC Sorbonne Universités) Résumé

20/02/2012 : Extraire et exploiter les descripteurs linguistiques en fouille de textes
Mathieu Roche (LIRMM, Montpellier) Résumé

13/02/2012 : The SANTE Method: Value Analysis, Program Slicing and Test Generation for C Program Debugging
Nikolai KOSMATOV (Software Safety Laboratory, CEA LIST ) Résumé

30/01/2012 : Réseaux de Manhattan dans le plan normé et réseaux de Manhattan orientés.
Nicolas Catusse (LIF) Résumé

23/01/2012 : Coloration des graphes de disques d'unité
Henning Bruhn (Univ. Paris 6) Résumé

16/01/2012 : A clustering algorithm for multiple relational data matrices
Francisco de A. T. de Carvalho (université Fédérale du Pernanbuc, Brésil) Résumé

Résumés des séminaires


Soutenance de thèse : Classification non supervisée : de la multiplicité des données à la multiplicité des analyses Jacques-Henri Sublemontier, LIFO
La classification automatique non-supervisée est un problème majeur, aux frontières de multiples communautés issues de l'Intelligence Artificielle, de l'Analyse de Données et des Sciences de la Cognition. Elle vise à formaliser et mécaniser la tâche cognitive de classification, afin de l'automatiser pour la rendre applicable à un grand nombre d'objets (ou individus) à classer.
Des visées plus applicatives s'intéressent simplement à l'organisation automatique de grands ensembles d'objets en différents groupes partageant des caractéristiques communes. Les objets à classer peuvent être : des clients dans le cadre du marketing, des gènes ou des protéines dans le cadre de la biologie ou des caractères manuscrits dans le cadre de la reconnaissance automatique de caractères. La présente thèse propose des méthodes de classification non-supervisées applicables lorsque les objets peuvent être décrits par plusieurs représentations indépendantes simultanément, ou lorsque plusieurs sources d'informations sont disponibles pour compléter et guider la recherche d'une ou plusieurs classifications des données. Pour la classification non supervisée multi-vues, la première contribution propose un mécanisme de recherche d'une classification des objets multi-représentés permettant d'atteindre des classifications locales adaptées à chaque représentation, ainsi qu'un consensus entre celles-ci. Pour la classification semi-supervisée, la seconde contribution propose d'utiliser des connaissances externes sur les données pour guider et améliorer la recherche d'une classification d'objets mono-représentés par un algorithme quelconque de partitionnement de données. Enfin, la troisième et dernière contribution propose un environnement collaboratif fondé sur la seconde contribution et permettant d'atteindre au choix les objectifs de consensus et d'alternatives pour la classification d'objets mono-représentés ou multi-représentés. Cette dernière contribution répond ainsi aux problèmes de la classification non-supervisée multi-vues, de la classification non supervisée collaborative et de la recherche d'alternatives en classification non supervisée, et propose, au sein d'une même plate-forme unificatrice, une proposition répondant à des problèmes très actifs et actuels en Fouille de Données et en Extraction et Gestion des Connaissances.

MEMBRES DU JURY :
Mme Christel VRAIN, Professeur, université d'Orléans, Directrice de thèse
M Younès BENNANI, Professeur, université Paris XIII, Rapporteur
M Yves LECHEVALLIER, Directeur de Recherche, INRIA Rocquencourt, Rapporteur
M Pierre GANҪARSKI, Professeur, université de Strasbourg, Examinateur
M Stéphane LALLICH, Professeur, université Lumière de Lyon 2,Examinateur
M Guillaume CLEUZIOU, Maître de conférences, université d'Orléans, Co-encadrant
M Lionel MARTIN, Maître de conférences, université d'Orléans, Co-encadrant


Soutenance de thèse : Analyses sécuritaires de code de carte à puce sous attaques physiques simulées Xavier Kauffmann, LIFO
Cette thèse s’intéresse aux effets des attaques par fautes physiques sur le code d’un système embarqué en particulier la carte à puce. De telles attaques peuvent compromettre la sécurité du système en donnant accès à des informations confidentielles, en compromettant l’intégrité de données sensibles ou en perturbant le fonctionnement pendant l’exécution. Dans cette thèse, nous décrivons des propriétés de sécurité permettant d’exprimer les garanties du système et établissons un modèle d’attaque de haut niveau définissant les capacités d’un attaquant à modifier le système. Ces propriétés et ce modèle nous servent à vérifier la sécurité du code par analyse statique ou test dynamique, combinés avec l’injection d’attaques, simulant les conséquences logicielles des fautes physiques. Deux méthodologies sont ainsi développées afin de vérifier le comportement fonctionnel du code sous attaques, tester le fonctionnement des sécurités implémentées et identifier de nouvelles attaques. Ces méthodologies ont été mises en œuvre dans un cadre industriel afin de faciliter le travail du développeur chargé de sécuriser un code de carte à puce. Jury: Examinateurs: - Pascal Berthomé Professeur des Universités, ENSI de Bourges (directeur de la thèse) - Francis Chambérot, Ingénieur responsable développement applicatif embarqués, Oberthur Technologies (co-encadrant de la thèse) - Mirian Halfeld Ferrari Alves, Professeur des Universités, IUT d'Orléans (examinateur) - Jean-François Lalande, Maître de Conférences, ENSI de Bourges (co-encadrant de la thèse) - Jean-Louis Lanet, Professeur des Universités, Université de Limoges (examinateur) Rapporteurs: - Samia Bouzefrane, Maître de conférences HDR, CNAM - Nathalie Drach-Temam, Professeur des Universités, UPMC Paris 6


On Granularity in Data-Parallel Programs Development Virginia Niculescu, Babes-Bolyai University of Cluj-Napoca
Parallel computation models with high level of abstraction, usually, do not have mechanisms for specifying and building granularity. If such mechanisms are introduced they could be very useful since they allow a better evaluation of the performance, and finally, an easier implementation. It is considered that a model of parallel computation, to be useful, must fulfill a set of requirements: abstractness, software development methodology, architecture independence, cost measures, no preferred scale of granularity, and efficiently implementable. The development of the programs correct by construction is also a very important issue in parallel setting. The normal flow in a derivation is to start from a specification, derive and express it using the chosen model, and then adjust it for implementation. The question that could arise is “When should we care about the granularity?” - only at the mapping phase, or starting from the beginning, in the derivation phase. Some case studies will be presented, and their analysis indicate that if we are able to specify and to build granularity from the first levels of design, then the chances to obtain good improvements of the resulted costs increase very much. One key to attaining good parallel performance is choosing the right granularity for the application.


Detecting Errors in Computational Grammars of Natural Language Claire Gardent, DR CNRS, LORIA Nancy
Computational Grammars of Natural Language typically contain several hundreds of rules labelled with complex feature structures thereby making it difficult to accurately predict their generative power. In this talk, I will explore two complementary ways of automatically detecting errors in such grammars. The first approach is a simple grammar traversal approach guided by a set of user defined constraints. It permits a systematic exploration of the grammar predictions. With this approach, we can ask general questions about the grammar (e.g., "can all rules in the grammar be used in at least one derivation?") and about its linguistic coverage (e.g., "Are all possible syntactic realisations of the verb and of its arguments generated and correct?"). The second approach applies a simple statistical analysis to the output produced by a sentence generator using the grammar under investigation. With this approach, we can identify the most likely sources of errors. Using the data provided by the Surface Realisation shared task, we show how this error mining approach permits rapidly improving the coverage of the grammar on this data.


Soutenance d'HDR : Contributions à la résolution de contraintes du premier ordre Khalil Djelloul, LIFO
La programmation par contraintes s’est largement développée au cours des dernières décennies avec la mise au point d’environnements de modélisation et de résolution permettant à un utilisateur de formaliser son problème et de bénéficier de solveurs efficaces. Toutefois, la majorité des travaux de cette communauté se sont concentrés sur les problèmes combinatoires, principalement de satisfaction de contraintes discrètes. Si l’élan initial de la programmation par contraintes trouvait sa source dans la programmation logique, la déclarativité de ce paradigme a été un peu délaissée. Pourtant, l’expressivité d’un langage logique du premier ordre permet d’exprimer de nombreux problèmes de manière naturelle et simple. De la même manière, l’utilisation de formules du premier ordre pour spécifier des contraintes, s’appuyant pleinement sur la quantification des variables et des connecteurs logiques, autorise des modélisations bien plus riches que les simples problèmes de satisfaction de contraintes. Bien évidemment, l’augmentation de l’expressivité se fait alors au détriment de la complexité de résolution.
Les travaux présentés constituent une étude fondamentale de la notion de résolution de contraintes du premier ordre et de sa relation intime avec la notion énigmatique de théorie complète. Différentes contributions, au croisement de l'intelligence artificielle et de la vérification formelle, ont été développées. On citera à titre d'exemple : la décomposabilité avancée, la résidualité, les contraintes duales, la modélisation déclarative par CHR, la complexité des RTS, la sémantique unifiée, la modularité et la parallélisation de la résolution.

Membres du jury :
- Mr François Fages, Directeur de recherche, INRIA Rocquencourt (rapporteur)
- Mr Frederic Saubion,Professeur des universités, Université d'Angers (rapporteur)
- Mr Lakhdar Sais, Professeur des universités, Université d'Artois (rapporteur)
- Mr Denys Duchier Professeur des universités, Université d'Orléans
- Mr Jean Michel Couvreur, Professeur des universités ,Université d'Orléans


Generate, Test, and Aggregate - A Calculation-based Framework for Systematic Parallel Programming with MapReduce Kento Emoto, The University of Tokyo
MapReduce, being inspired by the map and reduce primitives available in many functional languages, is the de facto standard for large scale data-intensive parallel programming. Although it has succeeded in popularizing the use of the two primitives for hiding the details of parallel computation, little effort has been made to emphasize the programming methodology behind, which has been intensively studied in the functional programming and program calculation fields. We show that MapReduce can be equipped with a programming theory in calculational form. By integrating the generate-and-test programing paradigm and semirings for aggregation of results, we propose a novel parallel programming framework for MapReduce. The framework consists of two important calculation theorems: the shortcut fusion theorem of semiring homomorphisms bridges the gap between specifications and efficient implementations, and the filter-embedding theorem helps to develop parallel programs in a systematic and incremental way. We give nontrivial examples that demonstrate how to apply our framework.


Model Checking régulier pour automate d'arbres à treillis Valérie Murat, IRISA
Le model checking régulier sur termes (TRMC) est une famille de techniques permettant d'analyser les systèmes à espace d'états infini dans lequel les états sont représentés par des termes, et les ensembles de termes par des automates d'arbres. Le problème principal du TRMC est de savoir si un ensemble d'états erreur est accessible ou non. Le calcul d'un automate d'arbres représentant (une sur-approximation de) l'ensemble des états accessibles est un problème indécidable. Mais des solutions efficaces basées sur la complétion ou l'itération de transducteurs d'arbres existent. Malheureusement, les techniques actuelles liées au TRMC ne permettent pas de capturer efficacement à la fois la structure complexe d'un système et certaines de ces caractéristiques. Si on prend par exemple les programmes Java, la structure d'un terme est principalement exploitée pour modéliser la structure d'un état du système. En contrepartie, les entiers présents dans le programmes Java doivent être encodés par des entiers de Peano, donc chaque opération algébrique est potentiellement modélisée par une centaine d'applications de règles de réécriture. Nous proposons ici des automates d'arbres à treillis (LTAs), une version étendue des automates d'arbres dont les feuilles sont équipés avec des éléments d'un treillis. Les LTAs nous permettent de représenter des ensembles possiblement infinis de termes pouvant être interprétés. Ces termes "interprétables" permettent de représenter efficacement des domaines complexes et leurs opérations associées. Enfin, en tant que contribution principale, nous définissons un nouvel algorithme de complétion permettant de calculer l'ensemble possiblement infini des termes interprétables accessibles en un temps fini.


Automatic Refinement of Service Compositions Umberto Costa, Universidade Federal do Rio Grande do Norte
We propose a method for the automatic composition of processing units (i.e., web services or components). Our method uses query rewriting techniques to translate high-level specifications into lower-level ones. We consider both functional and non-functional requirements. We extend and adapt the MiniCon query rewriting algorithm to obtain a specification refinement algorithm which takes into account the existence of an ontology alignment, optional parameters and conversion functions. Experiments indicate that our method produces feasible compositions.


Asymptotic Modularity of some Graph Classes, ISAAC '11 (Algotel '12) Mauricio Soto, LIFO
Modularity has been introduced as a quality measure for graph partitioning. It has received considerable attention in several disciplines, especially complex systems. In order to better understand this measure from a graph theoretical point of view, we study the modularity of a variety of graph classes. We first consider simple graph classes such as tori and hypercubes. We show that these regular graph families have asymptotic modularity 1 (that is the maximum possible). We extend this result to the general class of unit ball graphs of bounded growth metrics. Our most striking result concerns trees with bounded degree which also appear to have asymptotic modularity 1. This last result can be extended to graphs with constant average degree and to some power-law graphs. (Joint work with F. de Mongolfier, L. Viennot)


Mimicking Nature via Self-Assembly Matthew J. Patitz, University of Arkansas
Algorithmic self-assembly has found increasing interest in both experimental and theoretical research as a tool for designing physical systems at the nanoscale. Laboratory-based experiments have made steady progress in the complexity and robustness of their outputs, and theoretical research has continued to explore the fundamental limitations of systems and models. In this talk I will introduce a basic theoretical model for artificial self-assembling systems composed of DNA ``tiles'' known as the abstract Tile Assembly Model, or aTAM, (introduced by Erik Winfree in 1998). I will then exhibit examples of the theoretical power of the aTAM. Next, I will introduce and briefly discuss a series of models derived from the aTAM and inspired by natural self-assembling systems. I will briefly discuss the relative power of these systems and potential future directions of research.


An operating system for safe execution of hard real-time and non real-time tasks Matthieu Lemerre, CEA, LIST, Embedded Real Time Systems Laboratory, Gif-sur-Yvette, France
This talk describes the principles to build an operating system for safe execution of hard real-time and non real-time tasks on a single computer. Achieving this goal requires not only to follow the traditional behavioral security principles, but also new resource security principles throughout the system. Even if these principles put heavy constraints on the system, they make allocation predictable, immune from denial of service attacks, and allows ensuring a task will have enough resource to complete its execution. We prove that building resource-secure systems is possible by describing the design and implementation of our prototype, Anaxagoros. The main issue for implementing the system is synchronization, and we propose several novel ways to solve synchronization problems.


On minimum $(K_q;k)$-stable graphs Andrzej Zak , AGH University of Science and Technology
Given a graph $H$ and a non-negative integer $k$, a graph $G$ is called $(H;k)$-stable if $G-S$ contains a copy of $H$ for every set $S\subset V(G)$ with $|S|\leq k$. We are interested in $(H;k)$-stable graphs with minimum number of edges, called minimum $(H;k)$-stable graphs. In the talk, for every $q\geq 2$, we will characterize minimum $(K_q;k)$-stable graphs provided that $k$ is sufficiently large.


Codes identifiants dans les graphes adjoints Aline Parreau, Institut Fourier, Université Joseph Fourier de Grenoble
Les codes identifiants ont été introduits en 1998 pour modéliser la détection d'erreurs dans des réseaux de processeurs. Un code identifiant d'un graphe est un sous-ensemble dominant de sommets tel que tout sommet du graphe ait une intersection unique avec le code. Dans cet exposé, nous nous intéresserons aux codes identifiants dans la classe particulière des graphes adjoints (line graphs), ce qui correspond à identifier les arêtes d'un graphe avec ses arêtes. Nousdonnons des bornes sur la taille minimale d'un code identifiant dans les graphes adjoints et montrons que le problème des codes identifiants reste NP-complet restreint à cette classe. Ces résultats ont été obtenus en collaboration avec Florent Foucaud,Sylvain Gravier, Reza Naserasr et Petru Valicov.


Similarité et fouille de données Maria Rifqi, LIP 6
La notion de similarité a été très tôt perçue comme un concept clé en intelligence artificielle. Elle intervient ainsi dans de nombreux domaines de l'intelligence artificielle comme l'apprentissage automatique, la recherche d'information, le raisonnement. Elle est aussi étudiée dans de nombreux domaines liées à l'intelligence artificielle comme l'analyse de données, les sciences cognitives ou la psychométrie. En pratique, la similarité est évaluée, le plus souvent, par une mesure de similarité ou une distance (l'ordre donné est alors inversé). La multitude de mesures de similarité existantes dans la littérature est à mettre en rapport avec la multitude de méthodes et de domaines où une mesure de similarité intervient. Ce constat nous motive pour proposer des moyens de comparer des mesures de similarité afin de mieux appréhender leur comportement et de mieux choisir une mesure de similarité. Dans la première partie de l'exposé, des critères de comparaison de mesures de similarité seront définis permettant de distinguer les mesures d'une part de manière cardinale, par leur pouvoir de discrimination, et de manière ordinale d'autre part, par l'ordre qu'elles génèrent, quantifié par un degré d'équivalence que nous avons introduit. Dans la seconde partie de l'exposé, les principes mis en évidence par la comparaison des mesures de similarité seront mis en oeuvre en fouille de données. Ces principes nous ont conduit à formuler une nouvelle méthode d'extraction automatique de règles graduelles du type "plus X est A, plus Y est B".


A venir Jean-Charles Lamirel, Université de Strasbourg


Aspects fondamentaux et applications du problème SAT Gilles Dequen, Université de Picardie
Le traitement efficace des problèmes de nature combinatoire difficiles reste un enjeu de la recherche en informatique. Pour ces problèmes de la classe NP et plus spécifiquement pour le problème SAT (le "père" des problèmes NP-Complets), de nombreuses solutions, complètes ou non, ont été proposées durant cette dernière décennie. A ce jour, bon nombre des enjeux fondamentaux relatifs à SAT tournent autour des modèles de génération aléatoire pour lesquels certains aspects sont similaires à des phénomènes étudiés en physique statistique. Par ailleurs, la puissance expressive de la logique propositionnelle permet à cette thématique de rendre accessible la résolution de formule de taille industrielle offrant ainsi une alternative intéressante aux solutions usuelles pour des problèmes de différentes natures tels que, la vision, la cryptographie, la tomographie, le model-checking, la validation de circuits et de connaissances, etc … Cet exposé présentera certaines contributions autour de ces deux volets.


Déduction automatique appliquée à l'analyse et la vérification de systèmes infinis Laurent Vigneron, Université de Lorraine - LORIA
Cet exposé présente différents travaux sur le thème de la déduction automatique, théoriques et appliqués. A partir de la conception de méthodes de déduction et de stratégies modulo des théories équationnelles, l'accent est tout d'abord mis sur une tâche très coûteuse : la réécriture. Une procédure de normalisation efficace est présentée, construisant un système de réécriture clos convergent à partir d'un ensemble initial d'équations closes. L'intérêt des méthodes de déduction est également mis en valeur par l'étude d'algèbres approximantes modélisant des "rough sets" utilisés en data mining. Les déductions sont utilisées pour engendrer des propriétés de ces algèbres, comparer ces algèbres, et démontrer des résultats importants. Enfin, la déduction automatique est appliquée à l'analyse de protocoles de sécurité, via la formalisation de spécifications de protocoles et des stratégies d'un intrus. Des techniques d'analyse sont également définies pour des classes particulières de protocoles, comme les protocoles de non répudiation ou de groupes. L'implantation de ces résultats dans divers outils, dont AVISPA, illustre leur originalité, leur efficacité et leur succès.


CAPE: Checkpointing Aided Parallel Execution Eric Renault, Institut Télécom / Télécom SudParis
Les directives de compilation OpenMP permettent de specifier les parties d'un programme pouvant s'executer en parallele sur une machine a memoire partagee. Cet expose presente comment il est possible d'utiliser les techniques de point de reprise pour produire un programme s'executant sur une machine a memoire distribuee a partir de ces memes directives OpenMP.La presentation s'achevera sur une presentation des premieres performances obtenues avec notre prototype en cours en developpement.


Direct Parsing of Discontinuous Constituents Wolfgang Maier, Université Heinrich Heine de Düsseldorf
Discontinuities are a frequent phenomenon, not only in free word order languages. Treebanks therefore usually contain an annotation mechanism which accounts for them. Nevertheless, a large part of the work on data-driven constituency parsing in the literature is based on Probabilistic Context-Free Grammar (PCFG) and discards this mechanism since CFG cannot model discontinuities directly. Linear Context-Free Rewriting Systems (LCFRS), an extension of CFG, can describe discontinuous constituents in a straightforward way and is therefore a natural candidate for the direct data-driven parsing of such structures. In this talk, I present the first efficient implementation of a weighted deductive CYK parser for Probabilistic LCFRS. The parser uses different context-summary estimates of parse items, some of them allowing for A* parsing. I present experimental results on the German NeGra treebank which show that data-driven LCFRS parsing is feasible and yields output of competitive quality.


Langages géométriques et polycubes Hadrien Jeanne, Université de Rouen
Les langages géométriques ont été introduits pour répondre à des problématiques de validation temporelle d'applications temps-réel. Classiquement, cette validation peut se faire selon deux modèles, un basé sur les langages rationnels, et un sur la géométrie discrète. Les langages géométriques se présentent comme un lien entre ces deux modèles. Cela a motivé la recherche d'un algorithme de caractérisation efficace. Les langages géométriques finis sont également modélisés par des polycubes dirigés (une dimension par lettre). Grâce à l'extension des propriétés usuelles des polyominos, nous avons pu déterminer différentes sous-classes de polycubes. Nous avons également pu définir une méthode d'énumération des polycubes dirigés, basée sur la décomposition par strates de Temperley, dont nous nous servons afin d'énumérer les classes de polycubes concernées.


Méthodes pour l'estimation du temps de calcul d'un algorithme de branchement : de l'analyse standard à Nicolas Bourgeois, ESSEC Business School
La recherche d'algorithmes en temps modérément exponentiel (plus rapides qu'une approche en force brute) pour les problèmes NP-difficiles est un champ très actif en algorithmique et théorie des graphes depuis une vingtaine d'années. Parmi eux, les algorithmes de branchements (récursifs) sont les plus répandus. L'analyse au pire des cas de la complexité de ces algorithmes a subi une importante évolution avec la définition en 2005 de mesures non-standards (paradigme "Measure & Conquer"). Aujourd'hui nous proposons une nouvelle approche qui permet d'améliorer de façon systématique la borne sur le temps de calcul de ces algorithmes.


Algorithmes paramétrés pour le consensus d'arbres phylogénétiques Sylvain Guillemot, Iowa State University, Ames, USA
Dans cet exposé, on considère divers problèmes de consensus entre arbres étiquetés aux feuilles. Etant donnée une collection d'arbres étiquetés T1,...,Tk, le problème du superarbre d'accord consiste à rechercher un arbre étiqueté T qui contienne chaque Ti comme sous-arbre. On décrira dans un premier temps des algorithmes polynomiaux résolvant le problème du superarbre d'accord dans le cas d'arbres enracinés. On étudiera ensuite deux relaxations du problème qui permettent de prendre en compte les désaccords entre arbres sources. La première relaxation, appelée Maximum Rooted Triplet Consistency, s'applique au cas où les arbres sources sont des triplets enracinés, c'est-à-dire des arbres enracinés à trois feuilles. Elle consiste à rechercher un plus grand sous-ensemble des triplets qui admette un superarbre d'accord. La seconde relaxation, appelée Maximum Agreement Supertree, s'applique au cas d'arbres sources quelconques. Elle consiste à rechercher un plus grand sous-ensemble des étiquettes pour lesquelles on peut construire un superarbre d'accord. Bien que ces deux relaxations soient NP-difficiles, on verra qu'elles admettent des algorithmes paramétrés efficaces, dûs à [Guillemot, Mnich, 2010] et [Fernandez-Baca, Guillemot, Shutters, Vakati 2012].


Lattice polynomial functions and their use in qualitative decision making Miguel Couceiro, Université Paris Dauphine
Aggregation refers to processes of merging or fusing several values, scores, etc., into a single meaningful one. Such processes are achieved by so-called aggregation functions, whose importance has become more and more apparent in an increasing number of areas not only of mathematics or physics, but especially of applied fields such as engineering, computer science, economics and social sciences. In particular, aggregation functions have attracted much attention in decision sciences since they provide an elegant and powerful formalism to model preference. These facts explain the rapid growth of aggregation theory which proposes, analyzes, and characterizes aggregation function classes. Traditionally, aggregation functions are regarded as mappings A: In → I, where I is a real inter- val (e.g., I = [0,1]), which are nondecreasing and satisfy the boundary conditions A(∧ In) = ∧ I and A(∨ In) = ∨ I. Typical examples include arithmetic and geometric means, and so-called Choquet inte- grals. Such examples of aggregation functions, despite producing values which are rather representative of their arguments, rely heavily on the rich arithmetic structure of the real numbers. Thus they are of little use over domains where no structure other than an order is assumed, e.g., qualitative scales such as {very bad, bad, satisfactory, good, very good}. In such situations, the most widely used aggre- gation functions are the so-called Sugeno integrals, which can be thought of as certain lattice polynomial functions, namely, those which are idempotent. This observation will be the starting point of our talk, in which we shall present a study of these lattice functions rooted in aggregation theory and motivated by their application in qualitative decision making. We shall start by presenting characterizations of lattice polynomial functions in terms of necessary and sufficient conditions which have natural interpretations in aggregation theory. Then we shall consider certain extensions of lattice polynomial functions which play an important role in decision making, in particular, in preference modeling, and present their characterizations accordingly. As we shall see, these results pave the way towards an axiomatic treatment of qualitative decision making. Some of the results we will discuss were obtained in collaboration with D. Dubois, J.-L. Marichal, H. Prade, and T. Waldhauser.


Counting independent sets in claw-free graphs Konstanty Szaniawski, Warsaw University of Technology, Faculty of Mathematics and Information Science
We will present an algorithm for counting independent sets in claw-free graphs. We start with a new description of the structure of claw-free graphs with maximum degree at most $4$. We define a family of some $14$ subgraphs and show that the set of edges of every claw-free graph with maximum degree at most $4$ can be decomposed into subsets inducing subgraphs isomorphic to graphs from this family. This decomposition is essential in the construction of our algorithm for counting independent sets. In the time complexity analysis of the algorithm we assign weights to subgraphs from the family of $14$ subgraphs mentioned above. As far as we know, this is the first use of the ,,measure and conquer'' method with the weigths asigned to subgraphs which are not vertices or edges. This approach allows us to estimate the time complexity of the algorithm by $O^*(1.1439^n) $ for claw-free graphs with maximum degree at most $4$. For claw-free graphs of arbitrary maximum degree the algorithm runs in time $ O^*(1.2152^n)$. The fastest currently known algorithm for counting independent sets in arbitrary graphs in polynomial space is the algorithm of Wahlstr\"om, which has the time complexity $O^*(1.2377^n) $. Using our algorithm as a procedure in the algorithm of Bj\"orklund, Husfeldt and Koivisto for finding a proper coloring of vertices of a graph, we obtain an algorithm for finding a proper coloring of vertices of a claw-free graph in polynomial space with the time complexity $O^*(2.2152^n)$.


Complexité paramétrée, algorithmes de noyau et Conflict Packing Anthony Perez, LIFO
La complexité paramétrée permet de mesurer la difficulté d'un problème de décision en fonction de la taille de l'instance et d'un paramètre k associé au problème. Un problème paramétré est dit FPT lorsqu'il peut être résolu en temps f(k).poly(n), où f() est une fonction calculable quelconque. De manière équivalente, un problème P est FPT lorsqu'il admet un algorithme de noyau, i.e. un algorithme polynomial qui, étant donnée une instance (I,k) de P, retourne une instance équivalente (I',k') de P telle que |I'| <= g(k) et k' <= k. Dans cet exposé, je présenterai un algorithme paramétré (simple) ainsi que différents algorithmes de noyau pour le problème Vertex Cover. Par la suite, je présenterai la notion de Conflict Packing, introduite avec Christophe Paul et Stéphan Thomassé et permettant d'obtenir des algorithmes de noyau polynomial pour de nombreux problèmes de modification de structures. Je décrirai en particulier comment cette méthode peut être appliquée au problème Feedback Arc Set in Tournaments pour obtenir un noyau contenant au plus 4k sommets. Pour conclure, j'expliquerai comment les idées présentées pour FAST peuvent s'appliquer à d'autres problèmes.


Modèles de calcul non initialisés Emmanuel Jeandel, LIF/LIRMM
Dans cet exposé, on considère les modèles de calcul usuels (machines de Turing, machines à compteurs) comme des systèmes dynamiques, correspondant à l'application de leur fonction de transition sur une configuration quelconque. En particulier, dans ce contexte, il est nécessaire d'observer leur comportement partant de n'importe quelle configuration, plutôt que d'une configuration initiale donnée. Le problème devient alors totalement différent. Par exemple, la preuve de l'indécidabilité de l'existence d'une configuration sur laquelle une machine de Turing ne s'arrête pas (Hooper, 1966) est bien plus délicate que l'indécidabilité de l'arrêt d'une machine de Turing partant d'une configuration donnée (Turing, 1937), et ce phénomène se répète pour la majorité des modèles de calcul. Après une présentation générale de la problématique, nous essaierons dans cet exposé d'illustrer les méthodes permettant de résoudre ou contourner le problème dans le cadre du modèle de calcul des pavages par tuiles de Wang, qui convient fort bien à un traitement dynamique.


Analysis of Microarray Gene Expression Data using Machine Learning Techniques Marcilio de Sauto, Universidade Federal de Pernambuco, Recife, Brazil
my research topics have included computability/learnability of artificial neural networks, cluster analysis, multi-classifier systems, hybrid intelligent systems, and bioinformatics. Recently, I have focused my work mainly on the analysis/development of machine learning techniques for bioinformatics problems, particularly in the context of cancer gene expression microarray data. Currently, cancer diagnosis at a molecular level has been made possible through the analysis of gene expression data. More specifically, one usually uses machine learning techniques to build, from cancer gene expression data, automatic diagnosis models (classifiers) or cluster them in order to find more refined subclasses of a given type of tumor. Cancer gene expression data often present some characteristics that make it complex to deal with. Some of these properties are data sparsity and an imbalanced class distribution. In this talk, I will go through the different approaches that my co-workers and I have been applying to these data: cluster ensemble and multi-objective optimization, meta-learning, and investigation of a set of indices aiming to extract the intrinsic complexity information from the data.


Maximum Metric Spanning Tree made Byzantine Tolerant Swan Dubois, LIP6 - UPMC Sorbonne Universités
Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. This paper focuses on systems that are both self-stabilizing and Byzantine tolerant. We consider the well known problem of constructing a maximum metric tree in this context. Combining these two properties is known to induce many impossibility results. In this paper, we first provide two new impossibility results about the construction of a maximum metric tree in presence of transient and (permanent) Byzantine faults. Then, we propose a new self-stabilizing protocol that provides optimal containment to an arbitrary number of Byzantine faults.


Extraire et exploiter les descripteurs linguistiques en fouille de textes Mathieu Roche, LIRMM, Montpellier
Les masses de données textuelles aujourd'hui disponibles engendrent un problème difficile lié à leur traitement automatique. Dans ce cadre, des méthodes de Fouille de Textes (FT) et de Traitement Automatique du Langage (TAL) peuvent, en partie, répondre à une telle problématique. Elles consistent à modéliser puis mettre en œuvre des méthodologies appliquées aux données textuelles afin d'en déterminer le sens et/ou découvrir des connaissances nouvelles. Dans ce processus, le descripteur linguistique constitue un élément pivot. Après une présentation des méthodes de traitement des descripteurs en eux-mêmes, ces derniers seront étudiés en contexte, c'est-à-dire en corpus. L'identification des descripteurs est souvent difficile à partir de corpus bruités et à faible contenu textuel sur lesquels nous concentrons nos efforts (par exemple, corpus issus du Web 2.0 ou du traitement OCR). Outre les mots considérés comme des descripteurs linguistiques pertinents en FT, nous nous sommes également intéressés à l'étude des syntagmes complexes à partir de corpus classiques puis d'une terminologie classique à partir de corpus complexes (par exemple, données logs ou corpus en français médiéval). Dans la suite, les syntagmes étudiés ne se situent plus à proprement parler dans les textes mais ils seront induits à partir des mots issus des corpus. Les méthodes proposées permettent de mettre en relief des syntagmes originaux tout à fait utiles pour l'identification d'Entités Nommées, le titrage automatique ou la construction de classes conceptuelles. Contrairement au raisonnement déductif, le raisonnement inductif est dit hypothétique. Dans ce cadre, l'utilisation de méthodes de validation automatique des relations induites par le biais d'approches de Fouille du Web se révèle déterminante. Les perspectives à ce travail se concentreront sur l'extraction de nouveaux descripteurs. Ces derniers seront associés à de nouvelles représentations sous forme d'entrepôts de données textuelles. Enfin, les travaux que nous souhaitons développer se focaliseront sur l’analyse des textes dans un contexte plus vaste lié au multimédia que le paradigme du Web 2.0 a mis en exergue ces dernières années.


The SANTE Method: Value Analysis, Program Slicing and Test Generation for C Program Debugging Nikolai KOSMATOV, Software Safety Laboratory, CEA LIST
This talk presents a prototype tool called SANTE (Static ANalysis and TEsting) implementing an original method combining value analysis, program slicing and structural test generation for verification of C programs. First, value analysis is called to generate alarms when it can not guarantee the absence of errors. Then the program is reduced by program slicing. Alarm-guided test generation is then used to analyze the simplified program(s) in order to confirm or reject alarms. Our experiments show that our method with program slicing outperforms previous combinations of static and dynamic analysis. Moreover, simplifying the program makes it easier to analyze detected errors and remaining alarms.


Réseaux de Manhattan dans le plan normé et réseaux de Manhattan orientés. Nicolas Catusse, LIF
Pour un ensemble de terminaux T dans le plan, un réseau de Manhattan est un réseau dans lequel il existe un plus court chemin rectilinéaire entre chaque paires de terminaux. Un réseau de Manhattan minimal est un réseau de Manhattan de longueur minimale. Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés dont la boule unitaire est un polygone convexe central symétrique. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.


Coloration des graphes de disques d'unité Henning Bruhn , Univ. Paris 6
Les graphes de disques d'unité constituent le modèle le plus simple pour un système des émetteurs sans-fils. Dans ce contexte, le problème d'allocation des fréquences se traduit au problème de colorier le graphe sous-jacent. Dans l'exposé je parlerai de la coloration des graphes de disques d'unité d'un point de vue structurel.


A clustering algorithm for multiple relational data matrices Francisco de A. T. de Carvalho, université Fédérale du Pernanbuc, Brésil
We present a clustering algorithm that is able to partition objects taking into account simultaneously their relational descriptions given by multiple dissimilarity matrices. These matrices have been generated using different sets of variables and dissimilarity functions. These methods are designed to provide a partition and a prototype for each cluster as well as to learn a relevance weight for each dissimilarity matrix by optimizing an adequacy criterion that measures the fitting between the clusters and their prototypes. These relevance weights change at each iteration and are different from one cluster to another. Experiments with real-valued datasets from UCI machine learning repository as well as symbolic data sets show the usefulness of the proposed clustering algorithm.