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].
Finite Materialisability of Datalog Programs with Metric Temporal Operators
Authors: Przemysław Wałęga, Michał Zawidzki, Bernardo Cuenca Grau
JAIR 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose and study finitely materialisable Datalog MTL programs, for which forward chaining reasoning is guaranteed to terminate. We consider a data-dependent notion of finite materialisability of a program... We show that, for bounded programs... checking data-dependent finite materialisability is Exp Space-complete... We show that checking data-independent finite materialisability for bounded progams is computationally easier, namely Exp Time-complete; moreover, we propose sufficient conditions for data-indenpendent finite materialisability that can be efficiently checked. We provide also the complexity landscape of fact entailment for different classes of finitely materialisable programs... |
| Researcher Affiliation | Academia | Przemysław Andrzej Wałęga EMAIL Michał Zawidzki EMAIL Bernardo Cuenca Grau EMAIL Department of Computer Science University of Oxford Parks Rd, Oxford, OX1 3QD, UK |
| Pseudocode | Yes | Algorithm 1: Apply Rules; Procedure 2: Materialisation-based reasoning; Algorithm 3: Checking finite materialisability for a single dataset; Algorithm 4: Checking finite materialisability for all bounded datasets |
| Open Source Code | No | In our recent work (Wang et al., 2022), we proposed a practical reasoning algorithm for Datalog MTL combining a materialisation-based procedure optimised for efficient rule application with the construction of Büchi automata to ensure completeness and termination. We implemented this approach in the Me Teo R reasoner, which is designed to minimise the use of automata-based techniques in favour of materialisation. The paper does not state that the code for the current paper's contributions is open-source. |
| Open Datasets | No | Example 1. There is growing evidence that individuals develop COVID-19 immunity for at least 3 months if they got vaccinated and remained without symptoms (or displayed a negative test result) within 3 to 4 weeks following vaccination, or if they were infected within the last 6 months (discounting the last ten days when they had no symptoms) (Feikin et al., 2022). Furthermore, individuals with immunity for at least 5 days display a negative test result. These conditions can be captured by a Datalog MTL program Πex with the rules: ... Assume also that historical data is stored in the form of facts stamped with validity intervals... Ben got vaccinated at 4 p.m. on July 19 (represented as 199 2/3). Moreover, Ben had no symptoms since midnight on July 1 (i.e., 181) until noon on August 30 (i.e., 242 1/2). The paper uses illustrative examples with synthetic data, not open datasets for empirical evaluation. The citation is for background information, not a dataset. |
| Dataset Splits | No | The paper does not describe any experimental setup involving data splits. It is a theoretical paper. |
| Hardware Specification | No | The paper does not provide specific hardware details for experimental runs, as it is a theoretical paper. |
| Software Dependencies | No | The paper discusses various software systems and languages in the context of related work (e.g., 'Me Teo R reasoner', 'Ontop platform', 'Telingo system', 'LARS', 'Datalog'), but it does not specify versions of any ancillary software dependencies required to reproduce the theoretical results or any implied practical procedures of this paper. |
| Experiment Setup | No | The paper is theoretical and does not contain details about experimental setup, hyperparameters, or training configurations. |