{"ID":2887943,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.00575","arxiv_id":"2508.00575","title":"Analysing Temporal Reasoning in Description Logics Using Formal Grammars","abstract":"We establish a correspondence between (fragments of) $\\mathcal{TEL}^\\bigcirc$, a temporal extension of the $\\mathcal{EL}$ description logic with the LTL operator $\\bigcirc^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 $\\mathcal{TEL}^\\bigcirc$ does not possess the property of ultimate periodicity of models, and further leads to undecidability of query answering in $\\mathcal{TEL}^\\bigcirc$, closing a question left open since the introduction of $\\mathcal{TEL}^\\bigcirc$. Moreover, it also allows to establish decidability of query answering for some new interesting fragments of $\\mathcal{TEL}^\\bigcirc$, and to reuse for this purpose existing tools and algorithms for conjunctive grammars.","short_abstract":"We establish a correspondence between (fragments of) $\\mathcal{TEL}^\\bigcirc$, a temporal extension of the $\\mathcal{EL}$ description logic with the LTL operator $\\bigcirc^k$, and some specific kinds of formal grammars, in particular, conjunctive grammars (context-free grammars equipped with the operation of intersecti...","url_abs":"https://arxiv.org/abs/2508.00575","url_pdf":"https://arxiv.org/pdf/2508.00575v1","authors":"[\"Camille Bourgaux\",\"Anton Gnatenko\",\"Michaël Thomazo\"]","published":"2025-08-01T12:17:49Z","proceeding":"cs.LO","tasks":"[\"cs.LO\",\"cs.AI\"]","methods":"[]","has_code":false}