Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries
Authors: Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev
JAIR 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main concern is first-order rewritability of ontology-mediated queries (OMQs) that consist of a 2D ontology and a positive temporal instance query. Our target languages for FO-rewritings are two-sorted FO(<) first-order logic with sorts for time instants ordered by the built-in precedence relation < and for the domain of individuals – its extension FO(<, ) with the standard congruence predicates t 0 (mod n), for any fixed n > 1, and FO(RPR) that admits relational primitive recursion. In terms of circuit complexity, FO(<, ) and FO(RPR) rewritability guarantee answering OMQs in uniform AC0 and NC1, respectively. We proceed in three steps. First, we define a hierarchy of 2D DL-Lite/LTL ontology languages and investigate the FO-rewritability of OMQs with atomic queries by constructing projections onto 1D LTL OMQs and employing recent results on the FO-rewritability of propositional LTL OMQs. As the projections involve deciding consistency of ontologies and data, we also consider the consistency problem for our languages. While the undecidability of consistency for 2D ontology languages with expressive Boolean role inclusions might be expected, we also show that, rather surprisingly, the restriction to Krom and Horn role inclusions leads to decidability (and Exp Space-completeness), even if one admits full Booleans on concepts. As a final step, we lift some of the rewritability results for atomic OMQs to OMQs with expressive positive temporal instance queries. The lifting results are based on an in-depth study of the canonical models and only concern Horn ontologies. |
| Researcher Affiliation | Academia | Alessandro Artale EMAIL Free University of Bozen-Bolzano, Italy; Roman Kontchakov EMAIL Birkbeck, University of London, UK; Alisa Kovtunova EMAIL Technische Universit at Dresden, Germany; Vladislav Ryzhikov EMAIL Birkbeck, University of London, UK; Frank Wolter EMAIL University of Liverpool, UK; Michael Zakharyaschev EMAIL Birkbeck, University of London, UK HSE University, Moscow, Russia |
| Pseudocode | No | The paper describes methods through logical rules and definitions, such as those found in Section 6.1 'Canonical Models', which outline inference steps (e.g., '(mp) if O contains ϑ1 ϑm ϑ and ϑi(w, n) Λ for all i, 1 i m, then we add ϑ(w, n) to Λ;'). These are descriptions of logical systems and their properties, rather than structured pseudocode or algorithm blocks for computational procedures. |
| Open Source Code | No | The paper makes no explicit statement about providing source code or links to a code repository for the methodology described. It discusses target languages for rewritings, such as 'FO(RPR)-queries can be expressed in SQL with recursion or procedural extensions', but does not offer its own implementation code. |
| Open Datasets | No | The paper introduces a motivating example using 'a database on the submission and publication of papers' but does not specify, use, or provide access information for any actual dataset in its theoretical analysis. It refers to 'ABoxes' as abstract data instances. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on specific datasets, therefore, there is no information provided about training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or execution, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on logical systems and complexity analysis. It mentions 'description logics DLs' and 'linear temporal logic LTL' as frameworks, but does not specify any software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | The paper is theoretical and does not conduct experiments. Consequently, no specific experimental setup details, such as hyperparameter values or training configurations, are provided. |