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

2022/04/29 by Funk, Maurice, Jung, Jean Christoph, Lutz, Carsten
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2204.14172

Abstract

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 out 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.

Related

• Exact Learning of Lightweight Description Logic Ontologies
• Actively Learning Concepts and Conjunctive Queries under ELr-Ontologies
• Learning Ontologies with Epistemic Reasoning: The EL Case
• A Complete Classification of the Complexity and Rewritability of Ontology-Mediated Queries based on the Description Logic EL
• The Expressive Power of DL-Lite