Conservative Extensions in Horn Description Logics with Inverse Roles

• URL: http://arxiv.org/abs/2011.09858v1
• Date: Thu, 19 Nov 2020 14:41:02 GMT
• Title: Conservative Extensions in Horn Description Logics with Inverse Roles
• Authors: Jean Christoph Jung, Carsten Lutz, Mauricio Martel, Thomas Schneider
• Abstract summary: We investigate the decidability and computational complexity of conservative extensions and the notions of inseparability and entailment in Horn description logics (DLs) with inverse roles. Our main results are that query conservative extensions are 2ExpTime-complete in all DLs between ELI and Horn-ALCHIF and between Horn-ALC and Horn-ALCHIF, and that deductive conservative extensions are 2ExpTime-complete in all DLs between ELI and ELHIF_bot.
• Score: 21.5203698966022
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the decidability and computational complexity of conservative extensions and the related notions of inseparability and entailment in Horn description logics (DLs) with inverse roles. We consider both query conservative extensions, defined by requiring that the answers to all conjunctive queries are left unchanged, and deductive conservative extensions, which require that the entailed concept inclusions, role inclusions, and functionality assertions do not change. Upper bounds for query conservative extensions are particularly challenging because characterizations in terms of unbounded homomorphisms between universal models, which are the foundation of the standard approach to establishing decidability, fail in the presence of inverse roles. We resort to a characterization that carefully mixes unbounded and bounded homomorphisms and enables a decision procedure that combines tree automata and a mosaic technique. Our main results are that query conservative extensions are 2ExpTime-complete in all DLs between ELI and Horn-ALCHIF and between Horn-ALC and Horn-ALCHIF, and that deductive conservative extensions are 2ExpTime-complete in all DLs between ELI and ELHIF_\bot. The same results hold for inseparability and entailment.

Related papers

• Nonparametric Partial Disentanglement via Mechanism Sparsity: Sparse Actions, Interventions and Sparse Temporal Dependencies [58.179981892921056]
  This work introduces a novel principle for disentanglement we call mechanism sparsity regularization. We propose a representation learning method that induces disentanglement by simultaneously learning the latent factors. We show that the latent factors can be recovered by regularizing the learned causal graph to be sparse.
  arXiv  Detail & Related papers  (2024-01-10T02:38:21Z)
• Language Models with Rationality [57.37201135072838]
  Large language models (LLMs) are proficient at question-answering (QA) It is not always clear how (or even if) an answer follows from their latent "beliefs"
  arXiv  Detail & Related papers  (2023-05-23T17:04:25Z)
• Think Rationally about What You See: Continuous Rationale Extraction for Relation Extraction [86.90265683679469]
  Relation extraction aims to extract potential relations according to the context of two entities. We propose a novel rationale extraction framework named RE2, which leverages two continuity and sparsity factors. Experiments on four datasets show that RE2 surpasses baselines.
  arXiv  Detail & Related papers  (2023-05-02T03:52:34Z)
• Equivalent non-rational extensions of the harmonic oscillator, their ladder operators and coherent states [0.0]
  We generate a family of quantum potentials that are non-rational extensions of the harmonic oscillator. We analyze some of their properties as temporal stability, continuity on the label, and completeness relation.
  arXiv  Detail & Related papers  (2022-08-20T18:59:48Z)
• Maieutic Prompting: Logically Consistent Reasoning with Recursive Explanations [71.2950434944196]
  We develop Maieutic Prompting, which infers a correct answer to a question even from the noisy and inconsistent generations of language models. Maieutic Prompting achieves up to 20% better accuracy than state-of-the-art prompting methods.
  arXiv  Detail & Related papers  (2022-05-24T06:36:42Z)
• 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)
• First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics [22.32075802508239]
  We show that FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise. In particular, FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise.
  arXiv  Detail & Related papers  (2020-11-19T14:24:02Z)
• On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles [8.107243891682305]
  We show tight 2EXPTIME upper bounds for unrestricted entailment of regular path queries for both extensions and finite entailment of positive existential queries for nominals. For inverses, we establish 2EXPTIME-completeness for unrestricted and finite entailment of instance queries.
  arXiv  Detail & Related papers  (2020-10-22T07:44:00Z)
• 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)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  We study the evaluation of ontology-mediated queries over relational databases. We provide a characterization of the classes of OMQs that are tractable in combined complexity. We also study the complexity of deciding whether a given OMQ is equivalent to an OMQ of bounded tree width.
  arXiv  Detail & Related papers  (2020-03-17T16:32:00Z)
• Conditional Self-Attention for Query-based Summarization [49.616774159367516]
  We propose textitconditional self-attention (CSA), a neural network module designed for conditional dependency modeling. Experiments on Debatepedia and HotpotQA benchmark datasets show CSA consistently outperforms vanilla Transformer.
  arXiv  Detail & Related papers  (2020-02-18T02:22: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.