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

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/10/2022 : Data Models and Integrity Constraints: from Relations to Graphs
Carmem Satie Hara (Federal University of Paraná (UFPR)) Résumé
Attention : Débute à 13 h 30.

25/05/2022 : [Séminaire LMV] Programmation fonctionnelle synchrone des systèmes réactifs
Adrien Guatto (Université Paris Cité, IRIF) Résumé
Attention : Débute à 10 h 30.

23/05/2022 : [Séminaire LMV] Formalisation pour la sécurisation d'applications critiques
Thierry Lecomte (Clearsy) Résumé

16/05/2022 : [Séminaire GaMoC] Le problème du domino apériodique en (presque) toute dimension
Benjamin Hellouin (LRI - Univ. Paris Sud) Résumé

09/05/2022 : [Séminaire GaMoC] Autoassemblage de tuiles confluent en dimension 2 et température 1.
Jérôme Durand-Lose (Université d'Orléans, LIFO) Résumé
Attention : Débute à 15 h.

26/04/2022 : [Séminaire GaMoC] Linear-Time Minimal Cograph Editing
Christophe Crespelle (LIP - Univ Claude Bernard, Lyon) Résumé
Attention : Débute à 10 h.

25/04/2022 : Retour sur deux expériences de mobilité
Guillaume Cleuziou & Frédéric Loulergue (LIFO, Université d'Orléans; Université de la Nouvelle-Calédonie; Northern Arizona University) Résumé
Attention : Débute à 15 h.

28/02/2022 : [Séminaire GAMoC] (In)approximability of Upper Edge Domination
Henning Fernau (Université de Trèves, Allemagne) Résumé

17/01/2022 : Context-free path query processing
Martin Musicante (Federal University of Rio Grande do Norte, Brazil) Résumé
Attention : Débute à 14 h 30. Lieu : En ligne

17/01/2022 : [Séminaire LMV] Data Analysis Algorithms: Modern Challenges and Solutions using Grapics Processing Units
Benoit Gallet (Northern Arizona University) Résumé
Attention : Débute à 13 h 30. Lieu : En ligne


Résumés des séminaires


Data Models and Integrity Constraints: from Relations to Graphs Carmem Satie Hara, Federal University of Paraná (UFPR)

Veracity is one of the 5 V's that characterize large databases or Big Data. It refers to the quality of data, which involves its correctness and consistency. Data consistency has always been a concern in the database area, and one way to define it is through integrity constraints. The study of integrity constraints is a traditional part of database theory. However, several applications are derived from these studies, such as in the area of data integration and data cleansing. In this talk we will revisit the influence of data models on the definition of integrity constraints. We will start with the traditional concepts of keys and functional dependencies in relational models, moving on to hierarchical models and finishing with proposals for defining these dependencies in graph models.


[Séminaire LMV] Programmation fonctionnelle synchrone des systèmes réactifs Adrien Guatto, Université Paris Cité, IRIF

Les systèmes réactifs sont des systèmes informatiques en interaction continue avec un environnement externe qu'ils cherchent à surveiller ou contrôler. Ces systèmes sont soumis à des contraintes importantes en matière de fiabilité et d'usage des ressources (temps, espace). Dans cet exposé introductif, je décrirai une famille de langages spécialisés dans la programmation des systèmes réactifs : les langages fonctionnels synchrones. En imposant une discipline de programmation basée sur le concept de temps logique partagé, ces langages réconcilient la manipulation d'objets sémantiquement infinis avec une utilisation finie des ressources à l'exécution. Si le temps le permet, j'expliquerai ensuite comment ces langages peuvent être connectés à des travaux récents en théorie des types modale qui éclairent sous jour nouveau leurs fondements logiques.


[Séminaire LMV] Formalisation pour la sécurisation d'applications critiques Thierry Lecomte, Clearsy

Le développement d'applications sûres et sécuritaires requiert une large palette de techniques pour leur développement logiciel et matériel, ainsi que pour leur vérification/validation. L'exposé présente une solution technologique (https://www.clearsy.com/outils/clearsy-safety-platform/) combinant un certain nombre de techniques, formelles ou non, comme:

  • la redondance matérielle et applicative,
  • la preuve de modèles formels,
  • la génération de code et la compilation diversifiée,
  • le passage dans un état puits restrictif en cas d'anomalie de fonctionnement.

L'approche permet de prendre en compte les défaillances aléatoires et systématiques (norme EN5012{6, 8, 9}) dans un cadre sûr (préservation de la vie humaine) et doit être étendu pour garantir la sécurité (préservation des secrets) dans un cadre sécuritaire (normes CC, IEC62433).

L'exposé fait le point sur le cadre d'application (incluant les spécifications système), le retour d'expérience, les travaux de recherche et développement en cours ainsi les problèmes scientifiques et techniques ouverts. Les thématiques couvertes incluent, à des degrés divers: la modélisation formelle, la génération de code et la compilation, la preuve mathématique, le deep-learning et la cybersécurité, le tout sous le prisme de la certification normative.


[Séminaire GaMoC] Le problème du domino apériodique en (presque) toute dimension Benjamin Hellouin, LRI - Univ. Paris Sud

Le problème du domino consiste à prendre un jeu de couleurs et à chercher un pavage, i.e. une coloration de la grille Z2, qui évite un ensemble de motifs interdits donnés en entrée. Ce problème est indécidable en dimension 2 et plus, une conséquence de l'existence d'ensemble de motifs interdits qui ne permettent de paver le plan que de manière apériodique. De manière générale, les considérations d'(a)périodicité ont façonné en profondeur ce domaine de recherche. On peut naturellement demander si chercher spécifiquement des pavages (a)périodiques est plus ou moins difficile que le problème de base. Il s'avère que le cas apériodique est significativement différent : bien que tous deux indécidables, le domino apériodique est beaucoup plus difficile que le domino, ce qui s'exprime en termes de classes d'indécidabilité. Encore plus surprenant, cette séparation ne commence qu'à partir de la dimension 3 ou 4. Je ferai un panorama de deux résultats: en dimension 2, le domino apériodique est co-récursivement énumérable-complet ; en dimension > 3, il est hors de la hiérarchie arithmétique. Le cas de la dimension 3 reste ouvert. Je mentionnerai quelques résultats similaires sur le domino apériodique dans les espaces de pavages plus généraux.


[Séminaire GaMoC] Autoassemblage de tuiles confluent en dimension 2 et température 1. Jérôme Durand-Lose, Université d'Orléans, LIFO

Autoassemblage de tuiles confluent en dimension 2 et température 1 : si l'assemblage est fini alors il y contient un chemin infini ultimement périodique


[Séminaire GaMoC] Linear-Time Minimal Cograph Editing Christophe Crespelle, LIP - Univ Claude Bernard, Lyon

We present an algorithm for computing a minimal editing of an arbitrary graph G into a cograph, i.e. a set of edits (additions and deletions of edges) that turns G into a cograph and that is minimal for inclusion. Our algorithm runs in linear time in the size of the input graph, that is O(n+m) time where n and m are the number of vertices and the number of edges of G, respectively.


Retour sur deux expériences de mobilité Guillaume Cleuziou & Frédéric Loulergue, LIFO, Université d'Orléans; Université de la Nouvelle-Calédonie; Northern Arizona University

Dans cet exposé nous vous présenterons comment préparer une mobilité hors de métropole et l'expérience de ces mobilités à l'Université de Nouvelle Calédonie, et à la Northern Arizona University.


[Séminaire GAMoC] (In)approximability of Upper Edge Domination Henning Fernau, Université de Trèves, Allemagne

We study the problem of finding a minimal edge dominating set of maximum size in a given graph $G=(V,E)$, called \textsc{Upper EDS}. We show that this problem is not approximable within a ratio of $n^{\varepsilon-\frac{1}{2}}$, for any $\varepsilon\in (0,\frac{1}{2})$, assuming $\ptime\neq\np$, where $n=|V|$. On the other hand, for graphs of minimum degree at least~2, we give an approximation algorithm with ratio $\frac{1}{\sqrt{n}}$, matching this lower bound. We further show that \textsc{Upper EDS} is $\apx$-complete in bipartite graphs of maximum degree~4, and $\np$-hard in planar bipartite graphs of maximum degree~4. This is joint work with Jérome Monnot and David Manlove.


Context-free path query processing Martin Musicante, Federal University of Rio Grande do Norte, Brazil

(This work is joint with Ciro M. Medeiros and Umberto Costa) Path queries are used to specify paths inside a data graph to match a given pattern. Query languages such as SPARQL usually include support for regular path patterns defined by means of regular expressions. Context-free path queries define a path whose language can be defined by a context-free grammar. This kind of query is interesting in practice in domains such as genetics, data science, and source code analysis. We present an algorithm for context-free path query processing. Our algorithm takes any context-free grammar and a set of nodes of the graph as input. We argue about the correctness of our approach and show its runtime and memory complexity. We show the viability of our approach by means of prototypes implemented in Go and Python. We run experiments proposed in recent works, which include both synthetic and real RDF databases, as well as a more realistic case inspired in Biology. Our algorithm shows performance gains when compared to other algorithms implemented using single-thread programs. --------- Martin Musicante is a professor at the Computer Science Department (DIMAP) of the Federal University of Rio Grande do Norte, Brazil. He earned his B.Sc at ESLAI (Argentina) and his D.Sc in Computer Science at UFPE, Brazil. His research interests include Programming and Query Language Semantics.


[Séminaire LMV] Data Analysis Algorithms: Modern Challenges and Solutions using Grapics Processing Units Benoit Gallet, Northern Arizona University

With years, data analysis algorithms faced a constantly increasing amount of data to process and, consequently, an increasing computing time. Concurrently, many solutions have been developed to alleviate the issue of computation time, whether by reducing the complexity of the algorithm, the size of the data, or by parallelizing the computation when possible. The recent introduction of Graphics Processing Units (GPUs) into the High-Performance Computing field, greatly helped reduce the computation time of several data analysis algorithms, including the similarity join, k-NN, or k-means algorithms. And, as the GPU architectures rapidly evolve, new solutions become available to further improve the performance of said algorithms. In this presentation, we will take a look at these challenges related to such algorithms and architecture, as well as some of the possible solutions that have been or that could be developed to palliate these challenges.