Abstract
In the current paper, we present two polynomial algorithms for constructing relatively small strongly
admissible labellings, with associated min-max numberings, for a particular argument. These labellings
can be used as relatively small explanations for the argument’s membership of the grounded extension.
Although our algorithms are not guaranteed to yield an absolute minimal strongly admissible labelling
for the argument (as doing so would have implied an exponential complexity), our best performing
algorithm yields results that are only marginally larger. Moreover, the runtime of this algorithm is
an order of magnitude smaller than that of the existing approach for computing an absolute minimal
strongly admissible labelling for a particular argument. As such, we believe that our algorithms can
be of practical value in situations where the aim is to construct a minimal or near-minimal strongly
admissible labelling in a time-efficient way
admissible labellings, with associated min-max numberings, for a particular argument. These labellings
can be used as relatively small explanations for the argument’s membership of the grounded extension.
Although our algorithms are not guaranteed to yield an absolute minimal strongly admissible labelling
for the argument (as doing so would have implied an exponential complexity), our best performing
algorithm yields results that are only marginally larger. Moreover, the runtime of this algorithm is
an order of magnitude smaller than that of the existing approach for computing an absolute minimal
strongly admissible labelling for a particular argument. As such, we believe that our algorithms can
be of practical value in situations where the aim is to construct a minimal or near-minimal strongly
admissible labelling in a time-efficient way
Original language | English |
---|---|
Publication status | Published - 16 Jul 2022 |
Externally published | Yes |
Event | SAFA’22: Fourth International Workshop on Systems and Algorithms for Formal Argumentation 2022 - Cardif, Cardif, United Kingdom Duration: 13 Sept 2022 → 13 Sept 2022 http://safa2022.argumentationcompetition.org/ |
Conference
Conference | SAFA’22 |
---|---|
Country/Territory | United Kingdom |
City | Cardif |
Period | 13/09/22 → 13/09/22 |
Internet address |
Keywords
- strong admissibility, polynomial algorithms