論文の概要: The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard

• arxiv url: http://arxiv.org/abs/2106.15150v1
• Date: Tue, 29 Jun 2021 08:12:03 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-30 15:22:19.391925
• Title: The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard
• Title（参考訳）: 自尊心の価格: ALCSelf の接続型クエリエンターメントは 2expTime-hard である
• Authors: Bartosz Bednarczyk and Sebastian Rudolph
• Abstract要約: 論理に基づく知識表現では、クエリ応答は基本的に単に満足度チェックに置き換えられている。 基本記述論理 ALC の知識ベースでは、連結クエリ(CQ)応答の計算複雑性はExpTime-complete であることが知られている。 自己演算子のみによるALCの拡張さえも,CQ含意の複雑さを2ExpTimeに高めることを示す。
• 参考スコア（独自算出の注目度）: 11.193504036335503
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In logic-based knowledge representation, query answering has essentially replaced mere satisfiability checking as the inferencing problem of primary interest. For knowledge bases in the basic description logic ALC, the computational complexity of conjunctive query (CQ) answering is well known to be ExpTime-complete and hence not harder than satisfiability. This does not change when the logic is extended by certain features (such as counting or role hierarchies), whereas adding others (inverses, nominals or transitivity together with role-hierarchies) turns CQ answering exponentially harder. We contribute to this line of results by showing the surprising fact that even extending ALC by just the Self operator - which proved innocuous in many other contexts - increases the complexity of CQ entailment to 2ExpTime. As common for this type of problem, our proof establishes a reduction from alternating Turing machines running in exponential space, but several novel ideas and encoding tricks are required to make the approach work in that specific, restricted setting.
• Abstract（参考訳）: 論理に基づく知識表現では、クエリ応答は基本的に、主関心の推論問題として単に満足度チェックに置き換えられている。 基本記述論理 ALC の知識ベースでは、連結クエリ(CQ)応答の計算複雑性はExpTime完全であることがよく知られており、満足度よりも難しくはない。 これは論理が特定の特徴(数え上げや役割階層など)によって拡張されたときに変化しないが、他のもの(逆、名目、推移性)を追加するとcqは指数関数的に難しくなる。 我々は、他の多くの文脈で無意味であることが証明された自己作用素によってalcを拡張することさえも、cqの複雑さを2exptimeに増やすことで、この一連の結果に寄与する。 この種の問題に共通して、我々の証明は指数空間で動作するチューリングマシンの交互化による削減を確立するが、その特定の制限された環境でアプローチを動作させるためには、いくつかの新しいアイデアと符号化トリックが必要である。

関連論文リスト

• Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints [48.831178420807646]
  我々は、EVentuality中心のKGに基づいて、ニューラルネットワークを利用して複雑な論理的クエリに応答する新しいフレームワークを提案する。 複合事象性クエリ・アンサーリング(CEQA)は、時間的順序と事象の発生を規定する暗黙の論理的制約を考察する。 また、CEQAタスク上での最先端のニューラルクエリエンコーダの性能を大幅に向上させるメモリ拡張クエリ(MEQE)を提案する。
  論文  参考訳（メタデータ） (2023-05-30T14:29:24Z)
• 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)
• Finite Entailment of UCRPQs over ALC Ontologies [0.82179684645881]
  我々は、クエリ言語、結合正則経路クエリの結合(UCRPQ)を考える。 記述論理 ALC を用いて,UCRPQ の包含のための厳密な 2EXP バウンドを示す。 入力オートマトンの背後にある決定論的有限オートマトンによって誘導される解釈の階層化を導入する新しいオートマトンベースの技術がある。
  論文  参考訳（メタデータ） (2022-04-29T17:38:13Z)
• End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking [52.05847268235338]
  機械学習システムが問題を過度に考えずに論理的外挿を行う方法を示す。 本稿では,問題インスタンスの明示的なコピーをメモリに保持して,それを忘れないようにするリコールアーキテクチャを提案する。 また、モデルが数に固有の行動を学ぶのを防ぎ、無期限に繰り返される行動を学ぶためにモデルをプッシュするプログレッシブトレーニングルーチンも採用しています。
  論文  参考訳（メタデータ） (2022-02-11T18:43:28Z)
• Logic Embeddings for Complex Query Answering [56.25151854231117]
  skolemisationを用いて効率的なクエリのための存在変数を排除する、複雑なクエリを組み込む新しいアプローチであるlogic embeddedsを提案する。 論理組込みは,大規模で不完全な知識グラフ上でのクエリ応答において競争的に高速かつ正確であり,否定的問合せよりも優れており,特に回答の不確かさのモデリングが向上している。
  論文  参考訳（メタデータ） (2021-02-28T07:52:37Z)
• 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)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)
• CQE in Description Logics Through Instance Indistinguishability (extended version) [0.0]
  Description Logics (DL) におけるプライバシ保護クエリ応答に関する研究 DL-Lite$_mathcal$$で応答するデータ複雑性の結果を導出します。 我々は,CQEに対する近似秘密性解答という意味論的に確立された概念を同定する。
  論文  参考訳（メタデータ） (2020-04-24T17:28:24Z)
• VQA-LOL: Visual Question Answering under the Lens of Logic [58.30291671877342]
  画像に関する疑問に答えるように訓練された視覚的質問応答システムが,複数の質問の論理的構成に答えられるかどうかを検討する。 本稿では,VQAデータセットをベンチマークとして拡張し,論理的構成や言語的変換を含む質問を行う。 本稿では,論理的結合性を理解するために質問注意と論理意図を用いたLOLモデルと,新しいFr'echet-Compatibility Lossを提案する。
  論文  参考訳（メタデータ） (2020-02-19T17:57:46Z)

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

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