Analysing Temporal Reasoning in Description Logics Using Formal Grammars

• URL: http://arxiv.org/abs/2508.00575v1
• Date: Fri, 01 Aug 2025 12:17:49 GMT
• Title: Analysing Temporal Reasoning in Description Logics Using Formal Grammars
• Authors: Camille Bourgaux, Anton Gnatenko, Michaël Thomazo,
• Abstract summary: We establish a correspondence between (fragments of) $mathcalTELbigcirc$, a temporal extension of the $mathcalEL$ description logic with the operator $bigcirck$.<n>This connection implies that $mathcalTELbigcirc$ does not possess the property of ultimate periodicity of models, and leads to undecidability of query answering in $mathcalTELbigcirc$.<n>It also allows to establish decidability of query answering for some new interesting fragments of $mathcalTELbigcirc$
• Score: 4.85429787471051
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Language Models May Verbatim Complete Text They Were Not Explicitly Trained On [97.3414396208613]
  We show that a $n$-gram based membership definition can be effectively gamed.<n>We show that it is difficult to find a single viable choice of $n$ for membership definitions.<n>Our findings highlight the inadequacy of $n$-gram membership, suggesting membership definitions fail to account for auxiliary information.
  arXiv  Detail & Related papers  (2025-03-21T19:57:04Z)
• Spectra of Cardinality Queries over Description Logic Knowledge Bases [1.9336815376402723]
  We identify a class of counting queries whose spectra can be effectively represented.<n>We refine constructions used for finite model reasoning and rely on a cycle-reversion technique for the Horn fragment.
  arXiv  Detail & Related papers  (2024-12-17T14:07:04Z)
• FLARE: Faithful Logic-Aided Reasoning and Exploration [50.9814063216852]
  We introduce a novel approach for traversing the problem space using task decompositions.<n>We use the Large Language Models to plan a solution, soft-formalise the query into facts and predicates using a logic programming code.<n>Our method allows us to compute the faithfulness of the reasoning process w.r.t. the generated code and analyse the steps of the multi-hop search without relying on external solvers.
  arXiv  Detail & Related papers  (2024-10-14T19:39:11Z)
• Temporal Ensemble Logic [2.71467552808655]
  We introduce Temporal Ensemble Logic (TEL), a monadic, first-order modal logic for linear-time temporal reasoning. TEL has been motivated from the requirement for rigor and for cohort specification and discovery in clinical and population health research. We present its formal semantics, a proof system, and provide a proof for the satisfiability of the satisfiability of $rm TEL_mathbbN+$.
  arXiv  Detail & Related papers  (2024-08-26T17:36:25Z)
• Efficient Semiring-Weighted Earley Parsing [71.77514972816347]
  This paper provides a reference description, in the form of a deduction system, of Earley's (1970) context-free parsing algorithm with various speed-ups. Our presentation includes a known worst-case runtime improvement from Earley's $O (N3|GR|)$, which is unworkable for the large grammars that arise in natural language processing. We treat the generalization to semiring-weighted deduction, preprocessing the grammar like Stolcke (1995) to eliminate deduction cycles, and further generalize Stolcke's method to compute the weights of sentence prefixes.
  arXiv  Detail & Related papers  (2023-07-06T13:33:59Z)
• Reasoning in the Description Logic ALC under Category Semantics [0.0]
  We present a reformulation of the usual set-theoretical semantics of the description logic $mathcalALC$ with general TBoxes by using categorical language. In this setting, $mathcalALC$ concepts are represented as objects, concept subsumptions as arrows, and memberships as logical quantifiers over objects and arrows of categories.
  arXiv  Detail & Related papers  (2022-05-10T14:03:44Z)
• Efficient TBox Reasoning with Value Restrictions using the $\mathcal{FL}_{o}$wer reasoner [8.977167559181982]
  $mathcalFL_o$wer can deal with written in the extension $mathcalFL_bot$ of $mathcalFLFL$ with the top and the bottom concept. $mathcalFL_o$wer can also deal with written in the extension $mathcalFL_bot$ of $mathcalFLFL$ with the top and the bottom concept.
  arXiv  Detail & Related papers  (2021-07-27T15:20:53Z)
• Proof-theoretic aspects of NL$\lambda$ [0.0]
  We present a proof-theoretic analysis of the logic NL$lambda$. We introduce a novel calculus of proof nets and prove it is sound and complete with respect to the sequent calculus for the logic. We show there is an unexpected convergence of the natural language analyses proposed in the two formalisms.
  arXiv  Detail & Related papers  (2020-10-23T08:13:39Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso bandit is an algorithm that estimates the vector defining the reward function as well as its sparse support. We establish non-asymptotic regret upper bounds scaling as $mathcalO( log d + sqrtT )$ in general, and as $mathcalO( log d + sqrtT )$ under the so-called margin condition.
  arXiv  Detail & Related papers  (2020-10-22T19:14:37Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)
• Intuitionistic Linear Temporal Logics [0.7087237546722617]
  We consider intuitionistic variants of linear temporal logic with next', until' and release' We prove that $iltl$ has the effective finite model property and hence is decidable, while $itlb$ does not have the finite model property. We also introduce notions of bounded bisimulations for these logics and use them to show that the until' and release' operators are not definable in terms of each other, even over the class of persistent posets.
  arXiv  Detail & Related papers  (2019-12-30T11:49:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.