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


21/12/2017 : TBA
Jean-Christophe DENEUVILLE (LIFO (SDS/INSA)) Résumé
Attention : Débute à 13 h. Lieu :

18/12/2017 : Equilibrage de charge dans les systèmes distribués
Noël Gillet (LIFO - GAMoC) Résumé
Attention : Débute à 15 h.

07/12/2017 : TBA
Armen PETROSSIAN (LIFO (SDS/INSA)) Résumé
Attention : Débute à 13 h. Lieu :

04/12/2017 : Projets 2017/2018
Anais Halftermeyer (LIFO - CA) Résumé

23/11/2017 : Réécriture, automates, logiques temporelles, et autres outils pour la vérification
Vincent HUGOT (LIFO (SDS/INSA)) Résumé
Attention : Débute à 13 h. Lieu :

16/10/2017 : Similarités et distances entre trajectoires
Thomas Devogele (LI - Tours) Résumé
Attention : Le séminaire sera suivi du groupe de travail Pamda sur le thème BigData et Etude de similarités.

11/07/2017 : An experience on the integration of heterogeneous distributed computing infrastructures
Joaquin Ezpeleta (Université de Zaragose) Résumé

10/07/2017 : Use of Data Complexity Measures in the Support of Supervised Machine Learning
Ana Lorena (UNIFESP, São José dos Campos, Brésil) Résumé

03/07/2017 : Separation of concerns in distributed and parallel environments
Hélène Coullon (IMTA/Inria (équipe Ascola), Nantes) Résumé

29/05/2017 : Analyse syntaxique multilingue en constituants discontinus
Benoît Crabbé (LLF, Université Paris 7) Résumé

13/04/2017 : Protection de données externalisées et mutualisées.
Dalel Bouslimi () Résumé
Attention : ce séminaire aura lieu à Bourges / Débute à 13 h. Lieu : Salle Régalis

11/04/2017 : Game semantics approach to higher order complexity
Hugo Férée (University of Kent ) Résumé

10/04/2017 : Lien entre Satisfiabilité Propositionnelle et Fouille de Données
Jerry Lonlac (CNRS – LIMOS, Université Clermont Auvergne) Résumé
Attention : Débute à 15 h 15.

10/04/2017 : Clustering collaboratif multistratégie et multitemporel : application à la télédétection
Pierre Gançarski (ICube, Strasbourg) Résumé

05/04/2017 : Ouroboros : Un protocole d'échange de clés efficace et quantum-résistant
Jean-Christophe Deneuville () Résumé
Attention : ce séminaire aura lieu à Bourges / Débute à 13 h. Lieu : Salle Régalis

03/04/2017 : Inégalités d'information dans le partage de secret
Tarik Kaced () Résumé
Attention : Débute à 15 h 15.

03/04/2017 : A Knowledge Discovery Approach for Mining Predictive Biomarkers in Complex Metabolomic Data
Dhouha Grissa (INRIA/Nancy) Résumé

27/03/2017 : A Big Data Framework for Intelligent Job Offers Recommendation Using Time Series Forecasting, and Semantic Classification.


Sidahmed Benabderrahmane (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.

23/03/2017 : Une approche par composants pour la visualisation scientifique interactive.
Abderrahim Ait Wakrime () Résumé
Attention : ce séminaire aura lieu à Bourges / Débute à 13 h. Lieu : Salle Régalis

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

20/03/2017 : Mots infinis auto-mélangeants
Svetlana Puzynina () Résumé

20/03/2017 : Collaborative Clustering and its Applications
Jérémie Sublime (ISEP Paris) Résumé
Attention : Débute à 15 h 15.

20/03/2017 : Arithmétique efficace pour une cryptographie asymétrique appliquée
Julien Eynard () Résumé
Attention : ce séminaire aura lieu à Bourges / Débute à 18 h. Lieu : Salle Régalis

16/03/2017 : 1) Gestion sécurisée des WFMS dans des environnements inter-organisationnels 2) Déploiement dynamique des politiques de sécurité en se basant sur l'AOP dans des environnements "pervasifs"
Ayed Samiha () Résumé
Attention : ce séminaire aura lieu à Bourges / Débute à 13 h. Lieu : Salle Régalis

14/03/2017 : Structuration automatique de documents audio
Abdesselam Bouchekif (Université du Maine) Résumé

13/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é

13/03/2017 : Introduction au calcul uniforme : Élection de leader sur les automates cellulaires à entrée périodique
Nicolas Bacquey (Laboratoire d'Informatique Fondamentale de Lille) Résumé
Attention : Débute à 15 h 15.

13/03/2017 : Concurrent C programs verification assisted by code and specification transformation.
Allan Blanchard () Résumé
Attention : ce séminaire aura lieu à Bourges Lieu : Salle Régalis

09/03/2017 : Enhanced Middleware for Maintaining Privacy in IoT Services
Ahmed Elmisery () Résumé
Attention : ce séminaire aura lieu à Bourges / Débute à 13 h. Lieu : Salle A108

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é

02/02/2017 : Security by design à travers deux exemples : Corrélation des événements de supervision informatique et authentification biométrique
Mehdi Bentounsi () Résumé
Attention : ce séminaire aura lieu à Bourges / Débute à 13 h.

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


Résumés des séminaires


TBA Jean-Christophe DENEUVILLE, LIFO (SDS/INSA)

TBA


Equilibrage de charge dans les systèmes distribués Noël Gillet , LIFO - GAMoC

Dans cet exposé je présenterai le travail réalisé au cours de ma thèse au LaBRI à Bordeaux, sous la direction de Nicolas Hanusse (CNRS). Dans ce travail, nous nous intéressons au problème de l'allocation de requêtes dans un environnement distribué. Ce problème est particulièrement motivé par le contexte actuel des données massives, où des systèmes distribués (plateforme de cloud computing par exemple) reçoivent énormément de requêtes à traiter de la part de nombreux utilisateurs, différents et distants. Un des enjeu majeur ici est bien sur de minimiser le temps de traitement de ces requêtes. Pour cela, une bonne répartition de la charge des requêtes entre les différents noeuds du système est essentielle. Dans ces systèmes, les données (aussi appelées objets) sont répliquées en plusieurs copies (souvent 3) afin de garantir une meilleure tolérance aux pannes et une meilleure accessibilité. Cependant on peut également se servir de ces copies afin de répartir judicieusement les requêtes entre les différents noeuds qui stockent les copies d'objets concernés par les requêtes. Dans un premier temps, on suppose que toutes les objets sont répliqués 2 fois, que les communications sont asynchrones et que certains noeuds du système peuvent être en pannes. On présente un algorithme d'allocation qui permet de garantir une allocation quasi-optimal d'un ensemble de requêtes recues en batch. On montrera que ce problème se modélise en fait par un problème d'orientation de graphe en distribué. Dans un deuxième temps, on suppose que chaque objet $o_i$ est répliqué $r_i\ge 2$ fois. On suppose également que les requêtes peuvent être choisies par un adversaire. Ici nous étudions l'impact de la réplication sur l'équilibrage de charge. Nous proposons un algorithme distribué qui combine une variante de l'algorithme d'allocation évoqué précédemment avec un mécanisme de gestion de copies. Ce mécanisme consiste à adapter le nombre de copies de chaque objet en fonction de leur popularité. On montre que notre solution garantie une approximation logarithmique de l'idéal pour toute distribution de requêtes. Enfin nous présenterons quelques expériences réalisées sur la base de données distribuée Apache Cassandra. Ici les requêtes n'arrivent pas en batch mais en flux. En modifiant légèrement nos algorithmes pour les adapter à ce modèle, on obtient un gain important sur le temps de traitement des requêtes par rapport à Cassandra. Les gains sont encore plus marqués lorsque le système n'est pas trop saturé (ie. ne reçoit pas trop de requête par unité de temps).


TBA Armen PETROSSIAN, LIFO (SDS/INSA)


Projets 2017/2018 Anais Halftermeyer, LIFO - CA

Dans ce séminaire, je compte présenter l'ensemble des projets auxquels je participe actuellement. Tout d'abord je présenterai l'état d'avancement du work package du projet Région ODIL auquel le LIFO participe concernant la production de ressources de l'oral annotées en syntaxe et en sémantique. Ce projet se terminera à la fin de l'année prochaine et amorcera dès début 2018 le projet RAVIOLI qui rassemble les mêmes partenaires dans un cadre assez proche. Je présenterai ensuite deux autres projets qui sont en cours de démarrage actuellement. Le premier, PREDICT4ALL, est financé par la fondation Bennetot et s’intéresse à la prédiction et correction de mots pour le public "dys" tandis que le second, TALAD est un projet ANR s’intéressant à l'enrichissement mutuel que peuvent s'apporter l'analyse du discours et le TAL sur des problématiques d'actualité (notamment en mettant en relation l'étude de la coréférence et de l'évolution des nominations dans le discours publique).


Réécriture, automates, logiques temporelles, et autres outils pour la vérification Vincent HUGOT, LIFO (SDS/INSA)

e propose une introduction douce à quelques outils formels pour la vérification (automatique ou semi-automatique) de propriété de sûreté et de sécurité. Parmi les sujets généraux abordés: -- quelques mots sur le model-checking (classique, symbolique, régulier), et un coup d’œil prudent aux logiques temporelles (CTL, LTL, CTL*) classiquement utilisées pour spécifier les propriétés à vérifier. -- introduction aux systèmes de réécriture de termes (TRS), automates d'arbres (ascendants) -- l'analyse d'accessibilité (de TRS). Exemple d'application à l'analyse de protocoles. Une fois les bases posées, en fonction du temps et de l'état d'éveil de chacun, je pourrai également aborder des sujets de recherches en cours ou potentiels autour de ces outils: -- Utiliser TRS pour modéliser systèmes de déduction: possible automatisation de l'élimination de coupures. Collab avec Sabine. -- Améliorer la préservation de la régularité dans les algos de complétion d'automates d'arbres (i.e. de meilleurs algos pour calculer R*(L) ). Le but concret est de rendre les outils logiciels plus utiles, en particulier pour l'application précédente. Collab possible avec Thomas Genet et son doctorant, Timothée Haudebourg, IRISA, Rennes, et LMV (Pierre, Nirina, Yohan,....). Implication possible d'Armen. -- Analyse d'accessibilité guidée par formules temporelles. (Extension de mes travaux de thèse; collab possible LMV) -- Techniques à base d'automates (de mots) pour la sécurisation de réseaux voituriers. Collab Christian, Benjamin Venelle (Valeo).


Similarités et distances entre trajectoires Thomas Devogele, LI - Tours


An experience on the integration of heterogeneous distributed computing infrastructures Joaquin Ezpeleta, Université de Zaragose

The talk will present the experience in the integration of grid, cluster and cloud infrastructures for solving computing intensive problems, and a proposal of general infrastructure to facilate such integration.


Use of Data Complexity Measures in the Support of Supervised Machine Learning Ana Lorena, UNIFESP, São José dos Campos, Brésil

Some studies in Machine Learning are devoted to understand how quantitative mesures about the complexity of data sets used in data classification, such as the geometric overlap between classes, affects the performance achieved in their solution. Among the contributions of this approach is a better understanding of the domains of competence and limitations of the ML techniques. This talk will show different measures from the literature able to characterize the complexity of classification problems. Next, their use in the support of noise identification, feature subset selection, generation of artificial datasets and decomposition of multiclass classification problems will be discussed.


Separation of concerns in distributed and parallel environments Hélène Coullon, IMTA/Inria (équipe Ascola), Nantes

Distributed and parallel systems and applications are difficult domains for which many different challenges arise. Among them are development models, automatic deployment on parallel and distributed architectures, reconfiguration, maintainability and flexibility. One additional challenge of such systems and applications is that different actors are involved at many different levels, such as end-users, developers (each of them with its own specific domain), cloud providers or system administrators etc. Many research efforts are needed such that a good abstraction level is proposed to any actor of those systems, and such that each concern of each actor can contribute (by composition) to the overall targeted final objective. In this talk I will browse the work I've done during my PhD thesis, my postdoctoral research position and the work I am currently initiating as a permanent researcher. I will illustrate that separation of concerns and abstraction problems appear at many different levels of such systems, for many different domains and can be composed together.


Analyse syntaxique multilingue en constituants discontinus Benoît Crabbé, LLF, Université Paris 7

On présente un système de transition pour l’analyse syntaxique en constituants appelé SR-GAP. Il s’agit d’une extension des systèmes d’analyse par décalage réduction avec une transition supplémentaire appelée GAP. On va d’abord montrer que ce système de transitions produit des résultats à l’état de l’art sur l’allemand en utilisant un simple perceptron comme méthode de pondération et une méthode de recherche de solutions en faisceau. Dans un second temps on donne des résultats préliminaires pour l’anglais, le français et l’allemand en utilisant comme méthode de pondération un modèle à apprentissage profond et une méthode de recherche gloutonne.


Protection de données externalisées et mutualisées. Dalel Bouslimi,


Game semantics approach to higher order complexity Hugo Férée, University of Kent

Computations usually handle finite inputs and outputs like finite words out integers. In a large variety of models of computation, the computed functions (which we call "first-order functions") is provided with a notion of complexity, and these notions of complexity are often somehow equivalent. Similarly, complexity has been defined for second-order functions (i.e. functions taking first-order functions as argument) or for functions over some other uncountable sets like the real numbers. However, this is not the case for functions of order three and above as well as for "larger" sets. We propose here a definition of complexity for such functions based on game semantics, where a computation is seen as a dialogue between the machine and its argument. In particular, we obtain a class of polynomial-time computable higher-order functions which contains the usual corresponding classes of first and second-order functions, extends them to all finite orders and verifies some properties that can be expected from such a class.


Lien entre Satisfiabilité Propositionnelle et Fouille de Données Jerry Lonlac, CNRS – LIMOS, Université Clermont Auvergne

Dans cet exposé décomposé en deux parties, je présenterai mes travaux autour de la Satisfiabilité en logique propositionnelle et de la fouille de données, en faisant ressortir les liens pouvant exister entre-elles. Dans la première partie je commencerai par introduire brièvement le problème de la Satisfiabilité en logique propositionnelle qui est un problème fondamental en théorie de la complexité. Ensuite, je me pencherai sur quelques travaux effectués autour des mécanismes d'apprentissage de clauses qui constituent la base des démonstrateurs SAT modernes. Dans la deuxième partie, je me focaliserai tout d'abord sur le problème de fouille de motifs graduels (découverte de covariations fréquentes entre attributs numériques dans une base de données). Ensuite, je présenterai brièvement un travail réalisé dans ce cadre sur l'extraction d'un type particulier de motifs graduels : les motifs graduels extraits sous contrainte de la temporalité. Enfin, je montrerai à travers un encodage SAT du problème de fouille de motifs graduels, comment rechercher ces motifs graduels en utilisant la Satisfiabilité propositionnelle.


Clustering collaboratif multistratégie et multitemporel : application à la télédétection Pierre Gançarski, ICube, Strasbourg

L'analyse de données lorsque celles-ci sont générées en grand volume et arrivent de façon quasi-continue, se heurte au problème de la définition de données de référence à jour pouvant être utilisées à la fois pour l'apprentissage et pour la validation. De fait, les méthodes non supervisées apparaissent comme une voie intéressante pour analyser ces données. Néanmoins, face à l'hétérogénéité des données et à leurs aspects temporelles, les méthodes de classification non supervisée, montrent aussi des limites. Dans le cadre de nos travaux, nous nous intéressons entre autres à la définition de mesures de similarité temporelle efficaces, à la combinaisons/collaboration de méthodes de classification et à la prise en compte de la connaissance dans le processus de classification. Dans cet exposé, je présenterai rapidement le contexte général de nos recherches puis focaliserai sur un ou plusieurs de ces points. Les méthodes présentées sont génériques. Néanmoins, je m'appuierai principalement sur des exemples d'application dans le domaine de la télédétection et des données de l'environnement.


Ouroboros : Un protocole d'échange de clés efficace et quantum-résistant Jean-Christophe Deneuville,

La sécurité des communications repose aujourd'hui principalement sur des problèmes bien étudiés, tels que la factorisation ou le logarithme discret. Cependant, ces problèmes s'avèrent calculatoirement faciles en présence d'éventuels ordinateurs quantiques. La majorité des protocoles de communication sur internet requièrent un échange de clé (dite de session), et avec la menace quantique, il devient urgent de repenser la façon de négocier de telles clés. Nous proposons une approche quantum-safe d'échange de clés, à la fois efficace en théorie et en pratique. Après un rappel des alternatives post-quantiques existantes, je présenterai notre nouvelle approche d'échange de clés. Sémantiquement plus sûre, elle présente notamment l'avantage d'être plus efficace. La portabilité à des appareils plus restreints en termes ressources est en cours d'étude. Un interfaçage avec les protocoles HTTPS et TLS est envisageable, et je présenterais les enjeux relevant de ce défi.


Inégalités d'information dans le partage de secret Tarik Kaced,

Après une introduction au partage de secret, je présenterais quelques resultats sur le partage de secret non-parfait. Nous expliquerons la méthode des inégalités d'information pour obtenir des bornes sur la complexité des schémas de partage. Nous expliquerons des resultats sur la géométrie du cone d'entropie.


A Knowledge Discovery Approach for Mining Predictive Biomarkers in Complex Metabolomic Data Dhouha Grissa, INRIA/Nancy

The analysis of complex and large metabolomic data with small sample size deriving from analytical platforms is a challenge In this work, we are interested in mining such metabolomic data to identify predictive biomarkers of metabolic disease (such as type 2 diabetes). The problem of classification and prediction using metabolomic data is a topic of recent interest. In this context, knowledge discovery methods have recently started to emerge to develop new strategies to tackle this challenge for biomarker discovery. The datasets to analyze consist in a limited set of individuals and a large set of attributes or features, in which predictive markers of clinical outcomes should be identified. Therefore, our goal is to explore a new knowledge discovery approach suitable for the reduction of high-dimensional metabolomic data, and the discovery of the best potential predictive biomarkers of metabolic diseases. This approach is specific of a supervised classification problem, where we investigate the combination of appropriate feature selection, statistical, and machine learning methods to discover meaningful features. Each combination is called a Classification Process (CP). Our experiments show that a combination of numerical methods, e.g. SVM, Random Forests (RF), and ANOVA, with a symbolic method such as Formal Concept Analysis (FCA), can be successfully used as complementary to highlight and visualize the best set of features and their CP. Our results show that RF and ANOVA seem to be the best suited methods for feature selection and discovery of potential predictive biomarkers.


A Big Data Framework for Intelligent Job Offers Recommendation Using Time Series Forecasting, and Semantic Classification.

 Sidahmed Benabderrahmane, Université Paris Dauphine

During the last decade, the expansion of automatic e-recruitment systems has led to the multiplication of web channels (job boards) that are dedicated to job offers disseminations. In a strategic and economic context where cost control is fundamental, the identification of the relevant job board for a given new job offers has become necessary. The purpose of this work is to present the recent results that we have obtained on a new job board recommendation system that is a decision-making tool intended to guide recruiters while they are posting a job on the Internet. First, the job applicant's clickstreams history on various job boards are stored in a big learning database, and then represented as time series. Second, probabilistic models as well as deep neural networks are used to predict future values of the clicks on the job boards. Third, dimensionality reduction techniques are used to transform the clicks multivariate time series into temporal symbolic sequences. Ngrams are then used to predict future symbols for each sequence. In a parallel way, a semantic classification of job offers is performed through a textual analysis using a controlled vocabulary from the open data (Codes ROME), for enhancing the recommendation process. Finally, a list of top ranked job boards are kept by maximizing the clickstreams forecasting in both representations. The algorithms were tested on a real dataset, coming from a big job-posting database from an industrial partner, and the results seem very promising.





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.


Une approche par composants pour la visualisation scientifique interactive. Abderrahim Ait Wakrime,


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.


Mots infinis auto-mélangeants Svetlana Puzynina,

Un mot infini x est auto-mélangeant s’il admet les décompositions : $x=prod_{i=1}^infty U_iV_i=prod_{i=1}^infty U_i=prod_{i=1}^infty V_i$, avec U_i,V_i mots finis. Autrement dit, x est une produit de mélange de deux copies de x. Nous montrons que beaucoup de mots importants et bien connus sont auto-mélangeants : cela inclut le mot de Thue-Morse et tous les mots Sturmiens qui ne sont pas de Lyndon. Nous trouvons des conditions nécessaires pour l'auto-mélange en prouvons que certains mots (par exemple, la suite de pliage de papier et les mots de Lyndon) ne sont pas auto-mélangeants. Comme une conséquence de notre caractérisation des mots Sturmiens auto-mélangeants, nous déduisons une preuve courte du théorème de Yasutomi sur la classification des mots Sturmiens purement morphiques. De plus, nous apportons une réponse positive à la question de T. Harju sur des mots auto-mélangeants sans carré et nous étudions l'auto-mélange dans les sous-shifts.


Collaborative Clustering and its Applications Jérémie Sublime, ISEP Paris

Unsupervised frameworks involving several clustering algorithms working together to tackle diff cult data sets are a recent area of research with a large number of new clustering paradigms such as multi-view clustering, clustering of distributed data, multi-expert clustering or multi-scale clustering analysis. Most of these frameworks can be regrouped under the umbrella of collaborative clustering, the aim of which is to reveal the common underlying structures found by the different algorithms while analyzing the data. The fundamental concept of collaboration is that clustering algorithms operate locally but collaborate by exchanging information about the local structures found by each algorithm. While many difficulties remain, using a unified framework for collaborative clustering has several promising real applications such as remote sensing analysis and the multi-view analysis of complex data.


Arithmétique efficace pour une cryptographie asymétrique appliquée Julien Eynard,


1) Gestion sécurisée des WFMS dans des environnements inter-organisationnels 2) Déploiement dynamique des politiques de sécurité en se basant sur l'AOP dans des environnements "pervasifs" Ayed Samiha,


Structuration automatique de documents audio Abdesselam Bouchekif, Université du Maine

La structuration thématique est une branche du traitement automatique du langage naturel. Elle permet à l’utilisateur de prendre rapidement connaissance de l’ensemble des thèmes traités dans un document contenant une pluralité de thèmes. La structuration thématique est également utilisée indirectement pour améliorer d’autres applications comme la recherche d’information ou le résumé automatique. Dans cet exposé, je présenterai le système de structuration thématique que j'ai implémenté durant ma thèse. Le système est composé de deux modules complémentaires : celui de segmentation thématique et celui de titrage. Le premier consiste à détecter les changements de thèmes de telle sorte que la zone entourée par deux frontières (i.e. segment) traite d’une seule thématique. L’ensemble des segments retournés est alors identifié par des étiquettes anonymes. Le rôle du seconde module est, quand à lui, d’attribuer un titre à chaque segment thématique.


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.


Introduction au calcul uniforme : Élection de leader sur les automates cellulaires à entrée périodique Nicolas Bacquey, Laboratoire d'Informatique Fondamentale de Lille

Les automates cellulaires sont représentatifs des modèles de calcul massivement parallèles. Ils consistent en une grille infinie de cellules évoluant de manière synchrone au cours du temps. Néanmoins, lorsqu'on considère les problèmes classiques qui se posent sur ces automates, leur définition et leur résolution n'utilisent qu'une partie finie de cette grille infinie. Cet exposé traite des différentes manières de donner une entrée finie à un modèle de calcul massivement parallèle et infini, qui n'a par définition aucun point de référence spatial. Les deux méthodes classiques sont soit de borner l'entrée finie par des symboles spéciaux, soit de considérer une configuration périodique, dont la période est l'entrée finie. Nous verrons en particulier que ces deux formalismes coïncident pour les automates cellulaires de dimension 1, à l'aide d'un algorithme d'élection de leader sur les configurations périodiques. Nous traiterons également des manières d'étendre cet algorithme aux automates cellulaires de dimension quelconque.


Concurrent C programs verification assisted by code and specification transformation. Allan Blanchard,


Enhanced Middleware for Maintaining Privacy in IoT Services Ahmed Elmisery,


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.


Security by design à travers deux exemples : Corrélation des événements de supervision informatique et authentification biométrique Mehdi Bentounsi,


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.