# Analysing Temporal Reasoning in Description Logics Using Formal Grammars

arXiv: https://arxiv.org/abs/2508.00575 · HTML: https://mlsanity.com/paper/2508.00575/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 5 of its 55 references that are in the map.
- First posted on arXiv 1 Aug 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 5 of 5)

- [The DL-Lite Family and Relations](https://mlsanity.com/paper/1401.3487/) (2014)
- [Querying Log Data with Metric Temporal Logic (Technical Report)](https://mlsanity.com/paper/1703.08982/) (2017)
- [MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators](https://mlsanity.com/paper/2201.04596/) (2022)
- [First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries](https://mlsanity.com/paper/2111.06806/) (2021)
- [On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)](https://mlsanity.com/paper/2501.13762/) (2025)

## Abstract (arXiv)

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