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

Lifo > Les séminaires du LIFO

 English Version



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 70 11
Fax: +33 (0)2 38 41 71 37



Les séminaires du LIFO


Accès par année : 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017

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).


10/04/2017 : à venir
Pierre Gançarski (ICube, Strasbourg) Résumé

03/04/2017 : ???
??? (???) Résumé

27/03/2017 : Recherche sémantique et à base de graphe dans des collections documentaires. L'intertextualité dans l'accès aux documents juridiques.
Nada Mimouni (Université Paris Dauphine) Résumé

27/03/2017 : Caractérisation impérative des algorithmes séquentiels en temps quelconque, primitif récursif et polynomial
Yoann Marquer (LACL, Créteil) Résumé
Attention : Débute à 15 h 15.

21/03/2017 : Continuous models of computation: computability, complexity, universality
Amaury Pouly () Résumé

20/03/2017 : à venir
??? () Résumé
Attention : Débute à 15 h 15.

13/03/2017 : à venir
??? () Résumé

13/03/2017 : à venir
Nicolas Bacquey (Laboratoire d'Informatique Fondamentale de Lille) Résumé
Attention : Débute à 15 h 15.

06/03/2017 : Sequential Decision Making in Linear Bandit Setting
Marta Soare (Department of Information and Computer Science, Aalto University et Helsinki Institute for Informati) Résumé

06/03/2017 : Calculer l'entropie des pavages mélangeants
Benjamin Hellouin () Résumé
Attention : Débute à 15 h 15.

27/02/2017 : Calculer dans un automate cellulaire unidirectionnel réversible : vers l'indécidabilité de la périodicité?
Martin Delacourt (LIFO, Université d'Orléans) Résumé

27/02/2017 : From mining under constraints to mining with constraints
Ahmed Samet (Université de Rennes 1 (UR1)/LACODAM) Résumé
Attention : Débute à 15 h 15.

13/02/2017 : Small complexity classes for cellular automata, dealing with diamond and round neighborhoods
Anaël Grandjean (LIRMM, Montpellier) Résumé

06/02/2017 : Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems
Sergiu Ivanov (TIMC-IMAG, Grenoble) Résumé

16/01/2017 : On the coinductive nature of centralizers
Charles Grellois (Università di Bologna) Résumé


Résumés des séminaires


à venir Pierre Gançarski, ICube, Strasbourg

à venir


??? ???, ???

à venir


Recherche sémantique et à base de graphe dans des collections documentaires. L'intertextualité dans l'accès aux documents juridiques. Nada Mimouni, Université Paris Dauphine

La recherche d’information et le traitement automatique des langues considèrent généralement les documents comme des unités distinctes même si ces derniers peuvent être pris dans un réseau de liens hypertextuels. Ce modèle traditionnel ne prend cependant pas en compte la richesse du réseau de relations sémantiques qui structurent les collections documentaires. Cette limitation est critique dans le domaine juridique où – de manière plus évidente qu’ailleurs – l’intertextualité conditionne la production et l’interprétation des textes. Au moment où les efforts de standardisation et d’ouverture donnent accès aux données publiques, il est essentiel de penser la modélisation des collections juridiques pour offrir des fonctionnalités d’interrogation avancées. Dans cet exposé, nous présentons un modèle documentaire qui prend en compte non seulement les annotations sémantiques portées par les documents, leurs structures logiques et leurs différentes versions mais aussi la structure d’une collection composée de plusieurs types de documents reliés entre eux par différents types de liens intertextuels. Le développement de la recherche d’information sémantique dans ses usages professionnels suppose d’exploiter tout cet ensemble de propriétés documentaires. Dans le domaine juridique, notamment, il faut pouvoir retrouver les documents d’un type particulier (par ex. des décrets émis par telle juridiction) qui portent sur une notion spécifique juridique (ex. contrat) et qui précisent un texte de loi donné. Il faut aussi pouvoir retrouver l’ensemble des textes portant sur un sujet donné (ex. le bruit) en vigueur à une date précise et la manière dont ils ont été appliqués, c’est-à-dire la jurisprudence relative à ces textes. L’approche proposée repose sur les standards du web sémantique. Elle a l’originalité d’intégrer les différents propriétés documentaires dans un modèle unique qui permet de croiser les critères sémantiques, temporels et relationnels dans la recherche d’information.


Caractérisation impérative des algorithmes séquentiels en temps quelconque, primitif récursif et polynomial Yoann Marquer, LACL, Créteil

On pourrait penser que des langages de programmation usuels sont algorithmiquement complets, mais la thèse de Church nous renseigne uniquement sur le comportement entrées-sortie (la fonction) et non sur les étapes intermédiaires (l'algorithme). D'ailleurs, nous évoquerons le fait que la récursion primitive ne permet pas de calculer tous les algorithmes en temps primitif récursif, et qu'une machine de Turing à deux rubans n'est pas algorithmiquement équivalente à une machine à un ruban. Il nous faut donc un modèle plus fin pour formaliser les algorithmes séquentiels. Nous avons été convaincus par la présentation axiomatique de Yuri Gurevich, qui a prouvé qu'elle était équivalente à son modèle des Abstract State Machines. Le problème est que les ASMs ne sont pas un modèle de programmation usuel, et qu'il y est difficile de caractériser des sous-classes naturelles. Ainsi, nous avons formalisé les langages impératifs par un système de transition, et en utilisant une traduction entre modèles et la notion de graphe de flot de contrôle, nous avons montré que : 1) Le langage While de Jones est algorithmiquement complet. 2) Pour des structures de données primitives récursives, une variante LoopC du langage Loop de Meyer et Ritchie est complète pour les algorithmes en temps primitif récursif. 3) Une restriction syntaxique PLoopC de LoopC est algorithmiquement 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.


Continuous models of computation: computability, complexity, universality Amaury Pouly,

In 1941, Claude Shannon introduced a continuous-time analog model of computation, namely the General Purpose Analog Computer (GPAC). The GPAC is a physically feasible model in the sense that it can be implemented in practice through the use of analog electronics or mechanical devices. It can be proved that the functions computed by a GPAC are precisely the solutions of a special class of differential equations where the right-hand side is a polynomial. Analog computers have since been replaced by digital counterpart. Nevertheless, one can wonder how the GPAC could be compared to Turing machines. A few years ago, it was shown that Turing-based paradigms and the GPAC have the same computational power. However, this result did not shed any light on what happens at a computational complexity level. In other words, analog computers do not make a difference about what can be computed; but maybe they could compute faster than a digital computer. A fundamental difficulty of continuous-time model is to define a proper notion of complexity. Indeed, a troubling problem is that many models exhibit the so-called Zeno's phenomenon, also known as space-time contraction. In this talk, I will present results from my thesis that give several fundamental contributions to these questions. We show that the GPAC has the same computational power as the Turing machine, at the complexity level. We also provide as a side effect a purely analog, machine-independent characterization of P and Computable Analysis. If time allows, I will present some recent work on the universality of polynomial differential equations. We show that when we impose no restrictions at all on the system, it is possible to build a fixed equation that is universal in the sense it can approximate arbitrarily well any continuous curve over R, simply by changing the initial condition of the system.


à venir ???,

à venir


à venir ???,

à venir


à venir Nicolas Bacquey, Laboratoire d'Informatique Fondamentale de Lille

à venir


Sequential Decision Making in Linear Bandit Setting Marta Soare, Department of Information and Computer Science, Aalto University et Helsinki Institute for Informati

When making a decision in an unknown environment, a learning agent decides at every step whether to gather more information on the environment (explore), or to choose what seems to be the best action given the current information (exploit). The multi-armed bandit setting is a simple framework that captures this exploration-exploitation trade-off and offers efficient solutions for sequential decision making. In this talk, I will review a particular multi-armed bandit setting, where there is a global linear structure in the environment. I will then show how this structure can be exploited for finding the best action using a minimal number of steps and for deciding when to transfer samples to improve the performance in other similar environments.


Calculer l'entropie des pavages mélangeants Benjamin Hellouin,

L'entropie est un paramètre réel capturant une notion de complexité d'un système, avec de nombreuses applications en mathématiques et en informatique. La question de notre capacité à calculer (par un algorithme) la valeur de ce paramètre a été étudiée sur de nombreux systèmes. J'étudie ce problème dans le cas des pavages (ou sous-décalages), i.e. des colorations du plan (de l'espace) soumis à des contraintes. Quand les contraintes sont en nombre fini (pavage de type fini), l'entropie est calculable en dimension 1 par une méthode algébrique classique. Le cas de la dimension 2 s'est révélé beaucoup plus difficile, l'entropie de beaucoup d'exemples simples étant encore inconnue. En 2007, il a été prouvé que l'entropie en dimension 2 n'est pas calculable en général. Des travaux plus récents ont montré que l'entropie redevient calculable sous des hypothèses supplémentaires : des hypothèses de mélange, c'est-à-dire d'indépendance des motifs situés à une certaine distance. Cependant, nous ne savons pas encore la limite exacte entre les mondes calculable et incalculable. Dans cet exposé, je parlerai de nos travaux sur les pavages soumis à un nombre potentiellement infini de contraintes. Dans ce contexte, nous montrons l'existence d'un seuil de difficulté (correspondant à un taux de mélange limite) au-delà duquel l'entropie passe du calculable à l'incalculable - exactement le résultat conjecturé dans le cas de type fini. Ces travaux sont en collaboration avec Silvère Gangloff et Cristobal Rojas.


Calculer dans un automate cellulaire unidirectionnel réversible : vers l'indécidabilité de la périodicité? Martin Delacourt, LIFO, Université d'Orléans

On s'intéresse au parallèle entre 2 problèmes sur des modèles distincts d'automates. D'une part, les automates de Mealy (transducteurs lettre à lettre complets) qui produisent des semi-groupes engendrés par les transformations sur les mots infinis associées aux états. En 2013, Gillibert a montré que le problème de la finitude de ces semi-groupes était indécidable. En revanche la question est ouverte dans le cas où l'automate de Mealy produit un groupe. D'autre part, les automates cellulaires unidirectionnels pour lesquels 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 vers une preuve d'indécidabilité en montrant qu'il est possible de simuler du calcul Turing dans un automate cellulaire unidirectionnel réversible, rendant ainsi des problèmes de prédiction indécidables ainsi que la question de la périodicité partant d'une configuration donnée finie.


From mining under constraints to mining with constraints Ahmed Samet, Université de Rennes 1 (UR1)/LACODAM

The mining of frequent itemsets from uncertain databases has become a very hot topic within the data mining community over the last few years. Although the extraction process within binary databases constitutes a deterministic problem, the uncertain case is based on expectation. Recently, a new type of databases also referred as evidential database that handle the constraint of having both uncertain and imprecise data has emerged. In this talk, we present an applicative study case of evidential databases use within the chemistry field. Then, we shed light on a WEvAC approach for amphiphile molecule properties prediction. Furthermore, the most existing approaches of pattern mining, which are based on procedural programs (as we often use/develop), would require specific and long developments to support the addition of extra constraints. In view of this lack of flexibility, such systems are not suitable for experts to analyze their data. Recent researches on pattern mining have suggested to use declarative paradigms such as SAT, ASP or CP to provide more flexible tools for pattern mining. The ASP framework has been proven to be a good candidate for developing flexible pattern mining tools. It provides a simple and principled way for incorporating expert's constraints within programs.


Small complexity classes for cellular automata, dealing with diamond and round neighborhoods Anaël Grandjean, LIRMM, Montpellier

We are interested in 2-dimensional cellular automata and more precisely in the recognition of langages in small time. The time complexity we consider is called real-time and is rather classic for the study of cellular automata. It consists of the smallest amount of time needed to read the whole imput. It has been shown that this set of langages depend on the neighborhood of the automaton. For example the two most used neighborhoods (Moore and von Neumann ones) are different with respect to this complexity. Our study deals with more generic sets of neighborhoods, round and diamond neighborhoods. We prove that all diamond neighborhoods can recognize the same langages in real time and that the round neighborhoods can recognize stricly less than the diamond ones.


Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems Sergiu Ivanov , TIMC-IMAG, Grenoble

In this work, we consider leftist insertion-deletion systems (LIDS), in which all rules have contexts on the same (left) side, and may only insert or delete one symbol at a time. We start by introducing extended rules, in which the contexts may be specified as regular expressions, instead of fixed words. We prove that, in this case, computational completeness is achieved when additional control mechanisms are used (graph control with two states, matrix control with binary matrices and random-context control). We then show how rules with regular contexts can be simulated by conventional rules checking one-symbol (resp. two-symbol) left contexts for insertion and two-symbol (resp. one-symbol) left contexts for deletion. This simulation does not generally hold in the controlled case, however. Hence, we provide a construction simulating an arbitrary 2-tag system using extended rules and which can be rewritten in terms of conventional rules of types above. These constructions imply that the studied insertion-deletion systems are universal.


On the coinductive nature of centralizers Charles Grellois, Università di Bologna

The centralizer of a language L is defined as the largest solution C(L) to the language equation XL = LX. In other terms, any word u.v obtained as a concatenation of a word u of L and of a word v of C(L) should admit a factorization starting by a word of C(L) and ending with a word of L. We can understand this as a rewriting process on the words of C(L). Kunc designed in 2006 a regular language L in which this rewriting process is such that it simulates the transitions of a Minsky machine. However, he could deduce from this that C(L) is not recursively enumerable... We will sketch a variant of his proof using Turing machines, and introduce the key concept of coinduction, which solves the mystery of Kunc's result: centralizers' behaviour is dual to the one of machines.