# Learning Query Inseparable ELH Ontologies

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2019.

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

- [Actively Learning Concepts and Conjunctive Queries under ELr-Ontologies](https://mlsanity.com/paper/2105.08326/) (2021)

## Abstract (arXiv)

We investigate the complexity of learning query inseparable ELH ontologies in a variant of Angluin's exact learning model. Given a fixed data instance A* and a query language Q, we are interested in computing an ontology H that entails the same queries as a target ontology T on A*, that is, H and T are inseparable w.r.t. A* and Q. The learner is allowed to pose two kinds of questions. The first is `Does (T,A)models q?', with A an arbitrary data instance and q and query in Q. An oracle replies this question with `yes' or `no'. In the second, the learner asks `Are H and T inseparable w.r.t. A* and Q?'. If so, the learning process finishes, otherwise, the learner receives (A*,q) with q in Q, (T,A*)models q and (H,A*)notmodels q (or vice-versa). Then, we analyse conditions in which query inseparability is preserved if A* changes. Finally, we consider the PAC learning model and a setting where the algorithms learn from a batch of classified data, limiting interactions with the oracles.