mlsanityData to 14 Oct 2026

Analysing Temporal Reasoning in Description Logics Using Formal Grammars

arXiv 2508.00575 ↗First posted 1 Aug 2025cs.LO cs.AIcited by 0

On the map: LLM reasoning → Knowledge- and tool-augmented reasoning

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.

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.

Builds on

5 of 55 references.

References · 5

  1. 2014The DL-Lite Family and Relationscited by 20
  2. 2017Querying Log Data with Metric Temporal Logic (Technical Report)cited by 10
  3. 2022MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operatorscited by 7
  4. 2021First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queriescited by 4
  5. 2025On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)cited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025On Syntactical Simplification of Temporal Operators in Negation-free MTL
  2. 2023Unlocking Temporal Question Answering for Large Language Models with Tailor-Made Reasoning Logic
  3. 2025T-CPDL: A Temporal Causal Probabilistic Description Logic for Developing Logic-RAG Agent
  4. 2026Applications of Intuitionistic Temporal Logic to Temporal Answer Set Programming
  5. 2024Transformer-based Language Models for Reasoning in the Description Logic ALCQ
  6. 2024LTLBench: Towards Benchmarks for Evaluating Temporal Reasoning in Large Language Models
  7. 2022Time and G"odel: Fuzzy temporal reasoning in PSPACE
  8. 2025Towards Constraint Temporal Answer Set Programming