KR2022Proceedings of the 19th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning

Haifa, Israel. July 31–August 5, 2022.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-01-0

Sponsored by
Published by

Copyright © 2022 International Joint Conferences on Artificial Intelligence Organization

Unique Characterisability and Learnability of Temporal Instance Queries

  1. Marie Fortin(University of Liverpool)
  2. Boris Konev(University of Liverpool)
  3. Vladislav Ryzhikov(Birkbeck, University of London)
  4. Yury Savateev(Birkbeck, University of London)
  5. Frank Wolter(University of Liverpool)
  6. Michael Zakharyaschev(Birkbeck, University of London)


  1. Learning spatial and temporal theories
  2. Geometric, spatial, and temporal reasoning
  3. Explanation finding, diagnosis, causal reasoning, abduction
  4. Description logics


We aim 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) or extensions thereof induced by the until operator. Not all of these queries admit polynomial characterisations, but by imposing a further restriction 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.