Strong admissibility, a tractable algorithmic approach

Caminada, Martin ORCID: https://orcid.org/0000-0002-7498-0238 and Harikrishnan, Meenakshi 2022. Strong admissibility, a tractable algorithmic approach. Presented at: Fourth International Workshop on Systems and Algorithms for Formal Argumentation, Cardiff, Wales, 13 September 2022. Proceedings of the Fourth International Workshop on Systems and Algorithms for Formal Argumentation. CEUR, pp. 33-44.

Preview

PDF (SAFA workshop paper) - Published Version Available under License Creative Commons Attribution. Download (1MB) | Preview

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.

Item Type:	Conference or Workshop Item (Paper)
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	CEUR
Date of First Compliant Deposit:	8 December 2022
Date of Acceptance:	2022
Last Modified:	26 Jan 2023 12:15
URI:	https://orca.cardiff.ac.uk/id/eprint/154756

Actions (repository staff only)

Edit Item