On the Equivalence between Logic Programming and SETAF
This work provides a theoretical bridge between logic programming and argumentation frameworks, enhancing understanding of their interrelationships for researchers in computational logic and AI.
The paper establishes a formal equivalence between Normal Logic Programs (NLPs) and SETAFs (sets of attacking arguments), showing pairwise semantic equivalence and structural equivalence for a subclass called RFALPs, with transformations proven confluent.
A framework with sets of attacking arguments (SETAF) is an extension of the well-known Dung's Abstract Argumentation Frameworks (AAFs) that allows joint attacks on arguments. In this paper, we provide a translation from Normal Logic Programs (NLPs) to SETAFs and vice versa, from SETAFs to NLPs. We show that there is pairwise equivalence between their semantics, including the equivalence between L-stable and semi-stable semantics. Furthermore, for a class of NLPs called Redundancy-Free Atomic Logic Programs (RFALPs), there is also a structural equivalence as these back-and-forth translations are each other's inverse. Then, we show that RFALPs are as expressive as NLPs by transforming any NLP into an equivalent RFALP through a series of program transformations already known in the literature. We also show that these program transformations are confluent, meaning that every NLP will be transformed into a unique RFALP. The results presented in this paper enhance our understanding that NLPs and SETAFs are essentially the same formalism. Under consideration in Theory and Practice of Logic Programming (TPLP).