Agenda

Département
Langue
Date
Thématique
2025

septembre

  • 14:00
    15:00

    Title: Query Entailment Problem for S.

    Abstract: In description logic, possibly infinite structures are described via an
    ABox A (i.e. a basic finite structure, to be completed), and an ontology
    T (or a TBox, a finite set of constraints aiming to complete the ABox).
    The query entailment problem asks the following: given an ABox A, a TBox
    T, and a conjunctive query q (= a subgraph), does any structure
    satisfying A and T necessarily also satisfy the request?

    In ALC, the basic description logic (which is nothing more than modal
    logic in disguise), this problem is well understood, as it is known to
    be ExpTime-complete in combined complexity, and coNP-complete in data
    complexity (i.e. with TBox and query fixed) [Lutz '08].

    However, the exact complexity for S, the extension of ALC where some
    roles (= binary relations) are specified to be transitive, was not known
    yet. The status being that the problem is coNExpTime-hard [Eiter et al.
    '09] and in 2ExpTime [Calvanese et al. '98]. Two articles in 2009 and
    2010 tried to close the gap by proving coNExpTime-completeness in
    special cases, but the general question remained open.

    In this seminar, we finally answer this question by showing that the
    query entailment problem for S is actually 2-ExpTime complete. In fact,
    we show that the complexity gap is associated with the number of
    transitive roles: two distinct transitive roles are enough to get
    2-ExpTime-hardness, while the case with only one transitive role (and
    possibly many non-transitive ones) is in coNExpTime.

    This latter case is proven by showing that whenever q is not entailed by
    (A,T), then there exists a counterexample with a representation of
    exponential size (while being most certainly infinite). In the talk, we
    will show how some variant of automata over infinite trees can be
    elegantly used in order to obtain such a representation. We will also
    highlight the crucial difficulties induced by two distinct transitive
    roles, that were overlooked so far.

    178
  • 14:00
    17:00

    Cette thèse porte sur le développement de méthodes automatisées pour la segmentation artère-veine (AV) dans les images du fond d’œil, une étape essentielle pour permettre la détection précoce et non invasive des maladies systémiques et neurodégénératives. La rétine offre une fenêtre unique sur la santé neuronale et vasculaire, sa vascularisation reflétant étroitement les changements au niveau cérébral et cardiovasculaire. Par conséquent, une
    segmentation AV précise joue un rôle clé dans l’extraction de biomarqueurs vasculaires à valeur diagnostique et pronostique. Malgré son importance, la segmentation AV demeure une tâche techniquement complexe. Les artères et les veines présentent des caractéristiques visuelles et structurelles très similaires, ce qui entraîne une ambiguïté même chez les annotateurs experts. Cette difficulté est aggravée par la rareté de jeux de données annotés au pixel près et de haute qualité, nécessaires à l’entraînement de modèles fiables. L’objectif de cette thèse est de relever ces défis en développant des méthodes automatisées permettant une segmentation AV fiable, reproductible et évolutive, afin d'extraire des mesures vasculaires à partir des images du fond d’œil.
     

    Amphi LaBRI
  • 13:00
    14:00

    Conjugacy and equivalence of weighted automata

    This talk starts with a result witin classical Finite Automata Theory:
    'Two regular languages with the same number of words for each length can be mapped one onto the other by a letter-to-letter (finite) transducer'.

    The notion of generating function of regular languages leads to the
    introduction of the model of weighted automata. The conjugacy of weighted automata, a concept borrowed to symbolic dynamics, is then defined and it is shown how the above statement can be derived from the central result of this work: 'Two equivalent weighted automata are conjugate to a third one when the weight semiring is B, N, Z, or any Euclidean domain (and thus any (skew) field)'.

    The talk is based on a joint work with Marie-Pierre Béal and Sylvain
    Lombardy.

    LaBRI
  • 11:00
    12:00

    Arthur Lunven (UBx Service Innovation)

    Title: Les missions de service Innovation et AAP Prématuration

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

    LaBRI 178
  • 14:00
    15:00

    We reduce the model checking problem for a subset of Python to
    the satisfiability of a first-order formula over finite words, which is
    known to be decidable. The reduction is based on the theory of
    polyregular functions, a recently developed generalization of regular
    languages to polynomial output string-to-string functions. We
    implemented this reduction in a verification tool called PolyCheck, that
    can use both automata-based solvers and classical SMT solvers as
    backends.

    This is a joint work with Rafał Stefański that was pursued
    at the University of Warsaw, and was published at CAV'2025.

    LaBRI
  • 09:30
    12:00

    Les humains du 21ème siècle sont exposés à un nombre inédit de stimuli esthétiques, particulièrement dans les espaces numériques tels que les réseaux sociaux. Dans ces espaces, la présentation de stimuli esthétiques, par exemple l'art visuel ou la musique, dépend de systèmes de recommandations qui requièrent un retour explicite de l'utilisateur. Cependant, un retour explicite demande du travail cognitif qui peut diminuer l'expérience esthétique (EE).
    Les interfaces cerveau-ordinateur (ICOs) passives permettent une surveillance implicite en temps réel des états mentaux, affectifs et conatifs de l'utilisateur. Ce travail fait partie du projet européen BITSCOPE qui a pour objectif d'améliorer l'expérience utilisateur (UX) en personnalisant la présentation d’oeuvres d’art dans les galeries virtuelles.
    En particulier, le but de cette thèse est de tenter de concevoir des ICOs hybrides passives pour évaluer l'UX dans les galeries virtuelles d'art. L'UX dans les espaces d'art relève de l'expérience de l'art, i.e. l’EE. Les EEs sont des expériences complexes composées de divers états mentaux, notamment les états attentifs, affectifs et hédoniques. Les EEs étant hédoniques, nous postulons que des marqueurs de bonnes EE indiquent également une bonne UX et qu'améliorer les EE améliore la UX. Par conséquent, des ICOs décodant l’EE pourraient personnaliser la présentation de l'art dans les espaces numériques sans interruption et donc d'améliorer l'UX. Pour atteindre ce but, nous avons d'abord identifié des corrélats neuro-physiologiques des EEs à partir de la littérature. Nous avons également créé une base ouverte avec plus de 200 stimuli d'art visuel très divers pour être utilisés dans des expériences en esthétique empirique. Ces stimuli ont ensuite été utilisés dans un protocole expérimental classique de pŕesentation et d’évaluation de stimuli. Les données ont ensuite été analysées pour trouver des corrélats neuro-physiologiques de l’EE. Sur la base de ces analyses, nous avons implémenté des pipelines de classification classiques et de plus récents pour estimer les EEs à partir des données neuro-physiologiques en essai unique. Nous avons d'abord exploré les données de l'Électroencephalographie (EEG) et de la physiologie, i.e. l’activité électrodermale (AED) et la Photoplethysmographie, indépendamment avant de tester une approche multi-modale où des caractéristiques des différents modalités sont fusionnées ensemble. Bien que tous les modèles de décodage ont été inférieurs au niveau de chance en moyenne, certains modèles ont fourni des résultats relativement bons pour certaines personnes. Les caractéristiques AED étaient
    particulièrement informatives pour une personne, avec une précision de ca 88%. En revanche, le meilleur résultat EEG était ca 71% de précision. Nous avons observé que les EEs et leurs corrélats sont très variables, ce qui rend difficile de trouver des modèles de décodage fiables. Il semble plausible que des méthodes de décodage plus complexes, tells que l’apprentissage ensembliste, puissent améliorer les performances. Cependant, nous avons discerné des défauts
    fondamentaux dans le paradigme expérimental classique utilisé par nous et dans la littérature. Notamment, ce type de protocole impose des contraintes artificielles aux participants ce qui résulte en des différences qualitatives d'attention comparées aux expériences d'art hors du laboratoire. Ces défauts limitent la généralisation des résultats obtenus vers des applications dans la vraie vie. En outre, ces protocoles sont difficiles à adapter aux ICOs en ligne. Au lieu de cela, nous proposons un nouveau protocole expérimental écologique et adapté pour le décodage en ligne. De plus, nous examinons certains défis liés à la recommandation d'art. En particulier, nous considérons le risque de biais de récommendation qui peut diminuer l’EE. Enfin, nous discutons également des applications de santé et de bien- être, ainsi que des problèmes éthiques liés à cette technologie.
     

    Ada Lovelace

octobre