Strategic Argumentation is NP-Complete

被引：12
作者：
Governatori, G.
Olivieri, F.
Scannapieco, S.
Rotolo, A.
Cristani, M.
机构：
来源：
21ST EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE (ECAI 2014) | 2014年 / 263卷
关键词：
DEFEASIBLE LOGIC;
D O I：
10.3233/978-1-61499-419-0-399
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We study the complexity of the Strategic Argumentation Problem for 2-player dialogue games where a player should decide what move (set of rules) to play at each turn in order to prove (disprove) a given thesis. We show that this is an NP-complete problem.
引用
收藏
页码：399 / 404
页数：6
相关论文
共 19 条
[1]  
Antoniou G, 2000, FRONT ARTIF INTEL AP, V54, P459
[2]  
Antoniou G., 2001, ACM Transactions on Computational Logic, V2, P255, DOI [10.1145/371316.371517, DOI 10.1145/371316.371517]
[3]   An Inclusion Theorem for Defeasible Logics [J].
Billington, David ;
Antoniou, Grigoris ;
Governatori, Guido ;
Maher, Michael .
ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2010, 12 (01)
[4]   Argumentation semantics for defeasible logic [J].
Governatori, G ;
Maher, MJ ;
Antoniou, G ;
Billington, D .
JOURNAL OF LOGIC AND COMPUTATION, 2004, 14 (05) :675-702
[5]  
Governatori G., 2012, ABS12065833 CORR, Vabs/1206.5833
[6]  
Governatori G., 2013, STRATEGIC ARGUMENTAT, Vabs
[7]   BIO logical agents: Norms, beliefs, intentions in defeasible logic [J].
Governatori, Guido ;
Rotolo, Antonino .
AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS, 2008, 17 (01) :36-69
[8]  
Grossi Davide, 2013, P 23 INT JOINT C ART, P143
[9]   Propositional defeasible logic has linear complexity [J].
Maher, MJ .
THEORY AND PRACTICE OF LOGIC PROGRAMMING, 2001, 1 :691-711
[10]   A Game-Theoretic Measure of Argument Strength for Abstract Argumentation [J].
Matt, Paul-Amaury ;
Toni, Francesca .
LOGICS IN ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2008, 5293 :285-297
12