Michaël Thomazo

ECAI Conference 2025 Conference Paper

Analysing Temporal Reasoning in Description Logics Using Formal Grammars

• Camille Bourgaux
• Anton R. Gnatenko
• Michaël Thomazo

We establish a correspondence between (fragments of) TEL◯, a temporal extension of the EL description logic with the LTL operator ◯k, and some specific kinds of formal grammars, in particular, conjunctive grammars (context-free grammars equipped with the operation of intersection). This connection implies that TEL◯ does not possess the property of ultimate periodicity of models, and further leads to undecidability of query answering in TEL◯, closing a question left open since the introduction of TEL◯. Moreover, it also allows to establish decidability of query answering for some new interesting fragments of TEL◯, and to reuse for this purpose existing tools and algorithms for conjunctive grammars.

NeurIPS Conference 2025 Conference Paper

Toward Interpretable Evaluation Measures for Time Series Segmentation

• Félix Chavelli
• Paul Boniol
• Michaël Thomazo

Time series segmentation is a fundamental task in analyzing temporal data across various domains, from human activity recognition to energy monitoring. While numerous state-of-the-art methods have been developed to tackle this problem, the evaluation of their performance remains critically limited. Existing measures predominantly focus on change point accuracy or rely on point-based metrics such as Adjusted Rand Index (ARI), which fail to capture the quality of the detected segments, ignore the nature of errors, and offer limited interpretability. In this paper, we address these shortcomings by introducing two novel evaluation measures: WARI (Weighted Adjusted Rand Index), a temporal extension of ARI that accounts for the position of segmentation errors, and SMS (State Matching Score), a fine-grained metric that identifies and scores four distinct and fundamental types of segmentation errors while allowing error-specific weighting. We empirically validate WARI and SMS on synthetic and real-world benchmarks, showing that they not only provide a more accurate assessment of segmentation quality but also uncover insights, such as error provenance and type, that are inaccessible with traditional measures.

KR Conference 2024 Conference Paper

Ontology-Based Query Answering over Datalog-Expressible Rule Sets is Undecidable

• David Carral
• Lucas Larroque
• Michaël Thomazo

Ontology-based query answering is a problem that takes as input a set of facts F, an ontology R (typically expressed by existential rules), a Boolean query q, and asks whether R and F entails q. This problem is undecidable in general, and a widely investigated approach to tackle it is called query rewriting: from (R, q) (a ``rule query'') is computed q_R such that for any set of facts F, it holds that R and F entail q iff F entails q_R. The literature mostly focused on q_R expressed as a union of conjunctive queries (UCQs), and an algorithm that such a q_R whenever it exists has been proposed in the literature. However, UCQ-rewritability is applicable only in restricted settings. This raises the question whether such a generic algorithm can be designed for a more expressive language, such as datalog. We solve this question by the negative, by studying the difference between datalog-expressibility and datalog-rewritability. In particular, we show that query answering under datalog-expressible rule queries is undecidable.

IJCAI Conference 2022 Conference Paper

Capturing Homomorphism-Closed Decidable Queries with Existential Rules (Extended Abstract)

• Camille Bourgaux
• David Carral
• Markus Krötzsch
• Sebastian Rudolph
• Michaël Thomazo

Existential rules are a very popular ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize properties that are preserved under homomorphisms. This paper is an extended abstract of our eponymous publication at KR 2021 where we show the converse: every decidable query that is closed under homomorphism can be expressed by an existential rule set for which the standard chase universally terminates. Membership in this fragment is not decidable, but we show via a diagonalisation argument that this is unavoidable.

KR Conference 2022 Conference Paper

Counting Queries over ELHI⊥ Ontologies

• Meghyn Bienvenu
• Quentin Manière
• Michaël Thomazo

While ontology-mediated query answering most often adopts (unions of) conjunctive queries as the query language, some recent works have explored the use of counting queries coupled with DL-Lite ontologies. The aim of the present paper is to extend the study of counting queries to Horn description logics outside the DL-Lite family. Through a combination of novel techniques, adaptations of existing constructions, and new connections to closed predicates, we achieve a complete picture of the data and combined complexity of answering counting conjunctive queries (CCQs) and cardinality queries (a restricted class of CCQs) in ELHI⊥ and its various sublogics. Notably, we show that CCQ answering is 2EXP-complete in combined complexity for ELHI⊥ and every sublogic that extends EL or DL-Lite-pos-H. Our study not only provides the first results for counting queries beyond DL-Lite, but it also closes some open questions about the combined complexity of CCQ answering in DL-Lite.

KR Conference 2022 Conference Paper

Normalisations of Existential Rules: Not so Innocuous!

• David Carral
• Lucas Larroque
• Marie-Laure Mugnier
• Michaël Thomazo

Existential rules are an expressive knowledge representation language mainly developed to query data. In the literature, they are often supposed to be in some normal form that simplifies technical developments. For instance, a common assumption is that rule heads are atomic, i. e. , restricted to a single atom. Such assumptions are considered to be made without loss of generality as long as all sets of rules can be normalised while preserving entailment. However, an important question is whether the properties that ensure the decidability of reasoning are preserved as well. We provide a systematic study of the impact of these procedures on the different chase variants with respect to chase (non-)termination and FO-rewritability. This also leads us to solve open problems related to chase termination of independent interest.

KR Conference 2022 Conference Paper

Revisiting Semiring Provenance for Datalog

• Camille Bourgaux
• Pierre Bourhis
• Liat Peterfreund
• Michaël Thomazo

Data provenance consists in bookkeeping meta information during query evaluation, in order to enrich query results with their trust level, likelihood, evaluation cost, and more. The framework of semiring provenance abstracts from the specific kind of meta information that annotates the data. While the definition of semiring provenance is uncontroversial for unions of conjunctive queries, the picture is less clear for Datalog. Indeed, the original definition might include infinite computations, and is not consistent with other proposals for Datalog semantics over annotated data. In this work, we propose and investigate several provenance semantics, based on different approaches for defining classical Datalog semantics. We study the relationship between these semantics, and introduce properties that allow us to analyze and compare them.

KR Conference 2021 Conference Paper

Capturing Homomorphism-Closed Decidable Queries with Existential Rules

• Camille Bourgaux
• David Carral
• Markus Krötzsch
• Sebastian Rudolph
• Michaël Thomazo

Existential rules are a very popular ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize properties that are preserved under homomorphisms. In this paper, we show the converse: every decidable query that is closed under homomorphism can be expressed by an existential rule set for which the standard chase universally terminates. Membership in this fragment is not decidable, but we show via a diagonalisation argument that this is unavoidable.

IJCAI Conference 2021 Conference Paper

Cardinality Queries over DL-Lite Ontologies

• Meghyn Bienvenu
• Quentin Manière
• Michaël Thomazo

Ontology-mediated query answering (OMQA) employs structured knowledge and automated reasoning in order to facilitate access to incomplete and possibly heterogeneous data. While most research on OMQA adopts (unions of) conjunctive queries as the query language, there has been recent interest in handling queries that involve counting. In this paper, we advance this line of research by investigating cardinality queries (which correspond to Boolean atomic counting queries) coupled with DL-Lite ontologies. Despite its apparent simplicity, we show that such an OMQA setting gives rise to rich and complex behaviour. While we prove that cardinality query answering is tractable (TC0) in data complexity when the ontology is formulated in DL-Lite-core, the problem becomes coNP-hard as soon as role inclusions are allowed. For DL-Lite-pos-H (which allows only positive axioms), we establish a P-coNP dichotomy and pinpoint the TC0 cases; for DL-Lite-core-H (allowing also negative axioms), we identify new sources of coNP complexity and also exhibit L-complete cases. Interestingly, and in contrast to related tractability results, we observe that the canonical model may not give the optimal count value in the tractable cases, which led us to develop an entirely new approach based upon exploring a space of strategies to determine the minimum possible number of query matches.

KR Conference 2021 Conference Paper

Parallelisable Existential Rules: a Story of Pieces

• Maxime Buron
• Marie-Laure Mugnier
• Michaël Thomazo

In this paper, we consider existential rules, an expressive formalism well adapted to the representation of ontological knowledge, as well as data-to-ontology mappings in the context of ontology-based data integration. The chase is a fundamental tool to do reasoning with existential rules as it computes all the facts entailed by the rules from a database instance. We introduce parallelisable sets of existential rules, for which the chase can be computed in a single breadth-first step from any instance. The question we investigate is the characterization of such rule sets. We show that parallelisable rule sets are exactly those rule sets both bounded for the chase and belonging to a novel class of rules, called pieceful. The pieceful class includes in particular frontier-guarded existential rules and (plain) datalog. We also give another characterization of parallelisable rule sets in terms of rule composition based on rewriting.

IJCAI Conference 2020 Conference Paper

Answering Counting Queries over DL-Lite Ontologies

• Meghyn Bienvenu
• Quentin Manière
• Michaël Thomazo

Ontology-mediated query answering (OMQA) is a promising approach to data access and integration that has been actively studied in the knowledge representation and database communities for more than a decade. The vast majority of work on OMQA focuses on conjunctive queries, whereas more expressive queries that feature counting or other forms of aggregation remain largely unexplored. In this paper, we introduce a general form of counting query, relate it to previous proposals, and study the complexity of answering such queries in the presence of DL-Lite ontologies. As it follows from existing work that query answering is intractable and often of high complexity, we consider some practically relevant restrictions, for which we establish improved complexity bounds.

I&C Journal 2019 Journal Article

On the height of towers of subsequences and prefixes

• Štěpán Holub
• Tomáš Masopust
• Michaël Thomazo

A tower is a sequence of words alternating between two languages in such a way that every word is a subsequence of the following word. We study upper and lower bounds on the number of words in maximal finite towers between two regular languages with respect to the size of the NFA (respectively the DFA) representation. We show that the upper bound is polynomial in the number of states and exponential in the size of the alphabet, and that it is asymptotically tight if the size of the alphabet is fixed. If the alphabet may grow with the number of states of the automata, the lower bound on the height of towers is exponential with respect to that number. In this case the asymptotically optimal bound remains an open problem. Since, in many cases, the constructed towers are sequences of prefixes, we also study towers of prefixes.

IJCAI Conference 2019 Conference Paper

Reasoning about Disclosure in Data Integration in the Presence of Source Constraints

• Michael Benedikt
• Pierre Bourhis
• Louis Jachiet
• Michaël Thomazo

Data integration systems allow users to access data sitting in multiple sources by means of queries over a global schema, related to the sources via mappings. Datasources often contain sensitive information, and thus an analysis is needed to verify that a schema satisfies a privacy policy, given as a set of queries whose answers should not be accessible to users. Such an analysis should take into account not only knowledge that an attacker may have about the mappings, but also what they may know about the semantics of the sources. In this paper, we show that source constraints can have a dramatic impact on disclosure analysis. We study the problem of determining whether a given data integration system discloses a source query to an attacker in the presence of constraints, providing both lower and upper bounds on source-aware disclosure analysis.

I&C Journal 2017 Journal Article

Complexity of universality and related problems for partially ordered NFAs

• Markus Krötzsch
• Tomáš Masopust
• Michaël Thomazo

Partially ordered NFAs (poNFAs) are NFAs where cycles occur only in the form of self-loops. A poNFA is universal if it accepts all words over its alphabet. Deciding universality is PSpace -complete for poNFAs. We show that this remains true when restricting to fixed alphabets. This is nontrivial since standard encodings of symbols in, e. g. , binary can turn self-loops into longer cycles. A lower coNP -complete complexity bound is obtained if all self-loops in the poNFA are deterministic. We find that such restricted poNFAs (rpoNFAs) characterize R -trivial languages, and establish the complexity of deciding if the language of an NFA is R -trivial. The limitation to fixed alphabets is essential even in the restricted case: deciding universality of rpoNFAs with unbounded alphabets is PSpace -complete. Consequently, we obtain the complexity results for inclusion and equivalence problems. Finally, we show that the languages of rpoNFAs are definable by deterministic (one-unambiguous) regular expressions.

TCS Journal 2017 Journal Article

On Boolean combinations forming piecewise testable languages

• Tomáš Masopust
• Michaël Thomazo

A regular language is k-piecewise testable (k-PT) if it is a Boolean combination of languages of the form L a 1 a 2 … a n = Σ ⁎ a 1 Σ ⁎ a 2 Σ ⁎ ⋯ Σ ⁎ a n Σ ⁎, where a i ∈ Σ and 0 ≤ n ≤ k. Given a finite automaton A, if the language L ( A ) is piecewise testable, we want to express it as a Boolean combination of languages of the above form. The idea is as follows. If the language is k-PT, then there exists a congruence ∼ k of finite index such that L ( A ) is a finite union of ∼ k -classes. Every such class is characterized by an intersection of languages of the from L u, for | u | ≤ k, and their complements. To represent the ∼ k -classes, we make use of the ∼ k -canonical DFA. We identify the states of the ∼ k -canonical DFA whose union forms the language L ( A ) and use them to construct the required Boolean combination. We study the computational and descriptional complexity of related problems.

MFCS Conference 2016 Conference Paper

On the Complexity of Universality for Partially Ordered NFAs

• Markus Krötzsch
• Tomás Masopust
• Michaël Thomazo

Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, i. e. , for which cycles occur only in the form of self-loops on a single state. A poNFA is universal if it accepts all words over its input alphabet. Deciding universality is \PSpace-complete for poNFAs, and we show that this remains true even when restricting to a fixed alphabet. This is nontrivial since standard encodings of alphabet symbols in, e. g. , binary can turn self-loops into longer cycles. A lower coNP-complete complexity bound can be obtained if we require that all self-loops in the poNFA are deterministic, in the sense that the symbol read in the loop cannot occur in any other transition from that state. We find that such restricted poNFAs (rpoNFAs) characterise the class of R-trivial languages, and we establish the complexity of deciding if the language of an NFA is R-trivial. Nevertheless, the limitation to fixed alphabets turns out to be essential even in the restricted case: deciding universality of rpoNFAs with unbounded alphabets is PSPACE-complete. Our results also prove the complexity of the inclusion and equivalence problems, since universality provides the lower bound, while the upper bound is mostly known or proved in the paper.

ECAI Conference 2014 Conference Paper

Mixing Materialization and Query Rewriting for Existential Rules

• Michaël Thomazo
• Sebastian Rudolph

Ontology-Based Data Access (OBDA) is a recent paradigm aiming at enhancing data access by taking ontological knowledge into account. When using existential rules as ontological language, query answering is an undecidable problem, whence numerous decidable classes of ontologies have been defined, ranging from classes with very good computational complexities (AC0 in data complexity) to classes with much larger expressivity. However, actually implementable algorithms have been proposed only for very restricted classes (typically those coinciding with lightweight description logics). The aim of this paper is to show how to deal with more expressive ontologies by proposing an algorithm that performs both materialization and rewriting and is applicable for a significant generalization of lightweight description logics. To this end, we first modify an existing algorithm previously proposed for a very generic class of rules, namely greedy bounded treewidth sets of rules. We then exhibit a special case, called pattern oblivious rule sets, which significantly generalizes the ℰ ℒ ℋ drdescription logic, which underlies the OWL 2 EL ontology standard, while keeping the beneficial worst-case computational complexity. We last define a subclass of pattern oblivious rules that is recognizable in polynomial time.

IJCAI Conference 2013 Conference Paper

Compact Rewritings for Existential Rules

• Michaël Thomazo

Querying large databases while taking ontologies into account is currently a very active domain research. In this paper, we consider ontologies described by existential rules (also known as Datalog+/-), a framework that generalizes lightweight description logics. A common approach is to rewrite a conjunctive query w. r. t an ontology into a union of conjunctive queries (UCQ) which can be directly evaluated against a database. However, the practicability of this approach is questionable due to 1) the weak expressivity of classes for which efficient rewriters have been implemented 2) the large size of optimal rewritings using UCQ. We propose to use semi-conjunctive queries (SCQ), which are a restricted form of positive existential formulas, and compute sound and complete rewritings, which are union of SCQ (USCQ). A novel algorithm for query rewriting, COMPACT, is presented. It computes sound and complete rewritings for large classes of ontologies. First experiments show that USCQ are both efficiently computable and more efficiently evaluable than their equivalent UCQ.

IJCAI Conference 2013 Conference Paper

Ontology Based Query Answering with Existential Rules

• Michaël Thomazo

IJCAI Conference 2013 Conference Paper

Sound, Complete, and Minimal Query Rewriting for Existential Rules

• Mélanie König
• Michel Leclère
• Marie-Laure Mugnier
• Michaël Thomazo

We address the issue of Ontology-Based Data Access which consists of exploiting the semantics expressed in ontologies while querying data. Ontologies are represented in the framework of existential rules, also known as Datalog+/-. We focus on the backward chaining paradigm, which involves rewriting the query (assumed to be a conjunctive query, CQ) into a set of CQs (seen as a union of CQs). The proposed algorithm accepts any set of existential rules as input and stops for so-called finite unification sets of rules (fus). The rewriting step relies on a graph notion, called a piece, which allows to identify subsets of atoms from the query that must be processed together. We first show that our rewriting method computes a minimal set of CQs when this set is finite, i. e. , the set of rules is a fus. We then focus on optimizing the rewriting step. First experiments are reported in the associated technical report.

I&C Journal 2012 Journal Article

On the complexity of entailment in existential conjunctive first-order logic with atomic negation

• Marie-Laure Mugnier
• Geneviève Simonet
• Michaël Thomazo

We consider the entailment problem in the fragment of first-order logic (FOL) composed of existentially closed conjunctions of literals (without functions), denoted by FOL ( ∃, ∧, ¬ a ). This problem can be recast as several fundamental problems in artificial intelligence and databases, namely query containment for conjunctive queries with negation, clause entailment for clauses without functions and query answering with incomplete information for Boolean conjunctive queries with negation over a fact base. Entailment in FOL ( ∃, ∧, ¬ a ) is Π 2 P -complete, whereas it is only NP-complete when the formulas contain no negation. We investigate the role of specific literals in this complexity increase. These literals have the property of being “exchangeable”, with this notion taking the structure of the formulas into account. To focus on the structure of formulas, we shall see them as labeled graphs. Graph homomorphism, which provides a sound and complete proof procedure for positive formulas, is at the core of this study. Let Entailment k be the following family of problems: given two formulas g and h in FOL ( ∃, ∧, ¬ a ), such that g has at most k pairs of exchangeable literals, is g entailed by h? The main results are that Entailment k is NP-complete if k is less or equal to 1, and P ‖ NP -complete for any value of k greater or equal to 3. As a corollary of our proofs, we are able to classify exactly Entailment k for any value of k ≠ 2 when g is decomposable into a tree.