A New Tractable Description Logic under Categorical Semantics

• URL: http://arxiv.org/abs/2505.08916v1
• Date: Tue, 13 May 2025 19:25:21 GMT
• Title: A New Tractable Description Logic under Categorical Semantics
• Authors: Chan Le Duc, Ludovic Brieulle,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Biomedical ontologies contain numerous concept or role names involving negative knowledge such as lacks_part, absence_of. Such a representation with labels rather than logical constructors would not allow a reasoner to interpret lacks_part as a kind of negation of has_part. It is known that adding negation to the tractable Description Logic (DL) EL allowing for conjunction, existential restriction and concept inclusion makes it intractable since the obtained logic includes implicitly disjunction and universal restriction which interact with other constructors. In this paper, we propose a new extension of EL with a weakened negation allowing to represent negative knowledge while retaining tractability. To this end, we introduce categorical semantics of all logical constructors of the DL SH including EL with disjunction, negation, universal restriction, role inclusion and transitive roles. The categorical semantics of a logical constructor is usually described as a set of categorical properties referring to several objects without using set membership. To restore tractability, we have to weaken semantics of disjunction and universal restriction by identifying \emph{independent} categorical properties that are responsible for intractability, and dropping them from the set of categorical properties. We show that the logic resulting from weakening semantics is more expressive than EL with the bottom concept, transitive roles and role inclusion.

Related papers

• On the Logical Content of Logic Programs [0.0]
  This paper introduces a novel perspective on Logic programming (LP) by defining a support'' relation that explicates what a program knows''<n>Results are formalized using the idea of base-extension semantics within proof-theoretic semantics.<n>Our approach offers new insights into the logical foundations of LP and has potential applications in knowledge representation, automated reasoning, and formal verification.
  arXiv  Detail & Related papers  (2025-03-07T11:58:08Z)
• 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)
• Semiring Provenance for Lightweight Description Logics [10.63497953913371]
  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.
  arXiv  Detail & Related papers  (2023-10-25T08:53:49Z)
• 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)
• Description Logics Go Second-Order -- Extending EL with Universally Quantified Concepts [0.0]
  We focus on the extension of description logic $mathcalEL$. We show that for a useful fragment of the extension, the conclusions entailed by the different semantics coincide. For a slightly smaller, but still useful, fragment, we were also able to show decidability of the extension.
  arXiv  Detail & Related papers  (2023-08-16T09:37:38Z)
• 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)
• The Transformation Logics [58.35574640378678]
  We introduce a new family of temporal logics designed to balance the trade-off between expressivity and complexity. Key feature is the possibility of defining operators of a new kind that we call transformation operators. We show them to yield logics capable of creating hierarchies of increasing expressivity and complexity.
  arXiv  Detail & Related papers  (2023-04-19T13:24:04Z)
• Zero-Shot Classification by Logical Reasoning on Natural Language Explanations [56.42922904777717]
  We propose the framework CLORE (Classification by LOgical Reasoning on Explanations) CLORE parses explanations into logical structures and then explicitly reasons along thess structures on the input to produce a classification score. We also demonstrate that our framework can be extended to zero-shot classification on visual modality.
  arXiv  Detail & Related papers  (2022-11-07T01:05:11Z)
• Reasoning in the Description Logic ALC under Category Semantics [0.0]
  We present a reformulation of the usual set-theoretical semantics of the description logic $mathcalALC$ with general TBoxes by using categorical language. In this setting, $mathcalALC$ concepts are represented as objects, concept subsumptions as arrows, and memberships as logical quantifiers over objects and arrows of categories.
  arXiv  Detail & Related papers  (2022-05-10T14:03:44Z)
• Logical Neural Networks [51.46602187496816]
  We propose a novel framework seamlessly providing key properties of both neural nets (learning) and symbolic logic (knowledge and reasoning) Every neuron has a meaning as a component of a formula in a weighted real-valued logic, yielding a highly intepretable disentangled representation. Inference is omni rather than focused on predefined target variables, and corresponds to logical reasoning.
  arXiv  Detail & Related papers  (2020-06-23T16:55:45Z)
• Reasoning about Typicality and Probabilities in Preferential Description Logics [0.15749416770494704]
  We describe preferential Description Logics of typicality, a nonmonotonic extension of standard Description Logics by means of a typicality operator T. This extension is based on a minimal model semantics corresponding to a notion of rational closure. We consider other strengthening of the rational closure semantics and construction to avoid the so-called blocking of property inheritance problem.
  arXiv  Detail & Related papers  (2020-04-20T14:50:31Z)

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.