論文の概要: Complexity of Arithmetic in Warded Datalog+-

• arxiv url: http://arxiv.org/abs/2202.05086v1
• Date: Thu, 10 Feb 2022 15:14:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-11 16:24:32.080778
• Title: Complexity of Arithmetic in Warded Datalog+-
• Title（参考訳）: warded datalog+における算術の複雑さ
• Authors: Lucas Berent, Markus Nissl, Emanuel Sallinger
• Abstract要約: Warded Datalog+- ロジックベースの言語Datalogを拡張し、ルールヘッドに存在量化器を配置する。 我々はWarded Datalog+を算術演算で拡張し、P完全性を証明する新しい言語を定義する。 我々は,新たに定義された言語に対する効率的な推論アルゴリズムを提案し,最近導入された整数演算を用いたデータログフラグメントの記述的複雑性を証明した。
• 参考スコア（独自算出の注目度）: 1.5469452301122173
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Warded Datalog+- extends the logic-based language Datalog with existential quantifiers in rule heads. Existential rules are needed for advanced reasoning tasks, e.g., ontological reasoning. The theoretical efficiency guarantees of Warded Datalog+- do not cover extensions crucial for data analytics, such as arithmetic. Moreover, despite the significance of arithmetic for common data analytic scenarios, no decidable fragment of any Datalog+- language extended with arithmetic has been identified. We close this gap by defining a new language that extends Warded Datalog+- with arithmetic and prove its P-completeness. Furthermore, we present an efficient reasoning algorithm for our newly defined language and prove descriptive complexity results for a recently introduced Datalog fragment with integer arithmetic, thereby closing an open question. We lay the theoretical foundation for highly expressive Datalog+- languages that combine the power of advanced recursive rules and arithmetic while guaranteeing efficient reasoning algorithms for applications in modern AI systems, such as Knowledge Graphs.
• Abstract（参考訳）: warded datalog+- 論理ベースの言語datalogをルールヘッドに存在量化子で拡張する。 存在規則は、例えば存在論的推論のような高度な推論タスクのために必要である。 warded datalog+-の理論的効率保証は、算術のようなデータ分析に不可欠な拡張はカバーしない。 さらに、一般的なデータ分析シナリオにおける算術の重要性にもかかわらず、算術によって拡張されたdatalog+-言語の決定可能な断片は特定されていない。 我々はWarded Datalog+を算術で拡張し、P完全性を証明する新しい言語を定義することで、このギャップを埋める。 さらに,新たに定義された言語に対する効率的な推論アルゴリズムを提案し,最近導入された整数演算によるデータログフラグメントの記述的複雑性を証明し,オープン質問を閉じる。 我々は、知識グラフのような現代のAIシステムにおけるアプリケーションに対する効率的な推論アルゴリズムを保証しながら、高度な再帰規則と算術の力を組み合わせた、高度に表現力のあるDatalog+言語の理論基盤を定めている。

関連論文リスト

• Discovering symbolic expressions with parallelized tree search [59.92040079807524]
  記号回帰は、データから簡潔で解釈可能な数学的表現を発見する能力のおかげで、科学研究において重要な役割を果たす。 既存のアルゴリズムは、複雑性の問題に対処する際の精度と効率の重要なボトルネックに直面してきた。 本稿では,限定データから汎用数学的表現を効率的に抽出する並列木探索(PTS)モデルを提案する。
  論文  参考訳（メタデータ） (2024-07-05T10:41:15Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  大規模言語モデル(LLM)に基づくKG上の複雑な推論スキーマを提案する。 任意の一階論理クエリを二分木分解により拡張し、LLMの推論能力を刺激する。 広く使われているデータセットに対する実験では、LACTは高度な手法よりも大幅に改善されている(平均+5.5% MRRスコア)。
  論文  参考訳（メタデータ） (2024-05-02T18:12:08Z)
• Fuzzy Datalog$^\exists$ over Arbitrary t-Norms [5.464669506214195]
  ニューロ・シンボリックAIの領域における大きな課題の1つは、ニューラルデータとシンボリックデータの両方の存在下で論理的推論を行うことである。 これは知識グラフ、ニューラルモデル予測、構造化データベース、クラウドソースデータなどの異種データソースを組み合わせる必要がある。 規則体における古典的な接続の代わりとして任意のt-ノルムを許容することにより、規則ベースの標準言語Datalogをその設定に存在規則で一般化する。 結果のフォーマリズムにより、計算複雑性結果の保存と確立された推論技術の適用性を保ちながら、関連するデータを不確実性の度合いで推論することが可能となる。
  論文  参考訳（メタデータ） (2024-03-05T12:51:40Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。 具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。 コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
  論文  参考訳（メタデータ） (2023-08-29T17:22:39Z)
• Enhancing Datalog Reasoning with Hypertree Decompositions [17.868595375154506]
  データログプログラムの物質化と漸進的評価にハイパーツリー分解を利用するアルゴリズムを提供する。 このアプローチを標準データログ推論アルゴリズムとモジュール方式で組み合わせることで,分解によるオーバーヘッドを低減する。
  論文  参考訳（メタデータ） (2023-05-11T14:51:16Z)
• Seminaive Materialisation in DatalogMTL [10.850687097496373]
  DatalogMTLは、計量時間演算子を備えたDatalogの拡張である。 本稿では,冗長計算を最小化するための物質化に基づく手法を提案する。 実験の結果,DatalogMTLの最適化セミナティブ戦略により,製造時間を大幅に短縮できることがわかった。
  論文  参考訳（メタデータ） (2022-08-15T10:04:44Z)
• On the Relationship between Shy and Warded Datalog+/- [3.4696964555947694]
  DatalogEは、存在量化によるDatalogの拡張である。 知識グラフの現代的な応用に適しているが、そのような言語に対するクエリ応答(QA)は一般には決定不可能であることが知られている。 異なる断片が出現し、表現力とQAの計算複雑性のバランスをとるDatalogEに構文的制限が導入された。
  論文  参考訳（メタデータ） (2022-02-13T11:24:22Z)
• Logic-Driven Context Extension and Data Augmentation for Logical Reasoning of Text [65.24325614642223]
  論理的な記号や表現をテキストで理解し、答えにたどり着くよう提案します。 このような論理的情報に基づいて,文脈拡張フレームワークとデータ拡張アルゴリズムを提案する。 本手法は最先端の性能を実現し,論理駆動コンテキスト拡張フレームワークとデータ拡張アルゴリズムの両方が精度向上に寄与する。
  論文  参考訳（メタデータ） (2021-05-08T10:09:36Z)
• iWarded: A System for Benchmarking Datalog+/- Reasoning (technical report) [0.0]
  iWardedは、非常に大きく、複雑で、現実的な推論設定を生成するシステムです。 我々は,iWardedシステムと,有効シナリオを生成するための新しい理論結果のセットを提示する。
  論文  参考訳（メタデータ） (2021-03-15T17:56:46Z)
• Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
  PAC-セマンティックスにおける暗黙学習を拡張し、線形算術の言語における間隔としきい値の不確実性を扱う。 最適線形プログラミング対象制約の学習に対する我々の暗黙的アプローチは、実際的な明示的アプローチよりも著しく優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-23T19:08:46Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  グラフニューラルネットワーク(GNN)を用いた論理一般化の課題について検討する。 ベンチマークスイートであるGraphLogでは、学習アルゴリズムが異なる合成論理でルール誘導を実行する必要がある。 モデルが一般化し適応する能力は、トレーニング中に遭遇する論理規則の多様性によって強く決定される。
  論文  参考訳（メタデータ） (2020-03-14T05:45:55Z)

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

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