- Renseignements pratiques
- Enseignement

**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

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

08/04/2024 : **TBA**
*Nicolo Tonci (Invité Pamda)*
Résumé

25/03/2024 : **Présentation de la charte de mise à disposition d’un droit d’administration local pour les personnels**
*Baptiste Mulot (DSI Université Orléans)*
Résumé

20/03/2024 : **Empowering Data Platforms with Smart Data Modeling and Management Strategies **
*Matteo Francia (Université de Bologne (Italie))*
Résumé

Attention : Débute à 15 h.

18/03/2024 : **Melocoton: A Program Logic for Verified Interoperability Between OCaml and C **
*Armaël Gueneau (INRIA Saclay)*
Résumé

11/03/2024 : **Covering some vertices with paths and a Hamiltonian degree condition for tough graphs **
*Cléophée Robin (GREYC)*
Résumé

26/02/2024 : **Path Covers of Temporal Graphs**
*Antoine Dailly (LIMOS)*
Résumé

19/02/2024 : **[PAMDA] A Global Approach for Optimizing Denormalized Schemas through a Multidimensional Cost Model**
*Jihane Mali (De Vinci Research Center)*
Résumé

05/02/2024 : **Énumération output-sensitive des complétions cordales minimales**
*Caroline Brosse (INRIA, Sophia-Antipolis)*
Résumé

22/01/2024 : **Effective Exploration of Graph-Structured Data**
*Madhulika Mohanty (INRIA, Saclay)*
Résumé

15/01/2024 : **[GAMoC] Computability of compact sets**
*Djamel Eddine AMIR (LORIA Nancy)*
Résumé

08/01/2024 : **MaLISSiA: Machine Learning and Interpretation of Sub-Surface Architectures**
*Gautier Laurent (ISTO)*
Résumé

**TBA** Nicolo Tonci, Invité Pamda

TBA

**Présentation de la charte de mise à disposition d’un droit d’administration local pour les personnels** Baptiste Mulot, DSI Université Orléans

Dans le contexte de l’application de la Politique de Sécurité des Systèmes d’Information de l’Etat (PSSIE - N°5725/SG), il est exigé de limiter l’utilisation du compte d’administration local des postes de travail informatique aux équipes en charge de l’exploitation et du support de ces postes.
L’utilisation des privilèges d’administration doit être réalisée uniquement pour les actions le nécessitant, pour installer des logiciels pédagogiques par exemple. Les utilisateurs ne doivent ainsi disposer que des privilèges nécessaires à la réalisation des actions relevant de leur mission.
Conscient que cette exigence de sécurité ne doit pas entraver le bon fonctionnement de l’établissement, la DSI a mis en place une charte de mise à disposition d’un compte d’administration local.
Celle-ci permet de définir un cadre respectant les obligations de la PSSIE tout en garantissant la flexibilité nécessaire à la réalisation des missions des agents.

**Empowering Data Platforms with Smart Data Modeling and Management Strategies ** Matteo Francia, Université de Bologne (Italie)

Data platforms are advanced and distributed information systems that manage the entire data lifecycle through ecosystems of services glued and automated by metadata. Creating effective data platforms requires addressing several issues, including (i) choosing appropriate services based on the data processes to support, (ii) finding data representations that are flexible enough to store heterogeneous data and enable efficient queries, (iii) defining querying systems to query data distributed in different engines, and (iv) leveraging meta-data for automated and smart management. Such challenges must be tackled by techniques and methodologies involving different stakeholders (e.g., designers, end users, cloud service providers) and must be tested on real case studies to understand their real power. This is of particular interest following the increasing interest in digital transformation (e.g., the Agritech sector) fueled by the ever-increasing data generated by more and more pervasive systems.

**Melocoton: A Program Logic for Verified Interoperability Between OCaml and C ** Armaël Gueneau, INRIA Saclay

In recent years, there has been tremendous progress on developing program logics for verifying the correctness of programs in a rich and diverse array of languages. Thus far, however, such logics have assumed that programs are written entirely in a single programming language. In practice, this assumption rarely holds since programs are often composed of components written in different programming languages, which interact with one another via some kind of foreign function interface (FFI).
In this talk, I will present our first steps towards the goal of developing program logics for multi-language verification. Specifically, I will present Melocoton, a multi-language program verification system for reasoning about OCaml, C, and their interactions through the OCaml FFI. Melocoton consists of the first formal semantics of (a large subset of) the OCaml FFI—previously only described in prose in the OCaml manual—as well as the first program logic to reason about the interactions of program components written in OCaml and C.
Melocoton is fully mechanized in Coq on top of the Iris separation logic framework.

**Covering some vertices with paths and a Hamiltonian degree condition for tough graphs ** Cléophée Robin, GREYC

A graph G is Hamiltonian if it exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G − S is at most |S| / t.
In 1973, Chvàtal conjecture the following : There exists a constant t such that every t-tough graphs is Hamiltonian.
Let t be a positive integer. A graph G with degree sequence d_1,d_2,…,d_n is P(t) (t being a positive integer) If for all i, t ≤ i < n/2, d_i ≤ i ⇒ d_{n−i+t} ≥ n−i. In 1995, Hoàng conjecture the following : If G is t-tough and P(t) then G is Hamiltonian. Hoàng prove that it is true for t ≤ 3. In 2023, Hoang and Robin proved that it is also true for t ≤ 4 by extending the Closure Lemma due to Bondy and Chvàtal into a version for tough graphs.
We prove that it is true for t≤7. To do so, we prove a lemma about covering some vertices of a graph with a bounded number of paths.
This is joint work with Chình T. Hoàng and Paul Dorbec.

**Path Covers of Temporal Graphs** Antoine Dailly, LIMOS

A famous result by Dilworth on posets implies that computing a minimum-size path cover (a collection of paths such that every vertex is in some path) of a directed acyclic graph (DAG) is polynomial. Those algorithms have been studied since the 1950s and are still the subject of recent improvements due to applications in fields such as bioinformatics or computational logic. Inspired by the problem of Multi-Robot Path Finding, we translate the problem on temporal graphs, that is, graphs whose arc-set changes over discrete time-steps (we say that a temporal graph is a temporal DAG/tree/etc if the underlying graph, using the union of all arcs that appear, is a DAG/tree/etc). A temporal path, in such a setting, is a path in the underlying (di)graph such that the arcs appear in strictly increasing time-steps (a robot cannot traverse multiple edges at the same time). We are interested in two problems: Temporal Path Cover (TPC), where we aim to simply cover the vertices of the temporal graph using temporal paths; and Temporally Disjoint Path Cover (TD-PC), where we want to cover the vertices with the added condition that two paths cannot occupy the same vertex at the same time, thus representing a partition by using the time-steps as a new dimension allowing paths to use the same vertex at different times (for when robots occupy the whole vertex when traversing it, for example). In both cases, we want to minimize the size of the cover. We prove that the two problems are NP-hard on temporal DAGs, even with strong constraints on both the underlying DAG and the time-steps. However, on temporal trees, while TD-PC remains NP-hard, TPC can be solved in polynomial-time. This is obtained by creating an auxiliary graph expressing the temporal connectedness of vertices, exhibiting an equivalence between temporal paths in the temporal graph and cliques in the auxiliary graph, and proving that the auxiliary graph is weakly chordal, allowing us to use powerful algorithms from the literature. Both problems are also polynomial-time solvable on temporal rooted directed trees and temporal lines, which is not the case of all problems on temporal graphs (such as Linkage). We also give an XP algorithm for TPC and an FPT algorithm for TD-PC, both parameterized by the treewidth plus the total number of time-steps. On the structural side, we discuss on when a temporal analogue of Dilworth's theorem holds in the classes that we study.

**[PAMDA] A Global Approach for Optimizing Denormalized Schemas through a Multidimensional Cost Model** Jihane Mali, De Vinci Research Center

As the volume of data continues to grow, the complexity of database systems has surged, giving rise to NoSQL systems. This forces Information Systems (IS) architects to constantly adapt their data models (i.e., the structure of stored information) and meticulously select the optimal option(s) for data storage and management. In response to this challenge, we propose an automated global approach for guiding the transformation of data models. Our approach initiates by transforming the conceptual model into a logical data model, then applies refinement rules recursively to generate all possible data models. To reduce the search space, our approach employs a heuristic that avoids redundancies and considers the use case.
Additionally, we propose a cost model, enabling the comparison of generated data models at a logical level. This cost model integrates both data model and query costs, along with considerations for environmental impact, financial, and time costs. For the first time, our approach introduces a multidimensional cost model that evaluates time, environmental, and financial constraints. This cost model eases the comparison of data models, helping with the selection of the most suitable one for a given use case and context by optimizing either the environmental impact or the stability of the data model.

**Énumération output-sensitive des complétions cordales minimales** Caroline Brosse, INRIA, Sophia-Antipolis

Minimal chordal completions of a graph, also called minimal triangulations, are an important object in graph theory. For some applications, e.g. to databases, it is useful to generate all minimal chordal completions of a graph as efficiently as possible. However, for efficiency we need to take into account the large (possibly exponential) number of solutions. This long-lasting problem was successfully addressed in 2017: Carmeli, Kenig, and Kimelfeld designed an efficient algorithm for the listing of all minimal chordal completions of a graph. Its total running time is polynomial in the number of solutions. However, for more efficiency, we aim at designing an algorithm running with polynomial delay: the time needed between two consecutive outputs should be polynomial in the input size only.
In this talk, I will present a new enumeration algorithm for the minimal chordal completions of a graph, running with polynomial delay and exponential space. After that, the space usage will be addressed, and I will exhibit how to modify our algorithm so that it only needs polynomial space.

**Effective Exploration of Graph-Structured Data** Madhulika Mohanty, INRIA, Saclay

Large Graphs such as YAGO, DBPedia, and Wikidata, form the backbone for many applications including chatbots, personal assistants and question answering systems. Graph database (GDB) users typically use structured queries to precisely express their information needs. However, given the exact match semantics of these languages, a common challenge that they face is that of getting empty or too few results. In this talk, I will discuss some solutions that enable GDB users to explore unfamiliar graphs. First, we integrate connecting tree patterns (CTPs) with existing graph query languages like GPML, SPARQL or Cypher, leading to Extended Queries (EQs). This allows finding general connections between two or more groups of nodes in a graph, without the need to specify exactly how. I will then present an efficient algorithm to evaluate the CTPs. Further, I will introduce Spec-QP, a system that performs automatic reformulations on user queries and efficiently evaluates them. I will conclude my talk with some ongoing works and future research directions.

**[GAMoC] Computability of compact sets** Djamel Eddine AMIR, LORIA Nancy

The topological properties of a set have a strong impact on its
computability properties. A striking illustration of this idea is given
by spheres and finite graphs without endpoints: if a set X is
homeomorphic to a sphere or a such graph, then any algorithm that
semicomputes X in some sense can be converted into an algorithm that
fully computes X. In other words, the topological properties of X enable
one to derive full information about X from partial information about X.
In that case, we say that X has computable type. Those results have been
obtained by Miller and Iljazović in the recent years.
We give a characterization of finite simplicial complexes having
computable type using a local property of stars of vertices. Moreover,
the reduction to homology implies that the computable type property is
decidable, for finite simplicial complexes of dimension at most 4. We
argue that the stronger, relativized version of computable type, is
better behaved. Consequently, we obtain characterizations of strong
computable type, related to the descriptive complexity of topological
invariants. This leads us to investigate the expressive power of low
complexity invariants in the Borel hierarchy and their ability to
differentiate between spaces. Notably, we show that they are sufficient
for distinguishing finite topological graphs.

**MaLISSiA: Machine Learning and Interpretation of Sub-Surface Architectures** Gautier Laurent, ISTO

This seminar will present an original approach to artificial intelligence application in geosciences, as proposed in the MaLISSiA project.
Artificial intelligence and digital twins offer tremendous opportunities for modelling and understanding Earth systems. However, these new developments have mainly been applied to geophysical processes occurring within relatively well-constrained geometries (e.g., on earth surface) and they have yet to make a breakthrough in the characterization of sub-surface architectures. Yet these geometrical considerations are determinant in the localization of sub-surface Earth processes. The difficulty to access sub-surface causes paramount epistemic uncertainties, which result in peculiar scientific challenges, e.g., the dependencies to scale, to time, and a general lack of observation with respect to the complexity of structures. These limitations are generally counterbalanced by expert interpretations that rely on human learning from analogues (outcrops and simulations). The search for more formal and automated solutions is challenging both the formalization of geological knowledge and the development of innovative artificial intelligence methods.
The MaLISSiA project draws its inspiration from the geocognitive process developed by human learning and interpretation. It proposes a new paradigm for automatically interpreting and explaining sub-surface architectures. This paradigm is based on two founding components: (1) a formalisation of geological and interpretation concepts in dedicated ontologies; (2) a Geocognitive Interpretation Process that breaks a complex spatial data assimilation problem into a series of explanation proposal and testing. Such formalism also enables the training of machine learning algorithms to answer key questions in the process. This training calls for the development of a corpus of interpreted geological references, based on both natural objects and process-based simulations that reproduce geological history.

Université d'Orléans | INSA Centre Val de Loire