論文の概要: Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic
Programs
- arxiv url: http://arxiv.org/abs/2108.03022v1
- Date: Fri, 6 Aug 2021 09:46:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-09 14:25:07.583718
- Title: Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic
Programs
- Title（参考訳）: 樹幅を用いたてんかん論理プログラムの定量的推論
- Authors: Viktor Besin, Markus Hecher, Stefan Woltran
- Abstract要約: 本稿では,このような量的推論問題に対処するために必要な基礎的数え上げ問題を効率的に解くことのできる,新しいシステムを提案する。
本システムでは,木幅をグラフベースで表し,ELPプログラムの抽象表現(グラフ)を反復的に探索し,精算する。
私たちのアプローチは、最近導入された既存のシステムと競合しています。
- 参考スコア（独自算出の注目度）: 22.39203220587435
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Extending the popular Answer Set Programming (ASP) paradigm by introspective
reasoning capacities has received increasing interest within the last years.
Particular attention is given to the formalism of epistemic logic programs
(ELPs) where standard rules are equipped with modal operators which allow to
express conditions on literals for being known or possible, i.e., contained in
all or some answer sets, respectively. ELPs thus deliver multiple collections
of answer sets, known as world views. Employing ELPs for reasoning problems so
far has mainly been restricted to standard decision problems (complexity
analysis) and enumeration (development of systems) of world views. In this
paper, we take a next step and contribute to epistemic logic programming in two
ways: First, we establish quantitative reasoning for ELPs, where the acceptance
of a certain set of literals depends on the number (proportion) of world views
that are compatible with the set. Second, we present a novel system that is
capable of efficiently solving the underlying counting problems required to
answer such quantitative reasoning problems. Our system exploits the
graph-based measure treewidth and works by iteratively finding and refining
(graph) abstractions of an ELP program. On top of these abstractions, we apply
dynamic programming that is combined with utilizing existing search-based
solvers like (e)clingo for hard combinatorial subproblems that appear during
solving. It turns out that our approach is competitive with existing systems
that were introduced recently. This work is under consideration for acceptance
in TPLP.
- Abstract（参考訳）: イントロスペクティブ推論能力による一般的なAnswer Set Programming(ASP)パラダイムの拡張は、ここ数年で関心を集めています。
認識論理プログラム(ELP)の形式には特に注意が払われており、標準規則には、既知のまたは可能なリテラルの条件、すなわち、すべてまたはいくつかの回答セットにそれぞれ含めるモダル演算子が備わっている。
ELPはワールドビューとして知られる複数の回答セットを提供する。
これまでの推論問題に対するELPの利用は主に、世界観の標準的な決定問題(複雑度解析)と列挙(システム開発)に限られてきた。
本稿では、まず、あるリテラルの受け入れが、そのセットと互換性のある世界ビューの数(分布)に依存する、ALPの量的推論を確立する。
第2に,このような量的推論問題に答えるために必要な計数問題を効率的に解くことができる新しいシステムを提案する。
本システムでは,木幅をグラフベースで表し,ELPプログラムの抽象表現(グラフ)を反復的に探索し,精算する。
これらの抽象化の上に、(e)clingoのような既存の検索ベースの解法と組み合わせた動的プログラミングを、解法中に現れるハードコンビネータサブプロブレムに適用する。
私たちのアプローチは、最近導入された既存のシステムと競合しています。
この研究はTPLPの受け入れを検討中である。
関連論文リスト
- Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
大規模言語モデルの複雑な推論能力を高めるために,textbftextitThought Propagation (TP)を提案する。
TP はまず LLM に対して,入力問題に関連する類似問題の集合を提案し,解決するよう促す。
TPは、類似問題の結果を再利用して、新しいソリューションを直接生成したり、スクラッチから得られた初期ソリューションを修正するための知識集約的な実行プランを導出する。
論文 参考訳（メタデータ） (2023-10-06T01:40:09Z) - A Semantic Approach to Decidability in Epistemic Planning (Extended
Version) [72.77805489645604]
我々は決定可能性を達成するために新しい意味論的アプローチを用いる。
具体的には、知識の論理S5$_n$と(知識)可換性と呼ばれる相互作用公理を拡大する。
我々は,本フレームワークが,独立した知識である共通知識の有限的非固定点的特徴を認めていることを証明した。
論文 参考訳（メタデータ） (2023-07-28T11:26:26Z) - A Hybrid System for Systematic Generalization in Simple Arithmetic
Problems [70.91780996370326]
本稿では,記号列に対する合成的および体系的推論を必要とする算術的問題を解くことができるハイブリッドシステムを提案する。
提案システムは,最も単純なケースを含むサブセットでのみ訓練された場合においても,ネストした数式を正確に解くことができることを示す。
論文 参考訳（メタデータ） (2023-06-29T18:35:41Z) - Pushing the Boundaries of Tractable Multiperspective Reasoning: A
Deduction Calculus for Standpoint EL+ [2.9005223064604073]
Standpoint EL は一般的な記述論理 EL のマルチモーダル拡張である。
本稿では,この定式化の表現性を推し進めることで,Standpoint EL+と呼ばれる拡張論理に到達できることを示す。
これは、原型的満足度チェックの推論計算を設計することで達成される。
論文 参考訳（メタデータ） (2023-04-27T16:49:17Z) - On the Complexity of Rational Verification [5.230352342979224]
合理的検証とは、同時マルチエージェントシステムの時間論理特性が保持する問題を指す。
合理的な検証の複雑さは仕様によって大幅に低減できることを示す。
平均支払ユーティリティ関数によって与えられるプレイヤーの目標を考慮した場合、合理的な検証のための改善された結果を提供する。
論文 参考訳（メタデータ） (2022-07-06T12:56:22Z) - Efficient Knowledge Compilation Beyond Weighted Model Counting [7.828647825246474]
このような問題に対する一般的なフレームワークとして,第2レベル代数モデルカウント (2AMC) を導入している。
KC(Knowledge Compilation)に基づく第1レベルのテクニックは、変数順序制約を課すことで、特定の2AMCインスタンスに適応している。
2AMC問題の論理構造を利用して、これらの制約の一部を省略し、負の効果を制限できることが示される。
論文 参考訳（メタデータ） (2022-05-16T08:10:40Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳（メタデータ） (2020-06-05T10:56:52Z) - The ILASP system for Inductive Learning of Answer Set Programs [79.41112438865386]
我々のシステムは、通常の規則、選択規則、厳しい制約を含むアンサーセットプログラムを学習する。
まず、ILASPの学習フレームワークとその機能の概要を説明します。
続いて、ILASPシステムの進化を概観する。
論文 参考訳（メタデータ） (2020-05-02T19:04:12Z) - Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。
任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
論文 参考訳（メタデータ） (2020-02-12T18:59:18Z) - Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である
本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。
また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
論文 参考訳（メタデータ） (2020-01-13T13:16:13Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。