---
title: "Analysing Temporal Reasoning in Description Logics Using Formal Grammars (IJCAI Extended Abstract)"
authors:
  - "Camille Bourgaux"
  - "Anton Gnatenko"
  - "Michaël Thomazo"
doi: "10.24963/ijcai.2026/918"
url: "https://ijcai.org/proceedings/2026/918"
pdf: "https://ijcai.org/proceedings/2026/0918.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "8232-8236"
track: "Sister Conferences Best Papers"
keywords:
  - "Knowledge Representation and Reasoning: Description logics and ontologies"
  - "Knowledge Representation and Reasoning: Qualitative, geometric, spatial, and temporal reasoning"
  - "Knowledge Representation and Reasoning: Computational complexity of reasoning"
---

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

Camille Bourgaux, Anton Gnatenko, Michaël Thomazo

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 8232-8236. DOI: [10.24963/ijcai.2026/918](https://doi.org/10.24963/ijcai.2026/918)

## Abstract

We establish a correspondence between (fragments of) TEL^o, a temporal extension of the EL description logic with the LTL operator O^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^o does not possess the property of ultimate periodicity of models, and further leads to undecidability of query answering in TEL^o, closing a question left open since the introduction of TEL^o. Moreover, it also allows to establish decidability of query answering for some new interesting fragments of TEL^o, and to reuse for this purpose existing tools and algorithms for conjunctive grammars.