Agenda

Département
Langue
Date
Thématique
2026

juin

  • 12:00
    15:00
    Français
    LaBRI
  • 14:00
    15:00

    Analysing Temporal Reasoning in Description Logics Using Formal Grammars

    In this joint work with Anton Gnatenko and Camille Bourgaux, we establish a connection between reasoning in fragments of the temporal description logic TEL (an extension of TEL with operators from LTL) and the so-called conjunctive grammars. This allows us to close some open problem regarding the ultimate periodicity of TEL models, and the undecidability of query answering. It also provides decidability results for new interesting fragements of TEL, and paves the way towards practical reasoners.

    Français
    LaBRI
  • 12:45
    13:45
    R3MOB

    En savoir plus et inscription ici.

     

    .

    Visio
  • 11:00
    12:00

    Émile Naquin (LaBRI)

    Title: Graph Exploration with Edge Weight Estimates

    Abstract:

    In the Travelling Salesman Problem, every vertex of an edge-weighted graph has to be visited by an agent who traverses the edges of the graph. In this problem, it is usually assumed that the costs of each edge are given in advance, making it computationally hard but possible to calculate an optimal tour for the agent.

    Also in the Graph Exploration Problem, every vertex of a given graph must be visited, but here the graph is not known in the beginning - at every point, an algorithm only knows about the already visited vertices and their neighbors.

    Both however are not necessarily realistic settings: Usually the structure of the graph (for example underlying road network) is known in advance, but the details are not. One usually has a prediction of how long it takes to traverse through a particular road, but due to road conditions or imprecise maps the agent might realize that a road will take slightly longer than expected when arriving on it. To deal with those deviations, it is natural to assume that the agent is able to adapt to the situation: When realizing that taking a particular road is more expensive than expected, recalculating the tour and taking another road instead is possible.

    In a sense, this setting lies in between the offline travelling salesman problem, and the online problem of graph exploration, as it allows some computation at the beginning, but remains an online problem during traversal through the graph.

    We analyze the competitive ratio of this problem based on the pertur- bation factor α of the edge weights. For general graphs we show that for realistic factors smaller than 2 there is no strategy that achieves a competitive ratio better than α, which can be matched by a simple algorithm.

    In addition, we prove an algorithm which has a competitive ratio of (1+α)/2 for restricted graph classes like complete graphs with uniform announced edge weights. Here, we present a matching lower bound as well, proving that the strategy for those graph classes is best possible. We conclude with a remark about special graph classes like cycles.

    https://algodist.labri.fr/index.php/Main/GT

    Français
    LaBRI 178
  • 16:00
    18:00

    Le jury est constitué des membres suivants :

    Tamara Munzner
    Raimund Dachselt
    Niklas Elmqvist
    Caroline Appert
    David Auber
     

    Amphi LaBRI
  • 09:30
    12:00

    Aymeric Ferron soutien sa thèse intitulée : « Exploration de visualisations concrètes et immersives pour communiquer l'impact environnemental des actions quotidiennes ».

    Salle Ada Lovelace (Inria)

juillet