• Accueil du LIFO
• Personnes (Annuaire)
• Equipes
• CA
• GAMoC
• PaMDA
• SDS
• Actions de Recherche
• Thèses en cours
• Séminaires et Evénements
• Séminaires
• Evénements au LIFO
• Evénements hors LIFO
• Publications et logiciels
• Publications
• Thèses et Habilitations
• Rapports de Recherche
• Logiciels
• Transfert de technologie

• Renseignements pratiques
• Organisation
• Accès
• Enseignement
• Département Informatique
• IUT Informatique
• ENSI de Bourges

Contact

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

Tel: +33 (0)2 38 41 70 11
Fax: +33 (0)2 38 41 71 37

Les séminaires du LIFO

27/06/2013 : Soutenance de thèse : Modèle géométrique de calcul : fractales et barrières de complexité
Maxime Senot (LIFO) Résumé
Attention : Lieu : Hamphithéâtre Herbrand

24/06/2013 : Deciding Kleene Algebra Terms (In)Equivalence in Coq
Simão Melo de Sousa () Résumé
Attention : Débute à 16 h. Lieu : Salle SR3, bâtiment 3IA

13/05/2013 : Weak Inclusion for Recursive XML Types
Joshua Amavi (LIFO) Résumé

25/03/2013 : Kernelization Using Structural Parameters in Sparse Graph Classes
Somnath Sikdar () Résumé

18/02/2013 : Comparaison de réseaux biologiques : graphe orienté vs graphe non-orienté
Hafedh Mohamed Babou (Université de Nantes) Résumé

11/02/2013 :
Petru Valicov (LRI) Résumé

04/02/2013 : ??
Muath Alrammal (LIFO) Résumé

Résumés des séminaires

Soutenance de thèse : Modèle géométrique de calcul : fractales et barrières de complexité Maxime Senot, LIFO
Descriptif : Les modèles géométriques de calcul permettent d'effectuer des calculs à l'aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d'illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d'abord à travers l'étude de fractales (et plus généralement de structures appelées accumulations) que les machines à signaux sont capables d'une utilisation massive et parallèle de l'espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base – les modules – munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l'application de cette méthode et l'utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appélée profondeur de collisions, qui est polynomiale, illustrant ainsi l'efficacité et le pouvoir de calcul parallèle des machines à signaux. Jury : Denys Duchier - Professeur des Universités, Université d'Orléans Jérôme Durand-Lose - Professeur des Universités, Université d'Orléans - Directeur de thèse Géraud Sénizergues - Professeur des Universités, Université de Bordeaux 1 Véronique Terrier - Maître de Conférence HDR, Université de Caen - Rapporteur Jean-Baptiste Yunès - Maître de Conférence HDR, Université de Paris 7 - Rapporteur

Deciding Kleene Algebra Terms (In)Equivalence in Coq Simão Melo de Sousa,
This talk presents a mechanically verified implementation of an algorithm for deciding the (in)equivalence of Kleene algebra terms. The algorithm decides the (in)equivalence of two given terms through an iterated process of testing the equivalence of their partial derivatives and does not require the construction of the corresponding automata. Recent theoretical and experimental research provide evidence that this method is, on average, more efficient than the classical methods based in automata. We present some performance tests, comparisons with similar approaches, and also introduce a generalization of the algorithm to decide the equivalence of terms of Kleene algebra with tests. The motivation for the presented work is that of using the developed libraries as trusted frameworks for carrying out certified program verification.

Weak Inclusion for Recursive XML Types Joshua Amavi, LIFO
In database area, an important problem is schema evolution, particularly when considering XML types. XML is also used for exchanging data on the web. In this setting, we want to compare XML types in a loose way. To do it, we address the more general problem of approximative comparison of unranked-tree languages defined by regular grammars. Considering that the unranked tree languages L(G) and L(G') are those defined by given possibly-recursive XML types G and G', in this seminar we propose a method to verify whether L(G) is ''approximatively'' included in L(G'). The approximation consists in weakening the father-children relationships. Experimental results are discussed, showing the efficiency of our method in many situations.

Kernelization Using Structural Parameters in Sparse Graph Classes Somnath Sikdar,
Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, there were meta-theorems for linear kernels on graphs of bounded genus, H-minor-free graphs, and H-topological-minor-free graphs. To the best of our knowledge, there are no known meta-theorems for kernels for any of the larger sparse graph classes: graphs of bounded expansion, locally bounded expansion, and nowhere dense graphs. In this paper we prove meta-theorems for these three graph classes. More specifically, we show that graph problems that have finite integer index (FII) have linear kernels on graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For graphs of locally bounded expansion, our result yields a quadratic kernel and for nowhere dense graphs, a polynomial kernel. While our parameter may seem rather strong, we show that a linear kernel result on graphs of bounded expansion with a weaker parameter will necessarily fail to include some of the problems included in our framework. Moreover, we only require problems to have FII on graphs of constant treedepth. This allows us to prove linear kernels for problems such as Longest Path/Cycle, Exact s,t-Path, Treewidth and Pathwidth which do not have FII in general graphs.

Comparaison de réseaux biologiques : graphe orienté vs graphe non-orienté Hafedh Mohamed Babou, Université de Nantes
La comparaison de réseaux biologiques est actuellement l'une des approches les plus prometteuses pour aider à la compréhension du fonctionnement des organismes vivants. Elle apparaît comme la suite attendue de la comparaison de séquences biologiques dont l'étude ne représente en réalité que l'aspect génomique des informations manipulées par les biologistes. Dans ce travail, nous proposons une approche innovante permettant de comparer deux réseaux biologiques modélisés respectivement par un graphe orienté D et un graphe non-orienté G, et dotés d'une fonction f établissant la correspondance entre les sommets des deux graphes. L'approche consiste à extraire automatiquement une structure dans D, biologiquement significative, dont les sommets induisent dans G, par f, une structure qui soit aussi biologiquement significative. Nous réalisons une étude algorithmique du problème issu de notre approche en commençant par sa version dans laquelle D est acyclique (DAG). Nous proposons des algorithmes polynomiaux pour certains cas, et nous montrons que d'autres cas sont algorithmiquement difficiles (NP-complets). Pour résoudre les instances difficiles, nous proposons une bonne heuristique et un algorithme exact basé sur la méthode branch-and-bound. Enfin, pour montrer l'efficacité de notre heuristique, nous l'appliquerons sur des données simulées et sur des données biologiques réelles. Mots clés : Réseaux hétérogènes, Biologie computationnelle, NP-difficulté, APX-difficulté, Complexité paramétrée, Heuristiques, Branch-and-Bound.

Petru Valicov , LRI

?? Muath Alrammal, LIFO
XML is a key standard for manipulating data on the Internet. However, querying large volume of XML data represents a bottleneck for several computationally intensive applications. Many modern applications require processing of massive streams of XML data, creating difficult technical challenges. Among these is the optimization of XPath query processing and accurate cost estimation for these queries. In this seminar, we present a novel performance prediction model which a priori estimates the cost of any Forward XPath structural in terms of space used and time spent. The model consists of (1) a lazy stream-querying algorithm LQ (2) a mathematical performance model (linear regression functions), and (3) a new selectivity estimation technique. Extensive experiments on both real and synthetic data sets show that our model achieves accuracy better than existing approaches. The resulting prototype supports the a priori design of efficient queries, as well as automatic query optimizations.