# Analysing Temporal Reasoning in Description Logics Using Formal Grammars (Extended Abstract)

Camille Bourgaux, Anton Gnatenko, Michaël Thomazo

► To cite this version:

Camille Bourgaux, Anton Gnatenko, Michaël Thomazo. Analysing Temporal Reasoning in Description Logics Using Formal Grammars (Extended Abstract). DL 2025 - 38th International Workshop on Description Logics, Sep 2025, Opole, Poland. hal-05291517

HAL Id: hal-05291517

https://inria.hal.science/hal-05291517v1

Submitted on 1 Oct 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Analysing Temporal Reasoning in Description Logics Using Formal Grammars (Extended Abstract)

Camille Bourgaux<fnref n="1" />, Anton Gnatenko<fnref n="2" /> and Michaël Thomazo<fnref n="1" />

## Abstract

We establish a correspondence between (fragments of) $TEL^\circ$, a temporal extension of $EL$ with the LTL operator $\sqsubseteq^k$, and conjunctive grammars (context-free grammars equipped with the operation of intersection). This connection implies that $TEL^\circ$ does not enjoy ultimate periodicity of models, and further leads to undecidability of query answering in $TEL^\circ$, closing a question left open since the introduction of $TEL^\circ$. It also allows to establish decidability of query answering for some new fragments of $TEL^\circ$, and to reuse for this purpose existing tools and algorithms for conjunctive grammars.

## Keywords

Description logics, temporal reasoning, conjunctive grammars, ontology-mediated query answering

This extended abstract presents the main results of a paper accepted for ECAI 2025 [1]. We consider (fragments of) $TEL$, a temporal extension of $EL$ with operators of linear temporal logic (LTL) introduced by Gutiérrez-Basulto et al. [2]. In this setting, ABox facts are associated with timestamps (they are of the form $A(a, n)$ or $r(a, b, n)$ with $n \in \mathbb{Z}$) and TBox concept inclusions may feature some operators from LTL: $\sqsubseteq$ (next), $\sqsupseteq$ (previous), $\diamond$ (eventually) and $\diamond$ (eventually in the past). Moreover, it is allowed to specify that some roles (binary relations) are rigid, i.e. do not change over time.

**Example 1.** Imagine that Alice is a professor in 2025, denoted Prof (Alice, 2025). Professorship is permanent and requires advising students, who in three years become doctors. Being an advisor of a doctor makes one proud, and proud professors are happy. This knowledge is formalized as follows (using a rigid role advisorOf):

Prof $\sqsubseteq$ $\circ$ Prof Prof $\sqcap$ Proud $\sqsubseteq$ Happy Student $\sqsubseteq$ $\circ^3$ Dr

Prof $\sqsubseteq$ $\exists$ advisorOf . Student $\exists$ advisorOf . Dr $\sqsubseteq$ Proud

*Figure 1a provides a graphical representation of some information about Alice that can be inferred from Prof (Alice, 2025) and the above TEL-TBox. In particular, Alice is happy in 2028.*

<figure><img src="image_2.png" /></figure>

DL 2025: 38th International Workshop on Description Logics, September 3–6, 2025, Opole, Poland

<figure><img src="image_3.png" /></figure>

camille.bourgaux@ens.fr (C. Bourgaux); anton.gnatenko@student.unibz.it (A. Gnatenko); michael.thomazo@inria.fr (M. Thomazo)

<figure><img src="image_4.png" /></figure>

https://www.di.ens.fr/camille.bourgaux/ (C. Bourgaux); https://gnatenko.github.io (A. Gnatenko); https://www.di.ens.fr/michael.thomazo/ (M. Thomazo)

<figure><img src="image_5.png" /></figure>

0000-0002-8806-6682 (C. Bourgaux); 0000-0003-1499-2090 (A. Gnatenko); 0000-0002-1437-6389 (M. Thomazo)

<figure><img src="image_6.png" /></figure>

© 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

<figure><img src="image_7.png" /></figure>

CEUR Workshop Proceedings (CEUR-WS.org)

<footnote n="1">¹DI ENS, ENS, CNRS, PSL University & Inria, Paris, France</footnote>

<footnote n="2">²Free University of Bozen-Bolzano, Italy</footnote>
<figure><img src="image_8.png" /></figure>

(a) Some inferences for Example 1. Dashed lines represent the temporal evolution of a given element, while dotted lines represent a relation whose existence is known due to role rigidity.

(b) An illustration for the facts that $c^3 \in L_{G_T}(\mathcal{N}_{ProfProf})$, in the upper part, and $c^3 \in L_{G_T}(\mathcal{N}_{ProfProud})$, in the lower part. Each symbol $c$ stands for a step forward in time.

<caption>**Figure 1:** Illustrations for the TBox $\mathcal{T}$ of Example 1.</caption>

$\mathcal{TEL}$ stems from a line of research which studies combinations of various description logics and LTL operators [3, 4, 5]. For a more in-depth discussion of temporal reasoning, we refer the reader to the survey by Artale et al. [6].

**Query answering and ultimately periodic TBoxes.** We refer to Gutiérrez-Basulto et al. [2] for the formal definition of $\mathcal{TEL}$. We write $(\mathcal{T}, \mathcal{A}) \models A(a, n)$ if a fact $A(a, n)$ is logically implied by a TBox $\mathcal{T}$ and an ABox $\mathcal{A}$, and $\mathcal{T} \models A \sqsubseteq \circ^n B$ if the concept inclusion $A \sqsubseteq \circ^n B$ is logically implied by $\mathcal{T}$. The temporal atomic query (TAQ) answering problem is that of deciding, given $\mathcal{T}, \mathcal{A}$ and $A(a, n)$, whether $(\mathcal{T}, \mathcal{A}) \models A(a, n)$. In particular, if $\mathcal{T}$ is the TBox of Example 1, we have $(\mathcal{T}, \{\text{Prof}(\text{Alice}, 2025)\}) \models \text{Happy}(\text{Alice}, 2028)$. We write $\mathcal{N}_C(\mathcal{T})$ for the set of concept names that occur in $\mathcal{T}$.

Gutiérrez-Basulto et al. [2] showed that TAQ answering is undecidable for $\mathcal{TEL}$. To restore decidability, they considered the fragment $\mathcal{TEL}^\circ$, which only allows operators $\circ$ and $\circ^-$, and imposed additional syntactic constraints based on some form of acyclicity (either on the description logics side, or on the temporal side). The constraints were designed to enforce the crucial property of ultimate periodicity. A TBox $\mathcal{T}$ is ultimately periodic if for all $A, B \in \mathcal{N}_C(\mathcal{T})$, the language $\{c^n \mid \mathcal{T} \models A \sqsubseteq \circ^n B\}$ is regular,<fnref n="1" /> and TAQ answering with ultimately periodic $\mathcal{TEL}^\circ$-TBoxes is in PSPACE, for data complexity [2]. It was left open whether every $\mathcal{TEL}^\circ$-TBox is ultimately periodic and whether TAQ answering with $\mathcal{TEL}^\circ$-TBoxes is decidable.

Our contribution is to link temporal reasoning with $\mathcal{TEL}^\circ$-TBoxes to the study of associated formal languages, which allows us to close (negatively) these open questions and obtain additional results. We work with $\mathcal{TEL}^\circ$-TBoxes in normal form, whose concept inclusions are of the form

$$A \sqsubseteq \circ^n B \qquad A \sqcap A' \sqsubseteq B \qquad \exists r. A \sqsubseteq B \qquad A \sqsubseteq \exists r. B \quad (1)$$

with $n \in \mathbb{Z}$ encoded in unary. We will further consider two fragments of $\mathcal{TEL}^\circ$: the *future* fragment, $\mathcal{TEL}_{future}^\circ$, is obtained by setting $n \ge 0$, and the *linear* fragment, $\mathcal{TEL}_{lin}^\circ$, disallows

<footnote n="1">¹Gutiérrez-Basulto et al. [2] gave a different definition based on quasimodels, but it is equivalent to ours.</footnote>
concept inclusions of the form $A \sqcap A' \subseteq B$. For simplicity, in this extended abstract we assume that all roles are rigid (all the results hold without this assumption).

**Conjunctive grammars** as introduced by Okhotin [7], have the form $G = (N, \Sigma, R)$, with an alphabet $\Sigma$ and finite sets $N$, of nonterminals, and $R$, of rules of the form $N \to \alpha\&\beta$, where $N \in N$, and $\alpha, \beta \in (N \cup \Sigma)^*$. The semantics extends that of context-free grammars [8], with $\alpha\&\beta$ being the intersection of languages generated by $\alpha$ and $\beta$. We write $L_G(N)$ for the language generated by $N$ (such languages are called conjunctive). An example of a conjunctive language which is not context-free is $\{a^n b^n c^n \mid n \in \mathbb{N}\} = \{a^n b^n c^k \mid k, n \in \mathbb{N}\} \cap \{a^k b^n c^n \mid k, n \in \mathbb{N}\}$. We refer to the survey by Okhotin [9] for more details.

The membership problem for conjunctive grammars is P-complete [10]. A language (or a grammar) is called unary when the underlying alphabet contains just one symbol, i.e. $\Sigma = \{c\}$. It follows from Parikh's Theorem [11] that every unary context-free language is regular. In contrast, there are unary conjunctive languages that are nonregular [12], and it is even undecidable whether a given grammar generates an empty language, or a regular language [13].

**TBoxes and grammars.** We establish a correspondence between TBoxes of $\mathcal{T}\mathcal{E}\mathcal{L}_{\text{future}}^{\circ}$ and $\mathcal{T}\mathcal{E}\mathcal{L}_{\text{lin}}^{\circ}$ and unary grammars.

**Theorem 2.** For every $\mathcal{T}\mathcal{E}\mathcal{L}_{\text{future}}^{\circ}$-TBox $\mathcal{T}$, one can construct in polynomial time a unary conjunctive grammar $G_{\mathcal{T}} = (N_{\mathcal{T}}, \{c\}, R_{\mathcal{T}})$ such that for any $A, B \in \mathbb{N}_C(\mathcal{T})$, there is $N_{AB} \in N_{\mathcal{T}}$ such that $c^n \in L_{G_{\mathcal{T}}}(N_{AB})$ iff $\mathcal{T} \models A \sqsubseteq \circ^n B$.

We sketch the construction. Set $N_{\mathcal{T}} = \{N_{AB} \mid A, B \in \mathbb{N}_C(\mathcal{T})\}$ and let $R_{\mathcal{T}}$ contain exactly the following rules.

$$N_{AB} \to \varepsilon, \quad \text{for } A \sqsubseteq B \in \mathcal{T} \text{ or } A = B \qquad (2)$$

$$N_{AB} \to c^k, \quad \text{for } A \sqsubseteq \circ^k B \in \mathcal{T}, k > 0 \qquad (3)$$

$$N_{AB} \to N_{AC} \& N_{AD}, \quad \text{for } A \in \mathbb{N}_C(\mathcal{T}), C \sqcap D \sqsubseteq B \in \mathcal{T} \qquad (4)$$

$$N_{AB} \to N_{CD}, \quad \text{for } A \sqsubseteq \exists r.C, \exists r.D \sqsubseteq B \in \mathcal{T} \qquad (5)$$

$$N_{AB} \to N_{AC} N_{CB}, \quad \text{for } A, B, C \in \mathbb{N}_C(\mathcal{T}) \qquad (6)$$

Intuitively, for every pair of concept names $A, B \in \mathbb{N}_C(\mathcal{T})$, $G_{\mathcal{T}}$ encodes every possible way of deriving $B(a, n)$ from $A(a, 0)$ with $\mathcal{T}$: either directly (using (2) when $n = 0$ or (3) when $n = k > 0$), or by obtaining $C(a, n)$ and $D(a, n)$ that together give $B(a, n)$ (4), or by going through an anonymous object (5), or through an intermediate point $C(a, m)$, $0 \le m \le n$ (6). See Figure 1b for an illustration.

Interestingly, a converse translation is also possible.

**Theorem 3.** For every unary conjunctive grammar $G = (N, \{c\}, R)$, one can construct in polynomial time a $\mathcal{T}\mathcal{E}\mathcal{L}_{\text{future}}$-TBox $T_G$ and $A \in \mathbb{N}_C(T_G)$, such that for every $B \in N$ there is $B \in \mathbb{N}_C(T_G)$ such that $T_G \models A \sqsubseteq \circ^n B$ iff $c^n \in L_G(B)$.

When considering the linear fragment, a similar connection can be built using only context-free grammars (over a two-symbol alphabet).
**Theorem 4.** For every $TE\mathcal{L}_{\text{lin}}^{\circ}$-TBox $\mathcal{T}$, there exists a context-free grammar $\Gamma_{\mathcal{T}} = (N_{\mathcal{T}}, \{c, d\}, R'_{\mathcal{T}})$, of size polynomial in $|\mathcal{T}|$, such that for any $A, B \in N_{\mathcal{C}}(\mathcal{T})$, there is $N_{AB} \in N$ such that $\mathcal{T} \models A \sqsubseteq \circ^n B$ iff there exists $w \in L_{\Gamma_{\mathcal{T}}}(N_{AB})$ with $\#c(w) - \#d(w) = n$.

Here, $N_{\mathcal{T}} = \{N_{AB} | A, B \in N_{\mathcal{C}}(\mathcal{T})\}$ is as in Theorem 2, and $R'_{\mathcal{T}}$ contains exactly the rules defined by (2), (3), (5), (6), as well as the following rules.

$$ N_{AB} \rightarrow d^{|k|}, \qquad \text{for } A \sqsubseteq \circ^k B \in \mathcal{T}, k < 0 \qquad (3^*) $$

In a word $w \in \{c, d\}^*$, a symbol $c$ corresponds to a step forwards in time, and a symbol $d$ to a step backwards. Otherwise, the intuition behind $\Gamma_{\mathcal{T}}$ is the same as that given for $G_{\mathcal{T}}$.

Note that Theorem 4 is not constructive: although $\Gamma_{\mathcal{T}}$ can be computed when all roles in $\mathcal{T}$ are rigid, in the general case we could only prove that it exists.

**Consequences for temporal atomic query answering.** Using Theorem 2, we show that TAQ answering with $TE\mathcal{L}_{\text{future}}^{\circ}$-TBoxes is decidable in polynomial time$^2$. It also follows that one can use tools that have been developed for conjunctive grammars, such as *Whale Calf* [14]. Furthermore, by Theorem 4 and Parikh's Theorem [11], every $TE\mathcal{L}_{\text{lin}}^{\circ}$-TBox is ultimately periodic. Using this, we show that TAQ answering with $TE\mathcal{L}_{\text{lin}}^{\circ}$-TBoxes is NL-complete for data complexity (and in EXPSPACE for combined complexity, when all role names are rigid).

On the other hand, by Theorem 3 and results on unary conjunctive grammars [9], there exists a $TE\mathcal{L}_{\text{future}}^{\circ}$-TBox that is not ultimately periodic. Moreover, we show that deciding emptiness of unary conjunctive grammars is reducible to TAQ answering with $TE\mathcal{L}^{\circ}$-TBoxes, or to TAQ answering with $TE\mathcal{L}_{\text{future}}^{\circ}$-TBoxes extended with rigid concept names. It follows that TAQ answering is undecidable in these two cases. It is also undecidable to check if the language $\{c^n | \mathcal{T} \models A \sqsubseteq \circ^n B\}$ is regular for a $TE\mathcal{L}_{\text{future}}^{\circ}$-TBox $\mathcal{T}$ and $A, B \in N_{\mathcal{C}}(\mathcal{T})$.

The fact that $TE\mathcal{L}_{\text{future}}^{\circ}$ is not ultimately periodic is arguably unexpected, as its temporal component, *LTL*, is ultimately periodic [15], and its DL component, $\mathcal{EL}$, is such that every pair $(\mathcal{T}, A)$ possesses a canonical model which has, informally speaking, a regular structure [16]. It remains open if ultimate periodicity of $TE\mathcal{L}^{\circ}$-TBoxes is decidable, since for the corresponding problem—given a unary conjunctive grammar tell if all its nonterminals generate regular languages—no result is known.

We hope to employ the TBox-grammar correspondence to develop a practical reasoner for $TE\mathcal{L}_{\text{future}}^{\circ}$. On the more theoretical side, it is possible that this correspondence can be lifted to more expressive temporal description logics and more general classes of formal grammars (e.g. Boolean grammars [9]). We also believe that our results may be of independent interest for the theory of unary conjunctive grammars.

## Acknowledgments

Many thanks to Roman Kontchakov for introducing us to the problem of ultimate periodicity from the perspective of semilinear sets. We would also like to thank Alexander Okhotin for providing us with the code of *Whale Calf* and valuable suggestions on the implementation.

<footnote>$^2$This can be alternatively derived from the results of Gutiérrez-Basulto et al. [2] on the temporally acyclic $TE\mathcal{L}^{\circ}$.</footnote>
References

[1] C. Bourgaux, A. Gnatenko, M. Thomazo, Analysing temporal reasoning in description logics using formal grammars, in: ECAI (to appear), 2025.

[2] V. Gutiérrez-Basulto, J. C. Jung, R. Kontchakov, Temporalized EL ontologies for accessing temporal data: Complexity of atomic queries, in: IJCAI, 2016. URL: http://www.ijcai.org/Abstract/16/160.

[3] A. Artale, R. Kontchakov, C. Lutz, F. Wolter, M. Zakharyaschev, Temporalising tractable description logics, in: TIME, 2007. doi:10.1109/TIME.2007.62.

[4] A. Artale, R. Kontchakov, F. Wolter, M. Zakharyaschev, Temporal description logic for ontology-based data access, in: IJCAI, 2013. URL: http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6824.

[5] A. Artale, R. Kontchakov, A. Kovtunova, V. Ryzhikov, F. Wolter, M. Zakharyaschev, First-order rewritability and complexity of two-dimensional temporal ontology-mediated queries, J. Artif. Intell. Res. (2022). doi:10.1613/JAIR.1.13511.

[6] A. Artale, R. Kontchakov, A. Kovtunova, V. Ryzhikov, F. Wolter, M. Zakharyaschev, Ontology-mediated query answering over temporal data: A survey (invited talk), in: TIME, 2017. doi:10.4230/LIPICS.TIME.2017.1.

[7] A. Okhotin, Conjunctive grammars, J. Autom. Lang. Comb. 6 (2001) 519–535. doi:10.25596/JALC-2001-519.

[8] N. Chomsky, Three models for the description of language, IRE Transactions on Information Theory 2 (1956) 113–124. doi:10.1109/TIT.1956.1056813.

[9] A. Okhotin, Conjunctive and boolean grammars: The true general case of the context-free grammars, Computer Science Review 9 (2013) 27–59. doi:10.1016/j.cosrev.2013.06.001.

[10] A. Okhotin, A recognition and parsing algorithm for arbitrary conjunctive grammars, Theoretical Computer Science 302 (2003) 365–399. doi:https://doi.org/10.1016/S0304-3975(02)00853-8.

[11] R. J. Parikh, On context-free languages, J. ACM 13 (1966) 570–581. doi:10.1145/321356.321364.

[12] A. Jeż, Conjunctive grammars generate non-regular unary languages, Int. J. Found. Comput. Sci. 19 (2008) 597–615. doi:10.1142/S012905410800584X.

[13] A. Jeż, A. Okhotin, Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth, Theory of Computing Systems 46 (2010) 27–58. doi:10.1007/S00224-008-9139-5.

[14] A. Okhotin, Whale calf, a parser generator for conjunctive grammars, in: CIAA, 2002.

[15] A. P. Sistla, E. M. Clarke, The complexity of propositional linear temporal logics, J. ACM 32 (1985) 733–749. doi:10.1145/3828.3837.

[16] R. Kontchakov, M. Zakharyaschev, An introduction to description logics and query rewriting, in: RW, 2014. doi:10.1007/978-3-319-10587-1_5.