On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles

• URL: http://arxiv.org/abs/2010.11503v1
• Date: Thu, 22 Oct 2020 07:44:00 GMT
• Title: On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles
• Authors: Thomas Gogacz, V\'ictor Guti\'errez-Basulto, Yazm\'in Ib\'a\~nez-Garc\'ia, Jean Christoph Jung, Filip Murlak
• Abstract summary: 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.
• Score: 8.107243891682305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the description logic SQ with number restrictions applicable to transitive roles, extended with either nominals or inverse roles. 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 (the latter under restriction to a single, transitive role).

Related papers

• DQ-LoRe: Dual Queries with Low Rank Approximation Re-ranking for In-Context Learning [66.85379279041128]
  In this study, we introduce a framework that leverages Dual Queries and Low-rank approximation Re-ranking to automatically select exemplars for in-context learning. DQ-LoRe significantly outperforms prior state-of-the-art methods in the automatic selection of exemplars for GPT-4, enhancing performance from 92.5% to 94.2%.
  arXiv  Detail & Related papers  (2023-10-04T16:44:37Z)
• Qubit Number Optimization for Restriction Terms of QUBO Hamiltonians [62.997667081978825]
  It is mathematically allowed to ask for fractional values of $R$. We show how they can reduce the number of qubits needed to implement the restriction hamiltonian even further. Finally, we characterize the response of DWave's Advantage$_$system4.1 Quantum Annealer (QA) when faced with the implementation of FRCs.
  arXiv  Detail & Related papers  (2023-06-12T08:25:56Z)
• Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts [53.579515853222986]
  We study a novel bandit setting, namely Multi-Armed Bandit with Temporally-Partitioned Rewards (TP-MAB) This setting is a natural extension of delayed-feedback bandits to the case in which rewards may be dilated over a finite-time span after the pull. We provide two algorithms to address TP-MAB problems, namely, TP-UCB-FR and TP-UCB-EW.
  arXiv  Detail & Related papers  (2022-06-01T15:56:59Z)
• Logic Embeddings for Complex Query Answering [56.25151854231117]
  We propose Logic Embeddings, a new approach to embedding complex queries that uses Skolemisation to eliminate existential variables for efficient querying. We show that Logic Embeddings are competitively fast and accurate in query answering over large, incomplete knowledge graphs, outperform on negation queries, and in particular, provide improved modeling of answer uncertainty.
  arXiv  Detail & Related papers  (2021-02-28T07:52:37Z)
• Superposition with Lambdas [59.87497175616048]
  We design a superposition calculus for a clausal fragment of extensional polymorphic higher-order logic that includes anonymous functions but excludes Booleans. The inference rules work on $betaeta$-equivalence classes of $lambda$-terms and rely on higher-order unification to achieve refutational completeness.
  arXiv  Detail & Related papers  (2021-01-31T13:53:17Z)
• Conservative Extensions in Horn Description Logics with Inverse Roles [21.5203698966022]
  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.
  arXiv  Detail & Related papers  (2020-11-19T14:41:02Z)
• 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)
• Answering Regular Path Queries Over SQ Ontologies [9.03029278078007]
  We study query answering in the description logic $mathcalSQ$. Our main contributions are a tree-like model property for $mathcalSQ$ knowledge bases and, building upon this, an optimal automata-based algorithm for answering positive existential regular path queries in 2ExpTime.
  arXiv  Detail & Related papers  (2020-11-17T18:27:20Z)
• On Finite Entailment of Non-Local Queries in Description Logics [1.3192452635990861]
  We focus on the logic descriptions ALCOIQ and ALCO, extended with transitive closure. For both logics, we show 2EXPTIME upper bounds for finite entailment of conjunctive queries with transitive closure.
  arXiv  Detail & Related papers  (2020-06-30T14:57:12Z)
• Relative Deviation Margin Bounds [55.22251993239944]
  We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity. We derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment.
  arXiv  Detail & Related papers  (2020-06-26T12:37:17Z)
• The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs [10.042878093985458]
  Ontology-mediated querying and querying in the presence of constraints are two key database problems. We study the limits of efficient query evaluation in the context of guarded and frontier-guarded TGDs and on UCQs as the actual queries.
  arXiv  Detail & Related papers  (2019-12-28T11:08:33Z)

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.