TLDR: A new study links temporal description logic (T EL⃝) fragments to formal grammars, revealing that query answering in full T EL⃝ is undecidable, but becomes polynomial-time for its “future-only” fragment and has low complexity for its “linear” fragment, leveraging existing grammar tools.
In the realm of artificial intelligence and data management, making sense of vast amounts of information is a constant challenge. One powerful approach is Ontology-Mediated Query Answering (OMQA), which enhances data access by enriching raw data with an ‘ontology’ – a structured representation of domain knowledge. This allows users to ask more sophisticated questions and get more complete answers, not just from explicit facts but also from logical deductions.
However, many real-world scenarios involve data that changes over time. Think of medical records, financial transactions, or even a person’s career progression. Integrating this ‘temporal’ aspect into OMQA has been a significant area of research. This is where T EL⃝ comes in, a temporal extension of a popular description logic called EL. In T EL⃝, data facts are tagged with timestamps, and the knowledge base can include temporal operators, such as ‘next’ (⃝) or ‘previous’ (⃝−), allowing for statements like ‘a professor in one year is also a professor the next year’.
A key question in this field has been the ‘decidability’ of query answering – whether an algorithm can always determine if a query has an answer in a finite amount of time. While EL and Linear Temporal Logic (LTL) (the temporal logic component) are individually decidable, their combination in T EL⃝ quickly leads to complex challenges. Previous work had left open the question of whether a restricted version of T EL⃝, specifically T EL⃝, which only uses the ‘next’ operator, could regain decidability. This question was tied to a property called ‘ultimate periodicity’ of models, which essentially means that the evolution of data over time eventually becomes predictable and repetitive.
A groundbreaking new research paper, titled Analysing Temporal Reasoning in Description Logics Using Formal Grammars, by Camille Bourgaux, Anton Gnatenko, and Michaël Thomazo, provides a definitive answer to this long-standing question. Their main contribution is establishing a novel and surprising correspondence between fragments of T EL⃝ and specific types of formal grammars, particularly ‘conjunctive grammars’ (which are an extension of context-free grammars that include an intersection operation).
Unveiling Undecidability and New Decidability
This connection has profound implications. For the full T EL⃝ language, the study shows that it does not possess the property of ultimate periodicity. More importantly, it leads to the conclusion that query answering in T EL⃝ is, in fact, undecidable. This closes the question left open by previous research, confirming that even with just the ‘next’ operator, the full language is too complex for general algorithmic solutions.
However, the research also brings positive news for specific fragments of T EL⃝. They introduce T EL⃝future, a fragment where concept inclusions only allow deriving information about the present or future (no ‘previous’ operator). For this fragment, the paper demonstrates that reasoning can be reduced to analyzing unary conjunctive languages. This reduction surprisingly shows that atomic query answering in T EL⃝future is solvable in polynomial time, a significant improvement from undecidability. This means that for future-oriented temporal queries, efficient algorithms are possible.
Another fragment, T EL⃝lin, which restricts the types of logical rules allowed, is shown to correspond to context-free grammars. This connection proves that T EL⃝lin-TBoxes *do* enjoy the property of ultimate periodicity, and query answering in this fragment has a considerably lower data complexity, making it more tractable for large datasets.
Also Read:
- Maintaining RDF Graph Integrity Through Proactive SHACL Validation
- Navigating the Mathematical Landscape: LLMs in Formal and Informal Reasoning
Leveraging Formal Language Tools
The beauty of this correspondence lies in its practical utility. By linking temporal reasoning in description logics to formal grammars, the researchers open the door to reusing existing tools and algorithms developed for formal language theory. For instance, parsing algorithms for conjunctive grammars can now be adapted and applied to solve query answering problems in T EL⃝future. This cross-disciplinary approach can accelerate the development of more efficient and practical reasoners for temporal knowledge bases.
This work not only settles a fundamental question about the decidability of T EL⃝ but also provides a roadmap for future research. It suggests that similar connections might exist between more expressive temporal description logics and other general classes of formal grammars. Ultimately, this research paves the way for developing more robust and practical systems for managing and querying temporal data in complex knowledge-based applications.
