Reasoning in the Description Logic ALC under Category Semantics

• URL: http://arxiv.org/abs/2205.04911v1
• Date: Tue, 10 May 2022 14:03:44 GMT
• Title: Reasoning in the Description Logic ALC under Category Semantics
• Authors: Ludovic Brieulle and Chan Le Duc and Pascal Vaillant
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present in this paper a reformulation of the usual set-theoretical semantics of the description logic $\mathcal{ALC}$ with general TBoxes by using categorical language. In this setting, $\mathcal{ALC}$ concepts are represented as objects, concept subsumptions as arrows, and memberships as logical quantifiers over objects and arrows of categories. Such a category-based semantics provides a more modular representation of the semantics of $\mathcal{ALC}$. This feature allows us to define a sublogic of $\mathcal{ALC}$ by dropping the interaction between existential and universal restrictions, which would be responsible for an exponential complexity in space. Such a sublogic is undefinable in the usual set-theoretical semantics, We show that this sublogic is {\sc{PSPACE}} by proposing a deterministic algorithm for checking concept satisfiability which runs in polynomial space.

Related papers

• A Theory of Interpretable Approximations [61.90216959710842]
  We study the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $mathcalH$. For any given pair of $mathcalH$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $mathcalH$ with arbitrary accuracy. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-
  arXiv  Detail & Related papers  (2024-06-15T06:43:45Z)
• LOGICSEG: Parsing Visual Semantics with Neural Logic Learning and Reasoning [73.98142349171552]
  LOGICSEG is a holistic visual semantic that integrates neural inductive learning and logic reasoning with both rich data and symbolic knowledge. During fuzzy logic-based continuous relaxation, logical formulae are grounded onto data and neural computational graphs, hence enabling logic-induced network training. These designs together make LOGICSEG a general and compact neural-logic machine that is readily integrated into existing segmentation models.
  arXiv  Detail & Related papers  (2023-09-24T05:43:19Z)
• 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)
• Fuzzy order-sorted feature logic [2.5672176409865686]
  Order-Sorted Feature (OSF) logic is a knowledge representation and reasoning language based on function-denoting feature symbols and set-denoting sort symbols ordered in a subsumption lattice. We give a flexible definition of a fuzzy subsumption relation which generalizes Zadeh's inclusion between fuzzy sets. We show how to find the greatest lower bound of two OSF terms by unifying them and how to compute the subsumption degree between two OSF terms.
  arXiv  Detail & Related papers  (2023-07-27T07:47:54Z)
• Lattice-preserving $\mathcal{ALC}$ ontology embeddings with saturation [50.05281461410368]
  An order-preserving embedding method is proposed to generate embeddings of OWL representations. We show that our method outperforms state-the-art theory-of-the-art embedding methods in several knowledge base completion tasks.
  arXiv  Detail & Related papers  (2023-05-11T22:27:51Z)
• Non-Deterministic Approximation Fixpoint Theory and Its Application in Disjunctive Logic Programming [11.215352918313577]
  Approximation fixpoint theory is a framework for studying the semantics of nonmonotonic logics. We extend AFT to dealing with non-deterministic constructs that allow to handle indefinite information. The applicability and usefulness of this generalization is illustrated in the context of disjunctive logic programming.
  arXiv  Detail & Related papers  (2022-11-30T18:58:32Z)
• Logic-Driven Context Extension and Data Augmentation for Logical Reasoning of Text [65.24325614642223]
  We propose to understand logical symbols and expressions in the text to arrive at the answer. Based on such logical information, we put forward a context extension framework and a data augmentation algorithm. Our method achieves the state-of-the-art performance, and both logic-driven context extension framework and data augmentation algorithm can help improve the accuracy.
  arXiv  Detail & Related papers  (2021-05-08T10:09:36Z)
• Lexicographic Logic: a Many-valued Logic for Preference Representation [1.5484595752241122]
  We propose lexicographic logic, an extension of classical propositional logic that can express a variety of preferences. We argue that the new logic is an effective formalism for ranking query results according to the satisfaction level of user preferences.
  arXiv  Detail & Related papers  (2020-12-20T14:42: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)
• Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
  We introduce refutationally complete superposition calculi for intentional and extensional clausal $lambda$-free higher-order logic. The calculi are parameterized by a term order that need not be fully monotonic, making it possible to employ the $lambda$-free higher-order lexicographic path and Knuth-Bendix orders.
  arXiv  Detail & Related papers  (2020-05-05T12:10:21Z)
• Intuitionistic Linear Temporal Logics [0.7087237546722617]
  We consider intuitionistic variants of linear temporal logic with next', until' and release' We prove that $iltl$ has the effective finite model property and hence is decidable, while $itlb$ does not have the finite model property. We also introduce notions of bounded bisimulations for these logics and use them to show that the until' and release' operators are not definable in terms of each other, even over the class of persistent posets.
  arXiv  Detail & Related papers  (2019-12-30T11:49: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.