論文の概要: The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules

• arxiv url: http://arxiv.org/abs/2407.14384v1
• Date: Fri, 19 Jul 2024 15:11:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-22 17:05:24.161752
• Title: The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules
• Title（参考訳）: 表現型クエリへの粘着経路:既存のルールによるナビゲーションクエリの決定可能性
• Authors: Piotr Ostropolski-Nalewaja, Sebastian Rudolph,
• Abstract要約: 本稿では,これらの断片の問合せの可否が正規経路クエリ(RPQ)にまで拡張されるのかを考察する。 有限ユニフィケーション集合(短い: fus)として知られる2番目の主要な断片群に対して、対応する結果は大部分が解明されている。 正の面では、この問題はスティッキー・ルールセットの顕著なファス・サブクラスに対して決定可能であることを証明し、RPQ形式主義の非常に穏やかな拡張が問題を再び決定不能にする点に注意する。
• 参考スコア（独自算出の注目度）: 4.557963624437784
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Extensive research in the field of ontology-based query answering has led to the identification of numerous fragments of existential rules (also known as tuple-generating dependencies) that exhibit decidable answering of atomic and conjunctive queries. Motivated by the increased theoretical and practical interest in navigational queries, this paper considers the question for which of these fragments decidability of querying extends to regular path queries (RPQs). In fact, decidability of RPQs has recently been shown to generally hold for the comprehensive family of all fragments that come with the guarantee of universal models being reasonably well-shaped (that is, being of finite cliquewidth). Yet, for the second major family of fragments, known as finite unification sets (short: fus), which are based on first-order-rewritability, corresponding results have been largely elusive so far. We complete the picture by showing that RPQ answering over arbitrary fus rulesets is undecidable. On the positive side, we establish that the problem is decidable for the prominent fus subclass of sticky rulesets, with the caveat that a very mild extension of the RPQ formalism turns the problem undecidable again.
• Abstract（参考訳）: オントロジーに基づく問合せ応答の分野における広範な研究により、原子的および共役的な問合せの決定可能な解法を示す多数の存在規則(タプル生成依存性とも呼ばれる)の断片が同定された。 ナビゲーションクエリに対する理論的および実践的な関心の高まりに動機づけられた本論文では,これらの断片のどちらが正規経路クエリ(RPQ)に拡張できるかを考察する。 実際、RPQの決定可能性は最近、普遍モデルが合理的に整形である(つまり有限クリフ幅である)ことを保証する全ての断片の包括的族に対して成り立つことが示されている。 しかし、有限統一集合(短い:fus)として知られる2番目の主要な断片群は、一階補修性に基づいており、それに対応する結果は、これまでほとんど解明されてきた。 任意のファス・ルールセットに対するRPQ応答が決定不可能であることを示して、この図を完成させる。 正の面では、この問題はスティッキー・ルールセットの顕著なファス・サブクラスに対して決定可能であることを証明し、RPQ形式主義の非常に穏やかな拡張が問題を再び決定不能にする点に注意する。

関連論文リスト

• Aggregation of Reasoning: A Hierarchical Framework for Enhancing Answer Selection in Large Language Models [84.15513004135576]
  最近の研究は、複数の推論チェーンをサンプリングし、応答周波数に基づいてアンサンブルすることで、Large Language Models(LLMs)の推論性能を向上させる。 このアプローチは、正しい答えが少数派である場合に失敗する。 階層的推論集約フレームワークAoRを導入し、推論連鎖の評価に基づいて回答を選択する。
  論文  参考訳（メタデータ） (2024-05-21T17:12:19Z)
• Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering [83.74210749046551]
  ヘテロジニアス知識統合のための質問分解手法を提案する。 階層的質問分解木(RoHT)を用いた新しい2段階XQAフレームワークを提案する。 複雑なQAデータセットKQA ProとMusiqueの実験は、我々のフレームワークがSOTAメソッドを著しく上回っていることを示している。
  論文  参考訳（メタデータ） (2023-05-24T11:45:59Z)
• Shortcomings of Question Answering Based Factuality Frameworks for Error Localization [51.01957350348377]
  質問応答(QA)に基づく事実性指標は、生成した要約の誤り範囲を正しく識別できないことを示す。 このようなローカライゼーションが不十分な理由として,QGモジュールが生成した質問は,非実数的な要約から誤りを継承することが多く,さらに下流モジュールに伝播する。 本実験は,より強力なQAモデルとQGモデルでのみ修正できないQAフレームワークを用いた局所化に関する根本的な問題が存在することを確定的に示す。
  論文  参考訳（メタデータ） (2022-10-13T05:23:38Z)
• Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making [48.87943416098096]
  本稿では,一般的な逐次決定のための簡単な学習アルゴリズムを提案する。 我々は,OMLEが極めて豊富な逐次的意思決定問題のクラスにおいて,ほぼ最適ポリシーを学習していることを証明する。
  論文  参考訳（メタデータ） (2022-09-29T17:56:25Z)
• Finite Entailment of UCRPQs over ALC Ontologies [0.82179684645881]
  我々は、クエリ言語、結合正則経路クエリの結合(UCRPQ)を考える。 記述論理 ALC を用いて,UCRPQ の包含のための厳密な 2EXP バウンドを示す。 入力オートマトンの背後にある決定論的有限オートマトンによって誘導される解釈の階層化を導入する新しいオートマトンベースの技術がある。
  論文  参考訳（メタデータ） (2022-04-29T17:38:13Z)
• Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
  本稿では,知識グラフにエッジを欠いた複雑な論理的クエリに応答するクエリ埋め込み手法を提案する。 回答エンティティは、エンティティの埋め込みとクエリの埋め込みの類似性に応じて選択される。 埋め込み空間上の様々な領域から多様な回答を検索するために,複雑なKGクエリ応答方法Q2Pを提案する。
  論文  参考訳（メタデータ） (2022-04-27T11:16:08Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Answering Fuzzy Queries over Fuzzy DL-Lite Ontologies [0.2741266294612776]
  ファジィDL-Liteにおける接続クエリとしきい値クエリに応答する問題について検討する。 idemdent G"odel t-norm に対して、古典的ケースへの還元に基づく効果的な方法を提案する。
  論文  参考訳（メタデータ） (2021-11-23T10:45:54Z)
• First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics [22.32075802508239]
  FO-rewriting is more complex for conjunctive query than for atomic query are present, but not other。 特にFO書き換えは、逆ロールが存在する場合のアトミッククエリよりも、結合型クエリでは複雑だが、そうでない場合は複雑である。
  論文  参考訳（メタデータ） (2020-11-19T14:24:02Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)
• Containment of Simple Regular Path Queries [1.869065967043578]
  クエリの包含をテストすることは、知識表現における基本的な推論タスクである。 ここでは厳格に制限された断片に焦点をあてるが、実際には非常に関連性が高いことが知られている。 クエリの正規表現で使用される機能によらず,np, pitwo, pspace, expspace の完全性の結果が得られた。
  論文  参考訳（メタデータ） (2020-03-09T21:05:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。