Semiring Provenance for Lightweight Description Logics

• URL: http://arxiv.org/abs/2310.16472v3
• Date: Wed, 26 Mar 2025 16:51:20 GMT
• Title: Semiring Provenance for Lightweight Description Logics
• Authors: Camille Bourgaux, Ana Ozaki, Rafael Peñaloza,
• Abstract summary: We investigate provenance semiring--a successful framework originally defined in the database setting--for description logics.<n>We show that under some restrictions on the semiring, the semantics satisfies desirable properties.<n>We study the complexity of problems related to the provenance of an assertion or a conjunctive query answer.
• Score: 10.63497953913371
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate semiring provenance--a successful framework originally defined in the relational database setting--for description logics. In this context, the ontology axioms are annotated with elements of a commutative semiring and these annotations are propagated to the ontology consequences in a way that reflects how they are derived. We define a provenance semantics for a language that encompasses several lightweight description logics and show its relationships with semantics that have been defined for ontologies annotated with a specific kind of annotation (such as fuzzy degrees). We show that under some restrictions on the semiring, the semantics satisfies desirable properties (such as extending the semiring provenance defined for databases). We then focus on the well-known why-provenance, for which we study the complexity of problems related to the provenance of an assertion or a conjunctive query answer. Finally, we consider two more restricted cases which correspond to the so-called positive Boolean provenance and lineage in the database setting. For these cases, we exhibit relationships with well-known notions related to explanations in description logics and complete our complexity analysis. As a side contribution, we provide conditions on an $\mathcal{ELHI}_\bot$ ontology that guarantee tractable reasoning.

Related papers

• CLATTER: Comprehensive Entailment Reasoning for Hallucination Detection [60.98964268961243]
  We propose that guiding models to perform a systematic and comprehensive reasoning process allows models to execute much finer-grained and accurate entailment decisions.<n>We define a 3-step reasoning process, consisting of (i) claim decomposition, (ii) sub-claim attribution and entailment classification, and (iii) aggregated classification, showing that such guided reasoning indeed yields improved hallucination detection.
  arXiv  Detail & Related papers  (2025-06-05T17:02:52Z)
• A New Tractable Description Logic under Categorical Semantics [0.0]
  It is known that adding negation to the tractable Description Logic (DL) EL allows for conjunction, existential restriction and concept inclusion.<n>We propose a new extension of EL with a weakened negation allowing to represent negative knowledge while retaining tractability.
  arXiv  Detail & Related papers  (2025-05-13T19:25:21Z)
• A Note on an Inferentialist Approach to Resource Semantics [48.65926948745294]
  'Inferentialism' is the view that meaning is given in terms of inferential behaviour. This paper shows how 'inferentialism' enables a versatile and expressive framework for resource semantics.
  arXiv  Detail & Related papers  (2024-05-10T14:13:21Z)
• Inferentialist Resource Semantics [48.65926948745294]
  This paper shows how inferentialism enables a versatile and expressive framework for resource semantics. How inferentialism seamlessly incorporates the assertion-based approach of the logic of Bunched Implications. This integration enables reasoning about shared and separated resources in intuitive and familiar ways.
  arXiv  Detail & Related papers  (2024-02-14T14:54:36Z)
• 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)
• Logic-induced Diagnostic Reasoning for Semi-supervised Semantic Segmentation [85.12429517510311]
  LogicDiag is a neural-logic semi-supervised learning framework for semantic segmentation. Our key insight is that conflicts within pseudo labels, identified through symbolic knowledge, can serve as strong yet commonly ignored learning signals. We showcase the practical application of LogicDiag in the data-hungry segmentation scenario, where we formalize the structured abstraction of semantic concepts as a set of logic rules.
  arXiv  Detail & Related papers  (2023-08-24T06:50:07Z)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning. Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
  arXiv  Detail & Related papers  (2023-06-21T07:34:27Z)
• Nested Counterfactual Identification from Arbitrary Surrogate Experiments [95.48089725859298]
  We study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. Specifically, we prove the counterfactual unnesting theorem (CUT), which allows one to map arbitrary nested counterfactuals to unnested ones.
  arXiv  Detail & Related papers  (2021-07-07T12:51:04Z)
• A Description Logic for Analogical Reasoning [28.259681405091666]
  We present a mechanism to infer plausible missing knowledge, which relies on reasoning by analogy. This is the first paper that studies analog reasoning within the setting of description logic.
  arXiv  Detail & Related papers  (2021-05-10T19:06:07Z)
• The logic of contextuality [0.0]
  Contextuality is a key signature of quantum non-classicality. We study the logic of contextuality in the setting of partial Boolean algebras.
  arXiv  Detail & Related papers  (2020-11-05T19:04:04Z)
• Foundations of Reasoning with Uncertainty via Real-valued Logics [70.43924776071616]
  We give a sound and strongly complete axiomatization that can be parametrized to cover essentially every real-valued logic. Our class of sentences are very rich, and each describes a set of possible real values for a collection of formulas of the real-valued logic.
  arXiv  Detail & Related papers  (2020-08-06T02:13:11Z)
• Provenance for the Description Logic ELHr [9.35688592148841]
  We consider a setting recently introduced for data access based on provenance and extending classical data provenance. We show that the presence of axioms poses various difficulties for handling provenance, some of which are mitigated by assuming multiplicative idempotency of the semiring.
  arXiv  Detail & Related papers  (2020-01-21T13:56:48Z)

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.