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

arXiv: https://arxiv.org/abs/2204.14172 · HTML: https://mlsanity.com/paper/2204.14172/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 44 references that are in the map.
- First posted on arXiv 29 Apr 2022.

## Builds on (most cited first, 6 of 6)

- [The DL-Lite Family and Relations](https://mlsanity.com/paper/1401.3487/) (2014)
- [Efficient Concept Induction for Description Logics](https://mlsanity.com/paper/1812.03243/) (2018)
- [Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP](https://mlsanity.com/paper/1301.6479/) (2013)
- [Learning Description Logic Ontologies. Five Approaches. Where Do They Stand?](https://mlsanity.com/paper/2104.01193/) (2021)
- [Exact Learning of Lightweight Description Logic Ontologies](https://mlsanity.com/paper/1709.07314/) (2017)
- [Conjunctive Queries: Unique Characterizations and Exact Learnability](https://mlsanity.com/paper/2008.06824/) (2020)

## Built on by (most cited first, 3 of 3)

- [SAT-Based PAC Learning of Description Logic Concepts](https://mlsanity.com/paper/2305.08511/) (2023)
- [On the Power and Limitations of Examples for Description Logic Concepts](https://mlsanity.com/paper/2412.17345/) (2024)
- [Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology](https://mlsanity.com/paper/2306.07662/) (2023)

## Abstract (arXiv)

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.