Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies

Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies

Maurice Funk, Jean Christoph Jung, Carsten Lutz

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 2627-2633. https://doi.org/10.24963/ijcai.2022/364

We study ELI queries (ELIQs) in the presence of ontologies formulated in the description logic DL-Lite. For the dialect DL-LiteH, we show that ELIQs have a frontier (set of least general generalizations) that is of polynomial size and can be computed in polynomial time. In the dialect DL-LiteF, in contrast, frontiers may be infinite. We identify a natural syntactic restriction that enables the same positive results as for DL-LiteH. We use our results on frontiers to show that ELIQs are learnable in polynomial time in the presence of a DL-LiteH / restricted DL-LiteF ontology in Angluin's framework of exact learning with only membership queries.
Keywords:
Knowledge Representation and Reasoning: Description Logics and Ontologies