Bounded Fitting for Expressive Description Logics

• URL: http://arxiv.org/abs/2605.07452v1
• Date: Fri, 08 May 2026 08:59:52 GMT
• Title: Bounded Fitting for Expressive Description Logics
• Abstract summary: Bounded fitting is an attractive paradigm for learning logical formulas from labeled data examples.<n>We study bounded fitting for learning concepts in expressive description logics that extend ALC with inverse roles, qualified number restrictions, and feature comparisons.
• Score: 6.136487946258519
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• SALA: Semantic-Aware Logical Alignment for Complex Reasoning in In-Context Learning [61.13104919370034]
  We propose SALA, a Semantic-Aware Logical Alignment framework.<n>Instead of relying on a fixed inventory, SALA automatically learns task-specific reasoning operations.<n>It then embeds these operations into a continuous semantic space and uses dynamic time warping to align the reasoning sequences.
  arXiv  Detail & Related papers  (2026-09-02T09:12:03Z)
• SAT-Based Bounded Fitting for the Description Logic ALC [7.193373053157516]
  We investigate bounded fitting for the description logic ALC and its syntactic fragments.<n>We show that the underlying size-restricted fitting problem is NP-complete for all studied fragments.<n>We present an implementation of bounded fitting in ALC and its fragments based on a SAT solver.
  arXiv  Detail & Related papers  (2025-07-29T12:32:16Z)
• On the Power and Limitations of Examples for Description Logic Concepts [6.776119962781556]
  We investigate the power of labeled examples for describing description-logic concepts.<n>Specifically, we study the existence and efficient computability of finite characterisations.
  arXiv  Detail & Related papers  (2024-12-23T07:17:58Z)
• Learning Rules Explaining Interactive Theorem Proving Tactic Prediction [5.229806149125529]
  We represent the problem as an Inductive Logic Programming (ILP) task. Using the ILP representation we enriched the feature space by encoding additional, computationally expensive properties. We use this enriched feature space to learn rules explaining when a tactic is applicable to a given proof state.
  arXiv  Detail & Related papers  (2024-11-02T09:18:33Z)
• The Foundations of Tokenization: Statistical and Computational Concerns [51.370165245628975]
  Tokenization is a critical step in the NLP pipeline.<n>Despite its recognized importance as a standard representation method in NLP, the theoretical underpinnings of tokenization are not yet fully understood.<n>The present paper contributes to addressing this theoretical gap by proposing a unified formal framework for representing and analyzing tokenizer models.
  arXiv  Detail & Related papers  (2024-07-16T11:12:28Z)
• H-STAR: LLM-driven Hybrid SQL-Text Adaptive Reasoning on Tables [56.73919743039263]
  This paper introduces a novel algorithm that integrates both symbolic and semantic (textual) approaches in a two-stage process to address limitations.<n>Our experiments demonstrate that H-STAR significantly outperforms state-of-the-art methods across three question-answering (QA) and fact-verification datasets.
  arXiv  Detail & Related papers  (2024-06-29T21:24:19Z)
• Constructive Interpolation and Concept-Based Beth Definability for Description Logics via Sequents [0.0]
  We introduce a constructive method for establishing the concept-based Beth definability property (CBP) based on sequent systems. Using the highly expressive DL RIQ as a case study, we show how certain interpolants can be computed from sequent calculus. This is the first sequent-based approach to computing interpolants and definitions within the context of description logics.
  arXiv  Detail & Related papers  (2024-04-24T12:28:27Z)
• An Encoding of Abstract Dialectical Frameworks into Higher-Order Logic [57.24311218570012]
  This approach allows for the computer-assisted analysis of abstract dialectical frameworks. Exemplary applications include the formal analysis and verification of meta-theoretical properties.
  arXiv  Detail & Related papers  (2023-12-08T09:32:26Z)
• SAT-Based PAC Learning of Description Logic Concepts [18.851061569487616]
  We propose bounded fitting as a scheme for learning logic concepts in the presence of description. We present the system SPELL which implements bounded fitting for the description logic $mathcalELHr$ based on a SAT solver, and compare its performance to a state-of-the-art learner.
  arXiv  Detail & Related papers  (2023-05-15T10:20:31Z)
• Linear Spaces of Meanings: Compositional Structures in Vision-Language Models [110.00434385712786]
  We investigate compositional structures in data embeddings from pre-trained vision-language models (VLMs) We first present a framework for understanding compositional structures from a geometric perspective. We then explain what these structures entail probabilistically in the case of VLM embeddings, providing intuitions for why they arise in practice.
  arXiv  Detail & Related papers  (2023-02-28T08:11:56Z)
• Evaluating Step-by-Step Reasoning through Symbolic Verification [20.156768135017007]
  Pre-trained language models (LMs) have shown remarkable reasoning performance for in-context learning. LMLP enjoys more than $25%$ higher accuracy than chain-of-thoughts (CoT) on length generalization benchmarks even with smaller model sizes.
  arXiv  Detail & Related papers  (2022-12-16T19:30:01Z)
• Linear Temporal Logic Modulo Theories over Finite Traces (Extended Version) [72.38188258853155]
  This paper studies Linear Temporal Logic over Finite Traces (LTLf) proposition letters are replaced with first-order formulas interpreted over arbitrary theories. The resulting logic, called Satisfiability Modulo Theories (LTLfMT), is semi-decidable.
  arXiv  Detail & Related papers  (2022-04-28T17:57:33Z)
• Joint Contrastive Learning with Infinite Possibilities [114.45811348666898]
  This paper explores useful modifications of the recent development in contrastive learning via novel probabilistic modeling. We derive a particular form of contrastive loss named Joint Contrastive Learning (JCL)
  arXiv  Detail & Related papers  (2020-09-30T16:24:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.