# SAT-Based PAC Learning of Description Logic Concepts

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 52 references that are in the map.
- First posted on arXiv 15 May 2023.

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

- [Conjunctive Queries: Unique Characterizations and Exact Learnability](https://mlsanity.com/paper/2008.06824/) (2020)
- [Extremal Fitting Problems for Conjunctive Queries](https://mlsanity.com/paper/2206.05080/) (2022)
- [Separating Data Examples by Description Logic Concepts with Restricted Signatures](https://mlsanity.com/paper/2107.05285/) (2021)
- [Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies](https://mlsanity.com/paper/2204.14172/) (2022)
- [Model Comparison Games for Horn Description Logics](https://mlsanity.com/paper/1904.06919/) (2019)

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

- [SAT-Based Bounded Fitting for the Description Logic ALC](https://mlsanity.com/paper/2507.21752/) (2025)
- [Fitting Ontologies and Constraints to Relational Structures](https://mlsanity.com/paper/2508.13176/) (2025)
- [Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology](https://mlsanity.com/paper/2306.07662/) (2023)
- [Fitting Horn DL Ontologies to ABox and Query Examples: A Tale of Simulation Quantifiers and Finite Models](https://mlsanity.com/paper/2604.26976/) (2026)
- [Bounded Fitting for Expressive Description Logics](https://mlsanity.com/paper/2605.07452/) (2026)

## Abstract (arXiv)

We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies. A main advantage is that the resulting learning algorithms come with theoretical guarantees regarding their generalization to unseen examples in the sense of PAC learning. We prove that, in contrast, several other natural learning algorithms fail to provide such guarantees. As a further contribution, we present the system SPELL which efficiently implements bounded fitting for the description logic ELHr based on a SAT solver, and compare its performance to a state-of-the-art learner.