arxiv: 2605.07452 · v1 · submitted 2026-05-08 · 💻 cs.AI

Recognition: no theorem link

Bounded Fitting for Expressive Description Logics

Maurice Funk , Jean Christoph Jung , Tom Voellmer

Authors on Pith no claims yet

Pith reviewed 2026-05-11 01:59 UTC · model grok-4.3

classification 💻 cs.AI

keywords bounded fittingdescription logicsconcept learningPAC guaranteesSAT solverinverse rolesqualified number restrictionsfeature comparisons

0 comments

The pith

Bounded fitting extends to expressive description logics with inverse roles, qualified number restrictions, and feature comparisons while retaining PAC-style guarantees under identified conditions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Bounded fitting learns logical concepts from labeled examples by searching for a formula of bounded size that correctly classifies the data. It provides PAC-style generalization bounds and reduces to a SAT problem for practical computation. The paper shows this paradigm carries over from basic ALC to richer description logics that add inverses, number restrictions, and feature comparisons. It identifies the conditions needed to preserve the theoretical guarantees and supplies a working SAT-based implementation. Experiments indicate the resulting tool competes with existing concept learners on standard benchmarks.

Core claim

Bounded fitting remains a viable approach for concept learning in description logics that extend ALC with inverse roles, qualified number restrictions, and feature comparisons. Under suitable conditions on the logic and the data, the approach retains its PAC-style generalization guarantees and admits an efficient reduction to SAT solving. A concrete SAT-based prototype learns concepts in these richer logics and produces competitive results when compared with state-of-the-art concept learners.

What carries the argument

Bounded fitting, the task of finding a description-logic concept of bounded size that separates given positive and negative examples, encoded as a SAT instance.

If this is right

Concept learning in expressive description logics can be performed by reducing to SAT rather than by custom search procedures.
The PAC-style sample-complexity bounds derived for ALC transfer to the extended logics once the identified conditions hold.
A single SAT encoding suffices to handle multiple constructors without separate case analysis for each extension.
Empirical performance remains comparable to specialized learners when the bounded-size restriction is chosen appropriately.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same bounded-fitting reduction might be adapted to other non-monotonic or probabilistic description logics by adjusting the SAT encoding.
If the identified conditions turn out to be mild in practice, bounded fitting could serve as a uniform backend for ontology-refinement tools that must handle rich constructors.
Scalability limits would be determined by the growth of the SAT encoding with the bound rather than by the number of constructors in the logic.

Load-bearing premise

Practical conditions exist under which the PAC-style guarantees and the SAT reduction stay effective after adding inverses, qualified number restrictions, and feature comparisons.

What would settle it

A family of learning problems in a logic with inverses or number restrictions for which every bounded-size fitting concept fails to generalize on unseen data or for which the corresponding SAT instances become intractable for realistic example sizes.

Figures

Figures reproduced from arXiv: 2605.07452 by Jean Christoph Jung, Maurice Funk, Tom Voellmer.

**Figure 2.** Figure 2: Example database I used in the reduction. The A-facts mark the end of the paths: A(an) and A(bj,n), for all j ∈ m. The r-facts can be grouped as follows: • r(a, a0), r(a, bj,0), and r(b, bj,0), connect the root elements a, b to the starts of the paths; • r(ai−1, ai) for all i ∈ {1, . . . , n} establish the path along the a-elements; and • r(bj,i−1, bj,i) for all i ∈ {1, . . . , n} and j ∈ {1, . . . , m} e… view at source ↗

read the original abstract

Bounded fitting is an attractive paradigm for learning logical formulas from labeled data examples that offers PAC-style generalization guarantees and can often be implemented leveraging SAT solvers. It has been successfully applied to learning concepts of the description logic ALC. We study bounded fitting for learning concepts in expressive description logics that extend ALC with inverse roles, qualified number restrictions, and feature comparisons. We investigate under which conditions bounded fitting keeps its favorable theoretical properties in this setting, and implement it using a SAT solver. We compare our tool with state-of-the-art concept learners with encouraging results, demonstrating that it is a practical approach to expressive concept learning.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Bounded fitting extends to these expressive DLs under conditions, with a working SAT implementation and positive comparisons.

read the letter

The key takeaway from this paper is that bounded fitting can be extended beyond ALC to description logics with inverse roles, qualified number restrictions, and feature comparisons, as long as certain conditions are met to preserve the PAC guarantees, and they've implemented it with a SAT solver that shows encouraging results in comparisons. What is new here is the extension itself and the specific conditions they identify for keeping the theoretical properties. The SAT implementation is also a step forward from the abstract ALC case. The paper does well in providing both the theoretical analysis and a working tool. Running comparisons against state-of-the-art concept learners adds practical value and shows it's feasible. Soft spots are minor but worth noting. The conditions for preserving the guarantees might restrict applicability in some real scenarios, and the empirical evaluation could benefit from more details on scalability or diverse datasets. However, nothing looks like a load-bearing flaw. This paper is for people in knowledge representation and AI who work on learning concepts from data in expressive logics. It would be useful for those looking for alternatives to existing learners. It deserves serious peer review because the combination of theory, implementation, and experiments is substantive. Recommendation: Engage with it; the work is worth refereeing.

Referee Report

0 major / 3 minor

Summary. The paper extends the bounded fitting paradigm—previously applied to ALC—to more expressive description logics that include inverse roles, qualified number restrictions, and feature comparisons. It investigates conditions under which the approach retains its PAC-style generalization guarantees, develops a SAT-solver-based implementation for concept learning from labeled examples, and reports empirical comparisons against state-of-the-art concept learners that yield encouraging results.

Significance. If the claimed conditions and implementation correctness hold, the work meaningfully broadens a theoretically grounded learning method to DLs of greater practical relevance in knowledge representation. The explicit focus on preserving PAC guarantees while leveraging SAT encodings, together with reproducible empirical comparisons, strengthens its contribution over purely heuristic concept learners.

minor comments (3)

The abstract and introduction would benefit from a brief, explicit statement of the precise conditions (e.g., on the bound or the signature) under which the PAC guarantees are shown to carry over; this would help readers quickly assess the scope of the theoretical results.
Section 4 (or wherever the SAT encoding is presented) should include a short complexity discussion or reference to the size of the generated formulas when qualified number restrictions and feature comparisons are added, to clarify scalability limits.
The experimental section would be strengthened by reporting the exact parameter settings used for the competing learners and any statistical significance tests on the accuracy differences.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation for minor revision. The assessment accurately reflects our contributions in extending bounded fitting to expressive description logics (with inverse roles, qualified number restrictions, and feature comparisons), the analysis of conditions for retaining PAC-style guarantees, the SAT-solver implementation, and the empirical comparisons.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper extends prior bounded fitting results for ALC to ALC with inverses, qualified number restrictions, and feature comparisons. It investigates conditions under which PAC-style guarantees are retained and provides a SAT encoding plus empirical comparisons. No load-bearing step reduces by construction to a fitted parameter, self-definition, or unverified self-citation chain; the central claims rest on explicit condition investigation and external benchmarking rather than tautological renaming or imported uniqueness.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities; full paper required for assessment.

pith-pipeline@v0.9.0 · 5389 in / 994 out tokens · 29868 ms · 2026-05-11T01:59:56.745346+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

300 extracted references · 300 canonical work pages

[1]

Proc.\ of KR , year =

Marie Fortin and Boris Konev and Vladislav Ryzhikov and Yury Savateev and Frank Wolter and Michael Zakharyaschev , title =. Proc.\ of KR , year =

work page
[2]

Ford, L. R. and Fulkerson, D. R. , year=. Maximal Flow Through a Network , volume=. doi:10.4153/CJM-1956-045-5 , journal=

work page doi:10.4153/cjm-1956-045-5 1956
[3]

Kuhn, H. W. , title =. Naval Research Logistics Quarterly , volume =. doi:https://doi.org/10.1002/nav.3800020109 , Aurl =

work page doi:10.1002/nav.3800020109
[4]

Paths, Trees, and Flowers , volume=

Edmonds, Jack , year=. Paths, Trees, and Flowers , volume=. doi:10.4153/CJM-1965-045-4 , journal=

work page doi:10.4153/cjm-1965-045-4 1965
[5]

Cohen and Haym Hirsh , title =

William W. Cohen and Haym Hirsh , title =. Machine Learning , volume =. 1994 , Aurl =. doi:10.1007/BF00993470 , timestamp =

work page doi:10.1007/bf00993470 1994
[6]

Ozaki, Ana , title=. KI - K. 2020 , Amonth=

work page 2020
[7]

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (

Balder ten Cate and Maurice Funk and Jean Christoph Jung and Carsten Lutz , title =. Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (. 2023 , Aurl =. doi:10.24963/IJCAI.2023/373 , Atimestamp =

work page doi:10.24963/ijcai.2023/373 2023
[8]

Information Processing Letters , volume =

Balder ten Cate and Maurice Funk and Jean Christoph Jung and Carsten Lutz , title =. Information Processing Letters , volume =. 2024 , Aurl =. doi:10.1016/J.IPL.2023.106431 , timestamp =

work page doi:10.1016/j.ipl.2023.106431 2024
[9]

, title =

Pitt, Leonard and Valiant, Leslie G. , title =. J. ACM , pages =. 1988 , publisher =. doi:10.1145/48014.63140 , abstract =

work page doi:10.1145/48014.63140 1988
[10]

, title =

Cook, Stephen A. , title =. Proceedings of the Third Annual ACM Symposium on Theory of Computing , pages =. 1971 , isbn =. doi:10.1145/800157.805047 , Aabstract =

work page doi:10.1145/800157.805047 1971
[11]

Warmuth , Akeywords =

Anselm Blumer and Andrzej Ehrenfeucht and David Haussler and Manfred K. Warmuth , Akeywords =. Occam's Razor , journal =. 1987 , issn =. doi:https://doi.org/10.1016/0020-0190(87)90114-1 , Aurl =

work page doi:10.1016/0020-0190(87)90114-1 1987
[12]

Artificial Intelligence , volume =

Jean Christoph Jung and Carsten Lutz and Hadrien Pulcini and Frank Wolter , title =. Artificial Intelligence , volume =. 2022 , url =. doi:10.1016/J.ARTINT.2022.103785 , timestamp =

work page doi:10.1016/j.artint.2022.103785 2022
[13]

Proceedings of 12th International Joint Conference on Automated Reasoning

Adrien Pommellet and Daniel Stan and Simon Scatton , Aeditor =. Proceedings of 12th International Joint Conference on Automated Reasoning. 2024 , Aurl =. doi:10.1007/978-3-031-63498-7\_22 , timestamp =

work page doi:10.1007/978-3-031-63498-7 2024
[14]

URL https://doi.org/10.1007/978-3-031-65633-0_10

Mojtaba Valizadeh and Nathana. Proceedings of the 36th International Conference on Computer Aided Verification (CAV) , series =. 2024 , Aurl =. doi:10.1007/978-3-031-65633-0\_10 , timestamp =

work page doi:10.1007/978-3-031-65633-0 2024
[15]

Learning temporal formulas from examples is hard , journal =

Corto Mascle and Nathana. Learning temporal formulas from examples is hard , journal =. 2023 , Aurl =. doi:10.48550/ARXIV.2312.16336 , eprinttype =. 2312.16336 , timestamp =

work page doi:10.48550/arxiv.2312.16336 2023
[16]

The Complexity of Learning

Benjamin Bordais and Daniel Neider and Rajarshi Roy , Aeditor =. The Complexity of Learning. Proceedings of 42nd International Symposium on Theoretical Aspects of Computer Science,. 2025 , Aurl =. doi:10.4230/LIPICS.STACS.2025.19 , timestamp =

work page doi:10.4230/lipics.stacs.2025.19 2025
[17]

Applied Intelligence , volume =

Luigi Iannone and Ignazio Palmisano and Nicola Fanizzi , title =. Applied Intelligence , volume =. 2007 , Aurl =. doi:10.1007/S10489-006-0011-5 , timestamp =

work page doi:10.1007/s10489-006-0011-5 2007
[18]

Future Gener

Giuseppe Rizzo and Nicola Fanizzi and Claudia d'Amato , title =. Future Gener. Comput. Syst. , volume =. 2020 , Aurl =. doi:10.1016/J.FUTURE.2020.02.071 , timestamp =

work page doi:10.1016/j.future.2020.02.071 2020
[19]

Forum for Specification and Design Languages (

Heinz Riener , title =. Forum for Specification and Design Languages (. 2019 , Aurl =. doi:10.1109/FDL.2019.8876900 , timestamp =

work page doi:10.1109/fdl.2019.8876900 2019
[20]

Information Systems , volume =

Denis Mayr Lima Martins , title =. Information Systems , volume =. 2019 , Aurl =. doi:10.1016/J.IS.2019.03.002 , timestamp =

work page doi:10.1016/j.is.2019.03.002 2019
[21]

Query by Example , booktitle =

Mosh. Query by Example , booktitle =. 1975 , Aurl =. doi:10.1145/1499949.1500034 , timestamp =

work page doi:10.1145/1499949.1500034 1975
[22]

McIlraith , Aeditor =

Alberto Camacho and Sheila A. McIlraith , Aeditor =. Learning Interpretable Models Expressed in Linear Temporal Logic , booktitle =. 2019 , doi =

work page 2019
[23]

Learning Linear Temporal Properties , booktitle =

Daniel Neider and Ivan Gavran , Aeditor =. Learning Linear Temporal Properties , booktitle =. 2018 , Aurl =. doi:10.23919/FMCAD.2018.8603016 , timestamp =

work page doi:10.23919/fmcad.2018.8603016 2018
[24]

Ian Horrocks and Peter F. Patel. From. Journal of Web Semantics , volume =. 2003 , Aurl =. doi:10.1016/J.WEBSEM.2003.07.001 , timestamp =

work page doi:10.1016/j.websem.2003.07.001 2003
[25]

W3C , howpublished =

work page
[26]

The Even More Irresistible

Ian Horrocks and Oliver Kutz and Ulrike Sattler , editor =. The Even More Irresistible. Proceedings, Tenth International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, June 2-5, 2006 , pages =. 2006 , url =

work page 2006
[27]

Proc.\ of

Boris Konev and Ana Ozaki and Frank Wolter , title =. Proc.\ of. 2016 , aurl =

work page 2016
[28]

Learning schema mappings , journal =

Balder ten Cate and V. Learning schema mappings , journal =. 2013 , aurl =

work page 2013
[29]

Valiant , title =

Leslie G. Valiant , title =. Communications of the ACM , volume =. 1984 , aurl =. doi:10.1145/1968.1972 , timestamp =

work page doi:10.1145/1968.1972 1984
[30]

Michael Frazier and Leonard Pitt , title =. Mach. Learn. , volume =. 1996 , aurl =

work page 1996
[31]

2016 , aurl =

Angela Bonifati and Radu Ciucanu and Slawek Staworko , title =. 2016 , aurl =

work page 2016
[32]

Weiss , title =

Sara Cohen and Yaacov Y. Weiss , title =. 2016 , aurl =

work page 2016
[33]

Cohen and Haym Hirsh , title =

William W. Cohen and Haym Hirsh , title =. Proc.\ of. 1994 , timestamp =

work page 1994
[34]

Dana Angluin and Michael Frazier and Leonard Pitt , title =. Mach. Learn. , volume =. 1992 , aurl =

work page 1992
[35]

Proc.\ of AAAI , pages =

Ana Ozaki and Cosimo Persia and Andrea Mazzullo , title =. Proc.\ of AAAI , pages =. 2020 , acrossref =

work page 2020
[36]

Dana Angluin , title =. Inf. Comput. , volume =. 1987 , aurl =

work page 1987
[37]

Cohen , title =

William W. Cohen , title =. Artificial Intelligence , volume =. doi:https://doi.org/10.1016/0004-3702(94)00034-4

work page doi:10.1016/0004-3702(94)00034-4
[38]

Proc.\ of

Kouichi Hirata , title =. Proc.\ of. 2000 , acrossref =. doi:10.1007/3-540-40992-0\_18 , timestamp =

work page doi:10.1007/3-540-40992-0 2000
[39]

Dana Angluin , title =. Mach. Learn. , volume =. 1987 , aurl =

work page 1987
[40]

J.\ Mach.\ Learn.\ Res

Exact Learning of Lightweight Description Logic Ontologies , AUTHOR =. J.\ Mach.\ Learn.\ Res. , year =

work page
[41]

Weddell , title =

Alexander Borgida and David Toman and Grant E. Weddell , title =. Proc. of. 2016 , Acrossref =

work page 2016
[42]

A general Datalog-based framework for tractable query answering over ontologies , journal =

Andrea Cal. A general Datalog-based framework for tractable query answering over ontologies , journal =. 2012 , Aurl =

work page 2012
[43]

Proc.\ of

Meghyn Bienvenu and Magdalena Ortiz and Mantas Simkus and Guohui Xiao , title =. Proc.\ of. 2013 , Acrossref =

work page 2013
[44]

Magdalena Ortiz , title =. Proc. of. 2019 , aurl =

work page 2019
[45]

Zhan, Q., Fang, R., Panchal, H

Emiel Krahmer and Kees van Deemter , title =. Computational Linguistics , volume =. 2012 , url =. doi:10.1162/COLI\_a\_00088 , timestamp =

work page doi:10.1162/coli 2012
[46]

A Relational Framework for Classifier Engineering , journal =

Benny Kimelfeld and Christopher R. A Relational Framework for Classifier Engineering , journal =. 2018 , url =. doi:10.1145/3268931 , timestamp =

work page doi:10.1145/3268931 2018
[47]

Diaz , title =

Marcelo Arenas and Gonzalo I. Diaz , title =. 2016 , aurl =

work page 2016
[48]

Martin Grohe and Martin Ritzert , title =. Proc. of. 2017 , url =. doi:10.1109/LICS.2017.8005080 , timestamp =

work page doi:10.1109/lics.2017.8005080 2017
[49]

Data-complexity of the two-variable fragment with counting quantifiers , journal =

Ian Pratt. Data-complexity of the two-variable fragment with counting quantifiers , journal =. 2009 , url =. doi:10.1016/j.ic.2009.02.004 , timestamp =

work page doi:10.1016/j.ic.2009.02.004 2009
[50]

Riccardo Rosati , title =. J. Comput. Syst. Sci. , volume =. 2011 , url =. doi:10.1016/j.jcss.2010.04.011 , timestamp =

work page doi:10.1016/j.jcss.2010.04.011 2011
[51]

Chang AND H

C.C. Chang AND H. Jerome Keisler , title =

work page
[52]

On the decision problem for two-variable first-order logic , journal =

Erich Gr. On the decision problem for two-variable first-order logic , journal =. 1997 , url =. doi:10.2307/421196 , timestamp =

work page doi:10.2307/421196 1997
[53]

CoRR , volume =

Maurice Funk and Jean Christoph Jung and Tom Voellmer , title =. CoRR , volume =. 2025 , Aurl =

work page 2025
[54]

2025 , pubstate =

Maurice Funk and Jean Christoph Jung and Tom Voellmer , Booktitle =. 2025 , pubstate =

work page 2025
[55]

2023 , url =

Balder ten Cate and Maurice Funk and Jean Christoph Jung and Carsten Lutz , title =. 2023 , url =. doi:10.1145/3641832.3641834 , timestamp =

work page doi:10.1145/3641832.3641834 2023
[56]

Carsten Lutz , title =. Proc. of. 2008 , Apublisher =

work page 2008
[57]

Maurice Funk , title =

work page
[58]

Pushing the

Franz Baader and Carsten Lutz and Sebastian Brandt , Aeditor =. Pushing the. Proc.\ of. 2008 , Aurl =

work page 2008
[59]

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence

Maurice Funk and Jean Christoph Jung and Carsten Lutz and Hadrien Pulcini and Frank Wolter , title =. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. 2019 , Apublisher =. doi:10.24963/ijcai.2019/233 , pages =

work page doi:10.24963/ijcai.2019/233 2019
[60]

Donini and Simona Colucci and Tommaso Di Noia and Eugenio Di Sciascio , title =

Francesco M. Donini and Simona Colucci and Tommaso Di Noia and Eugenio Di Sciascio , title =. Proc.\ of

work page
[61]

Gordon Plotkin , title =

work page
[62]

Approximating Most Specific Concepts in Description Logics with Existential Restrictions , booktitle =

Ralf K. Approximating Most Specific Concepts in Description Logics with Existential Restrictions , booktitle =. 2001 , doi =

work page 2001
[63]

What's in an Attribute? Consequences for the Least Common Subsumer , journal =

Ralf K. What's in an Attribute? Consequences for the Least Common Subsumer , journal =. 2001 , url =. doi:10.1613/jair.702 , timestamp =

work page doi:10.1613/jair.702 2001
[64]

Bernhard Nebel , title =

work page
[65]

Cohen and Alexander Borgida and Haym Hirsh , title =

William W. Cohen and Alexander Borgida and Haym Hirsh , title =. Proc.\ of. 1992 , timestamp =

work page 1992
[66]

Pushing the

Franz Baader and Sebastian Brandt and Carsten Lutz , booktitle =. Pushing the

work page
[67]

On the computation of common subsumers in description logics , school =

Anni. On the computation of common subsumers in description logics , school =

work page
[68]

Carsten Lutz and Robert Piro and Frank Wolter , title =. Proc. of

work page
[69]

Maurice Funk and Jean Christoph Jung and Carsten Lutz and Hadrien Pulcini and Frank Wolter , title =

work page
[70]

Some Lower Bounds for the Computational Complexity of Inductive Logic Programming , booktitle =

J. Some Lower Bounds for the Computational Complexity of Inductive Logic Programming , booktitle =. doi:10.1007/3-540-56602-3_131 , year =

work page doi:10.1007/3-540-56602-3_131
[71]

Haym Hirsh and Nina Mishra and Leonard Pitt , title =. Artif. Intell. , volume =

work page
[72]

Perspectives on Ontology Learning , Publisher =

Concept Learning , Author =. Perspectives on Ontology Learning , Publisher =. 2014 , Pages =

work page 2014
[73]

Perspectives on Ontology Learning , series =

Jens Lehmann and Johanna V. Perspectives on Ontology Learning , series =

work page
[74]

2007 , crossref =

Franz Baader and Bernhard Ganter and Baris Sertkaya and Ulrike Sattler , title =. 2007 , crossref =

work page 2007
[75]

2006 , url =

Sebastian Rudolph , title =. 2006 , url =

work page 2006
[76]

Nicola Fanizzi and Claudia d'Amato and Floriana Esposito , title =. Proc. of

work page
[77]

Carsten Lutz and Robert Piro and Frank Wolter , title =. Proc. of. 2011 , Apublisher =

work page 2011
[78]

Handbook of Modal Logic , pages=

Model theory of modal logic , author=. Handbook of Modal Logic , pages=. 2007 , publisher=

work page 2007
[79]

Carsten Lutz and Frank Wolter , title =. J. Symb. Comput. , volume =

work page
[80]

Lisi , title =

Francesca A. Lisi , title =. Proc.\ of

work page

Showing first 80 references.