Reverse Engineering of Temporal Queries Mediated by LTL Ontologies
Authors: Marie Fortin, Boris Konev, Vladislav Ryzhikov, Yury Savateev, Frank Wolter, Michael Zakharyaschev
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we investigate temporal queryby-example by focusing on the basic but very useful case where data D is a set of timestamped atomic propositions. Our query languages are positive fragments of linear temporal logic LTL with the temporal operators (eventually), (next), and U (until) interpreted under the strict semantics [Demri et al., 2016].We take the first steps towards understanding the complexity and especially feasibility of the queryby-example problems QBE(L, Q) with L an ontology and Q a query language. We are particularly interested in whether there is a difference in complexity between path and branching queries and whether it can be reduced by bounding the number of positive or negative examples. Our results in the ontology-free case are summarised in Table 1Our proof techniques range from reductions to common subsequence existence problems [Maier, 1978; Fraser, 1996] and dynamic programming to mimicking separability by path and branching U-queries in terms of containment and simulation of transition systems [Kupferman and Vardi, 1996]. |
| Researcher Affiliation | Academia | Marie Fortin1 , Boris Konev2 , Vladislav Ryzhikov3 , Yury Savateev4 , Frank Wolter2 and Michael Zakharyaschev3 1Universit e Paris Cit e, CNRS, IRIF, France 2Department of Computer Science, University of Liverpool, UK 3Department of Computer Science and Information Systems, Birkbeck, University of London, UK 4School of Electronics and Computer Science, University of Southampton, UK |
| Pseudocode | No | No structured pseudocode or algorithm blocks were found. |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., a specific repository link, explicit release statement, or mention in supplementary materials) for source code related to the described methodology. |
| Open Datasets | No | The paper presents theoretical work and does not describe experiments that use publicly available datasets for training. The examples provided (e.g., D+1, D+2) are illustrative, not datasets for empirical evaluation. |
| Dataset Splits | No | The paper describes theoretical research and does not provide specific dataset split information (percentages, counts, or methodology) for validation. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., GPU/CPU models, memory, or cloud resources) used for running experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers (e.g., library or solver names with version numbers) needed to replicate the theoretical analysis. |
| Experiment Setup | No | The paper focuses on theoretical analysis and does not describe an experimental setup with concrete hyperparameter values, training configurations, or system-level settings. |