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

CREATORMaurice Funk, Jean Christoph Jung, Tom Voellmer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-21752

Browse the full library ยท About the Tower of Babel