論文の概要: Structural Decompositions of Epistemic Logic Programs

• arxiv url: http://arxiv.org/abs/2001.04219v1
• Date: Mon, 13 Jan 2020 13:16:13 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-11 22:30:29.362216
• Title: Structural Decompositions of Epistemic Logic Programs
• Title（参考訳）: てんかん論理プログラムの構造分解
• Authors: Markus Hecher, Michael Morak, Stefan Woltran
• Abstract要約: 認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である 本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。 また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
• 参考スコア（独自算出の注目度）: 29.23726484912091
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Epistemic logic programs (ELPs) are a popular generalization of standard Answer Set Programming (ASP) providing means for reasoning over answer sets within the language. This richer formalism comes at the price of higher computational complexity reaching up to the fourth level of the polynomial hierarchy. However, in contrast to standard ASP, dedicated investigations towards tractability have not been undertaken yet. In this paper, we give first results in this direction and show that central ELP problems can be solved in linear time for ELPs exhibiting structural properties in terms of bounded treewidth. We also provide a full dynamic programming algorithm that adheres to these bounds. Finally, we show that applying treewidth to a novel dependency structure---given in terms of epistemic literals---allows to bound the number of ASP solver calls in typical ELP solving procedures.
• Abstract（参考訳）: 認識論理プログラム (ELP) は標準解集合プログラミング (ASP) の一般的な一般化であり、言語内の解集合を推論する手段を提供する。 このよりリッチな形式主義は、多項式階層の4番目のレベルに達する高い計算複雑性の価格で現れる。 しかし、標準的なASPとは対照的に、トラクタビリティに関する専用の調査はまだ行われていない。 本稿では,この方向の最初の結果を示し,有界木幅で構造特性を示すELPに対して線形時間で中央のALP問題を解くことができることを示す。 また、これらの境界に従う完全な動的プログラミングアルゴリズムも提供します。 最後に,新しい依存関係構造に木幅を適用することで,典型的なERP解決手順におけるASPソルバ呼び出し数を制限できることを示す。

関連論文リスト

• Probabilistic and Causal Satisfiability: the Impact of Marginalization [3.44747819522562]
  確率的・因果的言語で表される満足度問題に焦点をあてる。 線形言語はNPPP-, PSPACE-, NEXP完全満足度問題をもたらすことを示す。 また、与えられたベイズネットワーク、有向非巡回グラフ構造、あるいは小さなサイズに制限された制約付きモデルについても検討する。
  論文  参考訳（メタデータ） (2024-05-12T20:25:36Z)
• REBEL: Reinforcement Learning via Regressing Relative Rewards [59.68420022466047]
  生成モデルの時代における最小限のRLアルゴリズムであるREBELを提案する。 理論的には、自然ポリシーグラディエントのような基本的なRLアルゴリズムはREBELの変種と見なすことができる。 我々はREBELが言語モデリングと画像生成に一貫したアプローチを提供し、PPOやDPOとより強くあるいは類似した性能を実現することを発見した。
  論文  参考訳（メタデータ） (2024-04-25T17:20:45Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  我々は任意の解法によって生成されるPOMDP実行から高品質なトレースを学習する。 我々は、データと時間効率のIndu Logic Programming(ILP)を利用して、解釈可能な信念に基づくポリシー仕様を生成する。 ASP(Answer Set Programming)で表現された学習は、ニューラルネットワークよりも優れた性能を示し、より少ない計算時間で最適な手作りタスクに類似していることを示す。
  論文  参考訳（メタデータ） (2024-02-29T15:36:01Z)
• Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? [21.10339925217772]
  プログラムのルール構造上での解離的ASPの構造パラメータの分類に対処する。 我々は、その範囲で最も顕著なパラメータに対して、二重指数下界を提供する。 本研究は, 通常のプログラムから解離プログラムへの新規な縮小に頼って, 深部硬度調査を行う。
  論文  参考訳（メタデータ） (2024-02-05T21:51:36Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。 具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。 コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
  論文  参考訳（メタデータ） (2023-08-29T17:22:39Z)
• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  プログラム合成において望ましいいくつかの異なる構成一般化形式を特徴付ける。 本稿では,ExeDecを提案する。ExeDecは,実行サブゴールを予測し,各ステップでプログラム実行によって段階的に通知される問題を解くための,新しい分解ベースの戦略である。
  論文  参考訳（メタデータ） (2023-07-26T01:07:52Z)
• Query Structure Modeling for Inductive Logical Reasoning Over Knowledge Graphs [67.043747188954]
  KGに対する帰納的論理的推論のための構造モデル付きテキスト符号化フレームワークを提案する。 線形化されたクエリ構造とエンティティを、事前訓練された言語モデルを使ってエンコードして、回答を見つける。 2つの帰納的論理推論データセットと3つの帰納的推論データセットについて実験を行った。
  論文  参考訳（メタデータ） (2023-05-23T01:25:29Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  本稿では,ニューラルネットワーク演算子から知識グラフの埋め込みを分解する,複雑な問合せ応答のためのフレームワークを提案する。 クエリグラフの上に、局所的な原子式上のワンホップ推論とグローバル論理的推論を結びつける論理メッセージパッシングニューラルネットワーク(LMPNN)を提案する。 我々のアプローチは、最先端のニューラルCQAモデルをもたらす。
  論文  参考訳（メタデータ） (2023-01-21T02:34:06Z)
• Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth? [9.480212602202517]
  本稿では、よく知られたエンコーディングを超えるSATから通常のASPへの新規な削減について述べる。 これは依存性グラフのサイクル長の必要な機能的依存性を確立することによって、きめ細かい方法で硬さを特徴づける。
  論文  参考訳（メタデータ） (2023-01-18T12:29:45Z)
• Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs [22.39203220587435]
  本稿では,このような量的推論問題に対処するために必要な基礎的数え上げ問題を効率的に解くことのできる,新しいシステムを提案する。 本システムでは,木幅をグラフベースで表し,ELPプログラムの抽象表現(グラフ)を反復的に探索し,精算する。 私たちのアプローチは、最近導入された既存のシステムと競合しています。
  論文  参考訳（メタデータ） (2021-08-06T09:46:34Z)
• selp: A Single-Shot Epistemic Logic Program Solver [19.562205966997947]
  Epistemic Logic Programs (ELP) は Answer Set Programming (ASP) の拡張である また, 有界アリティを持つ非地上ASPへの ELP からの直接変換が存在することを示す。 次に、この符号化手法を、最近提案された大規模かつ非地上的なASPルールを扱う手法を用いて、プロトタイプのELP解決システム「セルプ」に実装する。
  論文  参考訳（メタデータ） (2020-01-04T15:36:31Z)

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

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