In an abstract argumentation framework, there are often multiple plausible ways to evaluate (or label) the status of each argument as accepted, rejected, or undecided. But often there exists a critical set of arguments whose status is sufficient to determine uniquely the status of every other argument. Once an agent has decided its position on a critical set of arguments, then essentially the entire frame-work has been evaluated. Likewise, once a group, e.g. a jury, agrees on the status of a critical set of arguments, all of their different views over all other arguments are resolved. Thus, critical sets of arguments are important both for efficient evaluation by individual agents and for collective agreement by groups of such. To exploit this idea in practice, however, a number of computational questions must be considered. In particular, how much computational effort is needed to verify that a set is, indeed, a critical set or a minimal critical set. In this paper we determine exact bounds on the computational complexity of these and related questions. In addition we provide similar analyses of issues: a concept closely related to critical set and derived in terms of (equivalence) classes of arguments related through “common” labelling behaviours.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com