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 99 29
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 2018

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


26/11/2018 : soutenance de thèse : universalité et complexité des automates cellulaires coagulants
Diego Maldonado (LIFO) Résumé
Attention : Débute à 13 h 30. Lieu : Amphi H, bâtiment 3IA

05/11/2018 : Modern Complexity Results of Formal Languages
Henning Fernau (Université de Trèves, Allemagne) Résumé
Attention : Débute à 13 h 45.

04/06/2018 : Time Series Constrained Clustering, with Application to Remote Sensing
Thomas Lampert (ICUBE, Université de Strasbourg ) Résumé

10/04/2018 : Soutenance de thèse : Discrétisation automatique de machines à signaux en automates cellulaires.
Tom Besson (LIFO) Résumé
Attention : Débute à 15 h. Lieu : Amphithéâtre Herbrand, bâtiment 3IA

14/03/2018 : Soutenance d'habilitation à diriger des recherches
Thi-Bich-Hanh Dao (LIFO) Résumé
Attention : Débute à 10 h 30. Lieu : Amphithéâtre Herbrand, bâtiment 3IA

12/03/2018 : Self-monitoring approximation algorithms
Henning Fernau (Universität Trier - Allemagne) Résumé

29/01/2018 : Introduction to Multi-Armed Bandits
Marta Soare (LIFO (CA)) Résumé


Résumés des séminaires


soutenance de thèse : universalité et complexité des automates cellulaires coagulants Diego Maldonado, LIFO

Les automates cellulaires forment une famille bien connue de modèles dynamiques discrets, introduits par S. Ulam et J. von Neumann dans les années 40. Ils ont été étudiés avec succès sous différents points de vue : modélisation, dynamique, ou encore complexité algorithmique. Dans ce travail, nous adoptons ce dernier point de vue pour étudier la famille des automates cellulaires coagulants, ceux dont l'état d'une cellule ne peut évoluer qu'en suivant une relation d'ordre prédéfinie sur l'ensemble de ses états. Nous étudions la complexité algorithmique de ces automates cellulaires de deux points de vue : la capacité de certains automates coagulants à simuler tous les autres automates cellulaires coagulants, appelée universalité intrinsèque, et la complexité temporelle de prédiction de l'évolution d'une cellule à partir d'une configuration finie, appelée complexité de prédiction. Nous montrons que malgré les sévères restrictions apportées par l'ordre sur les états, les automates cellulaires coagulants peuvent toujours exhiber des comportements de grande complexité. D'une part, nous démontrons qu'en dimension deux et supérieure il existe un automate cellulaire coagulants intrinséquement universel pour les automates cellulaires coagulants en codant leurs états par des blocs de cellules ; cet automate cellulaire effectue au plus deux changements d'états par cellule. Ce résultat est miniaml en dimension deux et peut être amélioré en passant à au plus un changement en dimensions supérieures. D'autre part, noius étudions la complexité algorithmique du problème de prédiction pour la famille des automates cellulaires totalistiques à deux états et voisinage de von Neumann en dimension deux. Dans cette famille de 32 automates, nous exhibons deux automates de complexité maximale dans le cas d'une mise à jour synchrone des cellules et nous montrons que dans le cas asynchrone cette complexité n'est atteinte qu'à partir de la dimension trois. Pour presque tous les autres automates de cette famille, nous montrons que leur complexité de prédiction est plus faible (sous l'hypothèse P≠NP).


Modern Complexity Results of Formal Languages Henning Fernau, Université de Trèves, Allemagne

In this talk, several aspects of these complexity results are surveyed in some case studies. I. String-to-String Correction: Wagner showed a dichotomy result back in 1975 regarding the permitted set of operations. Only in two (kind of equivalent) situations, an NP-hardness result could be shown, all other cases are solvable in polynomial time. One of the pecularities of this result is that the NP-hardness proof depends on arbitrary large alphabets. Only quite recently, Meister could show that this is necessary, as there is a polynomial-time algorithm for each fixed alphabet. II. Grammar-based Compression: Again back in the 1970s, NP-hardness of the problem of producing a smallest grammar for the language $\{w\}$, given a word $w$, was shown. Also in this case, the proof blew up the size of the (terminal) alphabet. In this case however, NP-hardness also holds for fixed alphabet sizes (ICALP 2016), although binary alphabets are still open. III. Synchronizing Words: We use algorithmic problems derived from this famous combinatorial problem on DFAs in order to explore the space of parameterizations and also show one rather typical feature for exact algorithms on hard automata problems: The seemingly naive algorithms tend to be provably optimal. IV. Consistency for DFAs: Again, we display the wealth of possible parameterizations and explain lower bound results, also based on (S)ETH. V. Lower bounds for NFA Universality: This textbook problem can be solved in time $O^*(2^t)$ on NFAs with $t$ states, but not better under ETH. For the parameterization with alphabet size and a bound $\ell$ on the length of words of interest for the universality test, the length-bounded variation can be solved in time $O^*(|\Sigma|^\ell)$ but no better under SETH. VI. Parsing CFL and TAL: Here, we explain lower bounds under the $k$-Clique-Hypothesis, which offers one of the rare examples of using fine-grained complexity in Formal Languages.


Time Series Constrained Clustering, with Application to Remote Sensing Thomas Lampert, ICUBE, Université de Strasbourg

Constrained clustering is becoming an increasingly popular approach in data mining. It offers a balance between the complexity of producing a formal definition of thematic classes---required by supervised methods---and unsupervised approaches, which ignore expert knowledge and intuition. Nevertheless, the application of constrained clustering to time-series analysis is relatively unknown. In this seminar we will explore popular constrained clustering algorithms, discuss their modification to use with time-series, and explore which factors influence an algorithm's performance when constraints are introduced. We will then discuss their application to high-resolution image time-series, and how the introduction of constraints aids a user in exploring such data.


Soutenance de thèse : Discrétisation automatique de machines à signaux en automates cellulaires. Tom Besson, LIFO

Dans le contexte du calcul géométrique abstrait, les machines à signaux ont été développées comme le pendant continu des automates cellulaires capturant les notions de particules, de signaux et de collisions. Une question importante est la génération automatique d'un AC reproduisant la dynamique d'une machine à signaux donnée. D'une part, il existe des conversions ad hoc. D'autre part, ce n'est pas toujours possible car certaines machines à signaux présentent des comportements « continus ». Par conséquent, la discrétisation automatique de telles structures est souvent complexe et pas toujours possible. Cette thèse propose trois manières différentes de discrétiser automatiquement les machines à signaux en automates cellulaires, avec ou sans approximation possible. La première s'intéresse à une sous-catégorie de machines à signaux, qui présente des propriétés permettant d'assurer une discrétisation automatique exacte pour toute machine de ce type. La deuxième est utilisable sur toutes les machines mais ne peut assurer ni l'exactitude ni la correction du résultat. La troisième s'appuie sur une nouvelle expression de la dynamique d'une machine à signaux pour proposer une discrétisation. Cette expression porte le nom de modularité et est décrite avant d'être utilisée pour discrétiser.


Soutenance d'habilitation à diriger des recherches Thi-Bich-Hanh Dao, LIFO

La programmation par contraintes est un paradigme puissant pour résoudre des problèmes combinatoires. Je présente mes travaux sur l’application de la programmation par contraintes au traitement automatique des langues et à la fouille de données. En traitement automatique des langues, nous nous intéressons à l’analyse syntaxique des grammaires de propriétés, décrites par des propriétés que doivent satisfaire les énoncés grammaticaux. Nous définissons une sémantique formelle en théorie des modèles et formalisons l’analyse syntaxique comme un problème d’optimisation sous contraintes. Nous développons un modèle en programmation par contraintes, ce qui amène à un analyseur entièrement à base de contraintes. En fouille de données, nous considérons le problème de classification non supervisée (clustering) sous contraintes utilisateur, qui vise à partitionner les objets en groupes homogènes, étant donnés une mesure de dissimilarité entre objets et un ensemble de contraintes utilisateur à satisfaire. Nous développons un cadre déclaratif qui intègre plusieurs critères d’optimisation principaux de clustering et tous types de contraintes utilisateur populaires. Nous montrons que sa flexibilité permet de trouver la frontière de Pareto pour des problèmes de clustering bi-objectif sous contraintes. Nous améliorons davantage l’efficacité l’approche en développant des contraintes globales dédiées aux critères d’optimisation de clustering. Nous explorons plusieurs nouveaux problèmes de clustering avec des contraintes et montre que la programmation par contraintes constitue un cadre flexible et efficace pour les résoudre.


Self-monitoring approximation algorithms Henning Fernau, Universität Trier - Allemagne

Reduction rules are one of the key techniques for the design of parameterized algorithms. They can be seen as formalizing a certain kind of heuristic approach to solving hard combinatorial problems. We propose to use such a strategy in the area of approximation algorithms. One of the features that we may gain is a self-monitorin} property. This means that the algorithm that is run on a given instance I can predict an approximation factor of the solution produced on I that is often (according to experiments) far better than the theoretical estimate that is based on a worst-case analysis.


Introduction to Multi-Armed Bandits Marta Soare, LIFO (CA)

A multi-armed bandit model is a simple framework that captures the exploration-exploitation trade-off that a learning agent needs to solve when facing an unknown and uncertain environment: The learning agent gets to sequentially choose "arms" (options/actions) available in the environment and has to infer their associated values based on the "rewards" (observations) returned by the environment as a response to the agent's choice. Given an objective, typically that of maximizing the cumulative reward, the agent can decide to "exploit" the information acquired thus far about the environment (keep selecting the arm with the seemingly largest reward), or to "explore" the arms whose associated value is more uncertain. This is a dynamic research topic with a wide range of applications, including clinical trials for deciding on the best treatment to give to a patient, on-line advertisements and recommender systems, or game playing. In this introduction we will present one of the simplest version of this problem, that of a stochastic multi-armed bandit game, and we will review some algorithms for optimally solving the arm selection problem.