Computational complexity of flat and generic Assumption-Based Argumentation, with and without probabilities
Computational complexity of flat and generic Assumption-Based Argumentation, with and without probabilities
复制标题
平面和通用的基于假设的论证的计算复杂性，有或没有概率
DOI：
10.1016/j.artint.2020.103449
复制
发表时间：
2021
影响因子：
14.4
通讯作者：
Cyras K
中科院分区：
文献类型：
--
作者：
Cyras K
近年来，带有概率信息的抽象推理在论证中引起了人们的广泛关注，并提出了概率抽象论证（PAA）、概率双极论证（PBA）和概率结构化论证（PSA）的形式化。这些基础性的进展得到了补充，一些方法的复杂性的研究PAA和PBA，但不是PSA。我们研究的复杂性，现有形式的PSA，即概率假设为基础的论证（PABA），一个强大的，实现的形式主义，其中包括几种形式的PAA和其他形式的PSA。具体而言，我们建立成员资格（一般上限）和完整性（实例化的下限）的推理在PABA类FP# P（与一个#P-预言计数的NP问题的解决方案的功能）就新引入的概率验证，轻信和怀疑接受功能的问题下几个阿坝语义。作为建立PABA复杂性结果所需的副产品，我们提供了一个全面的阿坝复杂性景观（平面和通用，可能是非平面阿坝）的经典决策问题的验证，存在，轻信和怀疑接受这些阿坝语义。
Abstract Reasoning with probabilistic information has recently attracted considerable attention in argumentation, and formalisms of Probabilistic Abstract Argumentation (PAA), Probabilistic Bipolar Argumentation (PBA) and Probabilistic Structured Argumentation (PSA) have been proposed. These foundational advances have been complemented with investigations on the complexity of some approaches to PAA and PBA, but not to PSA. We study the complexity of an existing form of PSA, namely Probabilistic Assumption-Based Argumentation (PABA), a powerful, implemented formalism which subsumes several forms of PAA and other forms of PSA. Specifically, we establish membership (general upper bounds) and completeness (instantiated lower bounds) of reasoning in PABA for the class FP# P (of functions with a# P-oracle for counting the solutions of an NP problem) with respect to newly introduced probabilistic verification, credulous and sceptical acceptance function problems under several ABA semantics. As a by-product necessary to establish PABA complexity results, we provide a comprehensive picture of the ABA complexity landscape (for both flat and generic, possibly non-flat ABA) for the classical decision problems of verification, existence, credulous and sceptical acceptance under those ABA semantics.
登录
查看更多内容
基于假设的论证：争议、解释、偏好。
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
K. Čyras;Xiuyi Fan;Claudia Schulz;Francesca Toni
通讯作者：
Francesca Toni
DOI：
--
发表时间：
2003
期刊：
影响因子：
--
作者：
R. Haenni;J. Kohlas;Norbert Lehmann
通讯作者：
Norbert Lehmann
ABAplus：抽象和结构化论证中的攻击逆转与偏好
DOI：
--
发表时间：
2017
期刊：
Prima
影响因子：
--
作者：
Ziyi Bao;K. Čyras;Francesca Toni
通讯作者：
Francesca Toni
DOI：
10.1016/j.ijar.2013.09.002
发表时间：
2014
期刊：
Int. J. Approx. Reason.
影响因子：
--
作者：
A. Hunter
通讯作者：
A. Hunter
影响因子：
3.9
作者：
Polberg, Sylwia;Hunter, Anthony
通讯作者：
Hunter, Anthony