## Abstract

Much like admissibility is the key concept underlying preferred semantics, strong admissibility is the key concept

underlying grounded semantics, as membership of a strongly admissible set is sufficient to show membership of the grounded

extension. As such, strongly admissible sets and labellings can be used as an explanation of membership of the grounded

extension, as is for instance done in some of the proof procedures for grounded semantics. 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.

underlying grounded semantics, as membership of a strongly admissible set is sufficient to show membership of the grounded

extension. As such, strongly admissible sets and labellings can be used as an explanation of membership of the grounded

extension, as is for instance done in some of the proof procedures for grounded semantics. 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.

Originalsprache | Englisch |
---|---|

Fachzeitschrift | Argument and Computation |

DOIs | |

Publikationsstatus | Elektronische Veröffentlichung vor Drucklegung - 2024 |