論文の概要: Parameterized Complexity of Logic-Based Argumentation in Schaefer's
Framework
- arxiv url: http://arxiv.org/abs/2102.11782v1
- Date: Tue, 23 Feb 2021 16:34:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-25 04:33:07.939717
- Title: Parameterized Complexity of Logic-Based Argumentation in Schaefer's
Framework
- Title(参考訳): シェーファーの枠組みにおける論理に基づく論証のパラメータ化複雑性
- Authors: Yasir Mahmood, Arne Meier, Johannes Schmidt
- Abstract要約: 以下の3つの計算タスクの命題的変種を議論の中で検討する。
ARG-Checkは複雑性クラスDPに対して完全であり、他の2つの問題は階層の2番目のレベルで完全であることが知られている。
いくつかの症例は非常に難治性が高い(paranp以降)
- 参考スコア(独自算出の注目度): 1.5469452301122177
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Logic-based argumentation is a well-established formalism modelling
nonmonotonic reasoning. It has been playing a major role in AI for decades,
now. Informally, a set of formulas is the support for a given claim if it is
consistent, subset-minimal, and implies the claim. In such a case, the pair of
the support and the claim together is called an argument. In this paper, we
study the propositional variants of the following three computational tasks
studied in argumentation: ARG (exists a support for a given claim with respect
to a given set of formulas), ARG-Check (is a given set a support for a given
claim), and ARG-Rel (similarly as ARG plus requiring an additionally given
formula to be contained in the support). ARG-Check is complete for the
complexity class DP, and the other two problems are known to be complete for
the second level of the polynomial hierarchy (Parson et al., J. Log. Comput.,
2003) and, accordingly, are highly intractable. Analyzing the reason for this
intractability, we perform a two-dimensional classification: first, we consider
all possible propositional fragments of the problem within Schaefer's framework
(STOC 1978), and then study different parameterizations for each of the
fragment. We identify a list of reasonable structural parameters (size of the
claim, support, knowledge-base) that are connected to the aforementioned
decision problems. Eventually, we thoroughly draw a fine border of
parameterized intractability for each of the problems showing where the
problems are fixed-parameter tractable and when this exactly stops.
Surprisingly, several cases are of very high intractability (paraNP and
beyond).
- Abstract(参考訳): 論理に基づく議論は、非単調推論をモデル化する定評のある形式主義である。
aiには何十年も前から大きな役割を果たしてきた。
形式的に、式の一式は、それが一貫した部分集合最小であり、主張を暗示するならば、与えられたクレームの支持である。
このような場合、サポートとクレームのペアを一緒に引数と呼びます。
本稿では,議論の中で研究されている3つの計算タスクの命題的変種について検討する。arg(ある論理式に対して与えられたクレームに対するサポートが存在する)、arg-check(与えられたクレームに対するサポートを与えられた集合である)、arg-rel(argとそれに含まれる追加の公式を必要とする)である。
ARG-Check は複雑性クラス DP に対して完全であり、その他の2つの問題は多項式階層の第2レベル (Parson et al., J. Log) に対して完全であることが知られている。
Comput., 2003)、そしてそれ故に、非常に難解である。
第一に、シェイファーの枠組み(STOC 1978)内の問題の可能性のあるすべての命題フラグメントを検討し、各フラグメントの異なるパラメータ化を研究する。
上記の決定問題に関連する合理的な構造パラメータ(クレーム,サポート,ナレッジベースのサイズ)のリストを同定する。
最終的に、固定パラメータがどこにあるか、いつそれが止まるのかを示す各問題に対して、パラメータ化の難しさの細かい境界を徹底的に描き出す。
驚くべきことに、いくつかのケースは非常に難易度が高い(paraNP以降)。
関連論文リスト
- Identification for Tree-shaped Structural Causal Models in Polynomial
Time [1.5151556900495786]
ノード間の相関から因果パラメータを同定することは、人工知能におけるオープンな問題である。
本稿では,木を配向成分とするSCMについて検討する。
本稿では,木形SCMの同定問題を解くランダム時間アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-11-23T15:26:29Z) - A Unifying Framework for Learning Argumentation Semantics [50.69905074548764]
Inductive Logic Programmingアプローチを用いて、抽象的および構造化された議論フレームワークのアクセシビリティセマンティクスを解釈可能な方法で学習する新しいフレームワークを提案する。
提案手法は既存の議論解法よりも優れており,フォーマルな議論や人間と機械の対話の領域において,新たな研究の方向性が開けることになる。
論文 参考訳(メタデータ) (2023-10-18T20:18:05Z) - Query Structure Modeling for Inductive Logical Reasoning Over Knowledge
Graphs [67.043747188954]
KGに対する帰納的論理的推論のための構造モデル付きテキスト符号化フレームワークを提案する。
線形化されたクエリ構造とエンティティを、事前訓練された言語モデルを使ってエンコードして、回答を見つける。
2つの帰納的論理推論データセットと3つの帰納的推論データセットについて実験を行った。
論文 参考訳(メタデータ) (2023-05-23T01:25:29Z) - Avoiding Pragmatic Oddity: A Bottom-up Defeasible Deontic Logic [1.160208922584163]
本稿では,実用性の問題に対処するため,Dedeasible Deontic Logicの拡張を提案する。
Pragmatic Oddity問題は、CTD推論の一般的な論理的処理の中で解決されなければならない; 2)非単調法はCTD推論を扱うために適用されなければならない; 3)CTD推論の論理モデルは計算可能で、可能であれば効率的でなければならない。
論文 参考訳(メタデータ) (2022-09-09T23:14:09Z) - Admissibility in Strength-based Argumentation: Complexity and Algorithms
(Extended Version with Proofs) [1.5828697880068698]
我々は、適応性に基づく意味論の強度に基づく論証フレームワーク(StrAF)への適応について研究する。
特に文献で定義された強い許容性は望ましい性質、すなわちDungの基本的な補題を満たさないことを示す。
計算(強弱)拡張に対する擬ブール制約の翻訳を提案する。
論文 参考訳(メタデータ) (2022-07-05T18:42:04Z) - Analytical Solutions for the Inverse Problem within Gradual Semantics [3.957174470017176]
本稿では,段階的意味論における逆問題の解法として解析的アプローチを用いる方法を示す。
現在の最先端とは違って、そのようなアプローチは素早く解を見つけることができ、そのことが保証される。
論文 参考訳(メタデータ) (2022-03-02T15:55:10Z) - Abstract Reasoning via Logic-guided Generation [65.92805601327649]
抽象的推論、すなわち、与えられた観測から複雑なパターンを推測することは、人工知能の中心的な構成要素である。
本稿では,後者のアプローチの枠組みを設計し,人工知能と人間の知能のギャップを埋めることを目的とする。
本稿では,提案する論理の最適化問題として,抽象的推論を削減した新しい生成型DNNフレームワークであるLoGeを提案する。
論文 参考訳(メタデータ) (2021-07-22T07:28:24Z) - Variational Causal Networks: Approximate Bayesian Inference over Causal
Structures [132.74509389517203]
離散DAG空間上の自己回帰分布をモデル化したパラメトリック変分族を導入する。
実験では,提案した変分後部が真の後部を良好に近似できることを示した。
論文 参考訳(メタデータ) (2021-06-14T17:52:49Z) - Logic Embeddings for Complex Query Answering [56.25151854231117]
skolemisationを用いて効率的なクエリのための存在変数を排除する、複雑なクエリを組み込む新しいアプローチであるlogic embeddedsを提案する。
論理組込みは,大規模で不完全な知識グラフ上でのクエリ応答において競争的に高速かつ正確であり,否定的問合せよりも優れており,特に回答の不確かさのモデリングが向上している。
論文 参考訳(メタデータ) (2021-02-28T07:52:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。