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

Bourgaux, Camille; Gnatenko, Anton; Thomazo, Michael

doi:10.24963/ijcai.2026/918

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

Camille Bourgaux, Anton Gnatenko, Michaël Thomazo

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Sister Conferences Best Papers. Pages 8232-8236.

https://doi.org/10.24963/ijcai.2026/918

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

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.

Camille Bourgaux, Anton Gnatenko, and Michael Thomazo. 2026. Analysing Temporal Reasoning in Description Logics Using Formal Grammars (IJCAI Extended Abstract). In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 8232–8236. https://doi.org/10.24963/ijcai.2026/918

@inproceedings{ijcai2026p918,
  title     = {Analysing Temporal Reasoning in Description Logics Using Formal Grammars (IJCAI Extended Abstract)},
  author    = {Bourgaux, Camille and Gnatenko, Anton and Thomazo, Michael},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {8232--8236},
  year      = {2026},
  month     = {8},
  note      = {Sister Conferences Best Papers},
  doi       = {10.24963/ijcai.2026/918},
  url       = {https://doi.org/10.24963/ijcai.2026/918},
}

TY  - CPAPER
TI  - Analysing Temporal Reasoning in Description Logics Using Formal Grammars (IJCAI Extended Abstract)
AU  - Bourgaux, Camille
AU  - Gnatenko, Anton
AU  - Thomazo, Michael
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 8232
EP  - 8236
DO  - 10.24963/ijcai.2026/918
UR  - https://doi.org/10.24963/ijcai.2026/918
ER  -