Strong Admissibility, a Tractable Algorithmic Approach

Martin Caminada*, Sri Harikrishnan

*Corresponding author for this work

Publication: Contribution to conferenceConference paper

29 Downloads (Pure)

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
Original languageEnglish
Publication statusPublished - 16 Jul 2022
Externally publishedYes
EventSAFA’22: Fourth International Workshop on Systems and Algorithms for Formal Argumentation 2022 - Cardif, Cardif, United Kingdom
Duration: 13 Sept 202213 Sept 2022
http://safa2022.argumentationcompetition.org/

Conference

ConferenceSAFA’22
Country/TerritoryUnited Kingdom
CityCardif
Period13/09/2213/09/22
Internet address

Keywords

  • strong admissibility, polynomial algorithms

Cite this