Unique Characterisability and Learnability of Temporal Instance Queries

Marie Fortin, Boris Konev, Vladislav Ryzhikov, Yury Savateev, Frank Wolter, Michael Zakharyaschev

Research output: Contribution to conferencePaperpeer-review

Abstract

Weaim to determine which temporal instance queries can be uniquely characterised by a (polynomial-size) set of positive and negative temporal data examples. We start by considering queries formulated in fragments of propositional linear temporal logic LTL that correspond to conjunctive queries (CQs)orextensions thereof induced by the until operator. Not all of these queries admit polynomial characterisations but by restricting them further to path-shaped queries we identify natural classes that do. We then investigate how far the obtained characterisations can be lifted to temporal knowledge graphs queried by 2D languages combining LTL with concepts in description logics EL or ELI (i.e., tree-shaped CQs). While temporal operators in the scope of description logic constructors can destroy polynomial characterisability, we obtain general transfer results for the case when description logic constructors are within the scope of temporal operators. Finally, we apply our characterisations to establish (polynomial) learnability of temporal instance queries using membership queries in the active learning framework.
Original languageEnglish
Publication statusPublished - 2022
Event19th International Conference on Principles of Knowledge Representation and Reasoning - Haifa, Israel
Duration: 31 Jul 20225 Aug 2022
Conference number: 19
https://kr2022.cs.tu-dortmund.de/

Conference

Conference19th International Conference on Principles of Knowledge Representation and Reasoning
Abbreviated titleKR 2022
Country/TerritoryIsrael
CityHaifa
Period31/07/225/08/22
Internet address

Fingerprint

Dive into the research topics of 'Unique Characterisability and Learnability of Temporal Instance Queries'. Together they form a unique fingerprint.

Cite this