The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation
We study the computational complexity of problems that arise in abstract argumentation in the context of dynamic argumentation, minimal change, and aggregation. In particular, we consider the following problems where always an argumentation framework F and a small positive integer k are given. - The Repair problem asks whether a given set of arguments can be modified into an extension by at most k elementary changes (i.e., the extension is of distance k from the given set). - The Adjust problem asks whether a given extension can be modified by at most k elementary changes into an extension that contains a specified argument. - The Center problem asks whether, given two extensions of distance k, whether there is a "center" extension that is a distance at most (k-1) from both given extensions. We study these problems in the framework of parameterized complexity, and take the distance k as the parameter. Our results covers several different semantics, including admissible, complete, preferred, semi-stable and stable semantics.
Code (0)
등록된 구현이 없습니다.
Tasks
Abstract ArgumentationSimilar Papers 제목 키워드 기반
Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation
In this paper, we explore the issue of inconsistency handling over prioritized knowledge bases (KBs), which consist of an ontology, a set of facts, and a priority relation between conflicting facts. In the database setti…
Abstract ArgumentationAn Imprecise Probability Approach for Abstract Argumentation based on Credal Sets
Some abstract argumentation approaches consider that arguments have a degree of uncertainty, which impacts on the degree of uncertainty of the extensions obtained from a abstract argumentation framework (AAF) under a sem…
Abstract ArgumentationDecision MakingCounting Complexity for Reasoning in Abstract Argumentation
In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a…
Abstract ArgumentationDiversity of Extensions in Abstract Argumentation
Argumentation is an important topic of AI for modelling and reasoning about arguments. In abstract argumentation, we consider directed graphs, so-called argumentation frameworks (AF), that express conflicts between argum…
Simple and precise static analysis of untrusted linux kernel extensions
Extended Berkeley Packet Filter (eBPF) is a Linux subsystem that allows safely executing untrusted user-defined extensions inside the kernel. It relies on static analysis to protect the kernel against buggy and malicious…