SAT-Based Bounded Fitting for the Description Logic ๐ โ โ โ ๐ \mathcal{ALC}
Maurice Funk, Jean Christoph Jung, Tom Voellmer ยท 2025
Read SAT-Based Bounded Fitting for the Description Logic ๐ โ โ โ ๐ \mathcal{ALC} by Maurice Funk, Jean Christoph Jung, Tom Voellmer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21752.txt.
Description
Maurice Funk and co-authors study learning logic formulas from examples in this 2025 paper. The setting is a description logic called ALC, used to write knowledge bases. Bounded fitting asks for a formula of capped size that accepts the positive examples and rejects the negative ones.
The authors prove the search is NP-complete for every fragment they study, even with just one example of each kind. That hardness still allows learning guarantees that rival methods for the same logic cannot offer. They build a working tool on top of a SAT solver, tune it, and compare it with other concept learners. The results map where guaranteed learning is practical for knowledge engineers.
Catalog record
| CREATOR | Maurice Funk, Jean Christoph Jung, Tom Voellmer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-21752