On Strong Equivalence Notions in Logic Programming and Abstract Argumentation
Giovanni Buraglio, Wolfgang Dvořák, Stefan Woltran · 2026
Read On Strong Equivalence Notions in Logic Programming and Abstract Argumentation by Giovanni Buraglio, Wolfgang Dvořák, Stefan Woltran (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14721.txt.
Introduction
Buraglio, Dvorak and Woltran investigate strong equivalence in logic programming and abstract argumentation. Strong equivalence lets one knowledge base replace another without changing results in any context. The two fields align in static settings. The alignment breaks in dynamic contexts because their notions of update differ. The authors introduce a new notion for logic programs. It preserves this property under translation to Dung-style and claim-augmented argumentation frameworks. Compatibility across the formalisms is thus restored.
Catalog record
| CREATOR | Giovanni Buraglio, Wolfgang Dvořák, Stefan Woltran |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105320 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14721
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Strong Equivalence Notions in Logic Programming and Abstract Argumentation Giovanni Buraglio, Wolfgang Dvořák, Stefan Woltran Abstract Strong equivalence between knowledge bases ensures the possibility of replacing one with the other without affecting reasoning outcomes, in any given context. This makes it a crucial property in nonmonotonic formalisms. In particular, the fields of logic programming and abstract argumentation provide primary examples in which this property has been subject to vast investigations. However, while (classes of) logic programs and abstract argumentation frameworks are known to be semantically equivalent in static settings, this alignment breaks in dynamic contexts due to differing notions of update. As a result, strong equivalence does not always carry over from one formalism to the other. In this paper, we carefully investigate this discrepancy and introduce a new notion of strong equivalence for logic programs. Our approach preserves strong equivalence under translation between certain classes of logic programs and both Dung-style and claim-augmented argumentation frameworks, thus restoring compatibility across these formalisms. 1 Introduction In the field of Knowledge Representation and Reasoning, the concept of equivalence between knowledge bases has been the subject of extensive studies. A primary motivation behind this research is the potential to exploit the equivalence between two knowledge bases to achieve a compact representation of the same information. Furthermore, the possibility to substitute a specific component of a given knowledge base \mathcal{K} with an equivalent yet simplified alternative has been shown to ease the computational cost of reasoning over \mathcal{K} . While this advantageous behavior can be taken for granted in monotonic formalisms (e.g. classical logic), it is usually not the case in non-monotonic ones. For this, the notion of strong equivalence has been introduced in a dynamic environment, to capture the idea of equivalence under any possible update [ 4 , 11 , 16 , 17 , 19 , 20 ] . In this paper, we consider two families of non-monotonic formalisms, namely logic programming and abstract argumentation. Logic programming is a declarative programming paradigm where a reasoning problem is specified by means of a so-called logic program (LP). This consists of a set of inference rules made of atoms, possibly preceded by a negation-as-failure operator. Negative literals are assumed to be true as long as their corresponding positive atom cannot be proven to hold. Abstract argumentation is a sub-field of symbolic Artificial Intelligence [ 1 ] that offers formal approaches to represent and reason over situations where conflicting information is present. An argumentative scenario is specified by means of an abstract argumentation framework, which is a directed graph where nodes represent arguments and edges their relation. The starting point in the field is the seminal work of Dung [ 8 ] , where argumentation frameworks, which we call Dung-style AFs, contain only a relation of attack. Several semantics have been proposed for both of these formalisms, with the common purpose of extracting solutions for the given program or argumentation framework. These are respectively sets of atoms that satisfy each rule in the program (called answer-sets ), and sets of arguments that are able to defend themselves against possible counter-arguments (called extensions ). In this work, we focus on the stable model semantics for LPs [ 12 ] and the stable semantics for AFs [ 8 ] . Previous work has introduced a one-to-one mapping between Dung-style AFs and (a resticted class of) LPs under the stable model semantics [ 5 , 8 ] . Any problem can be either specified via a program P or an abstract argumentation framework F in such a way that their solutions coincide. Later, this mapping has been extended to a wider class of LPs and generalizations of Dung-style AFs, such as claim-augmented AFs [ 10 ] . Thus, equivalent LPs correspond to equivalent AFs. However, such a semantic correspondence does not necessarily carry over to dynamic contexts, where strong equivalence is required. It is possible for two logic programs that are strongly equivalent to induce argumentation frameworks that are not, due to the incongruous notions of update (or expansion) in the two realms. To acknowledge such mismatch, consider the following example: Example 1 Two suspects, X and Y, are under investigation for a murder proven by forensic analysis to have been committed by a single person. While questioning possible witnesses, the detective learns that X and Y have been seen far away from the crime scene at the time of the murder, and the case remains unsolved. We model the detective’s knowledge via an Dung-style AF and an LP as follows: F x y a P= \{x\leftarrow\mathtt{not}\,y,\mathtt{not}\,a., y\leftarrow\mathtt{not}\,x,\mathtt{not}\,a., a\leftarrow.\} where a means “has an alibi" and x (resp. y ) means “X (resp. Y) is the murder". Later, another witness testifies that Z was drunk ( d ) on the same night, falsifying the suspects’ alibi. This information update is captured via: F^{\prime} a d P^{\prime}=\{a\leftarrow\mathtt{not}\,d.,\;d\leftarrow.\} In accordance with equivalence results between logic programs and argumentation frameworks, the two ways of modeling our knowledge base are consistent with each other when taken individually. However, this does not happen when they are combined. Incorporating the second pair of knowledge bases ( F^{\prime} and P^{\prime} ) into the first one (resp. F and P ) yields different result: in the case of F and F^{\prime} , their union returns the expected result in the form of two possible extensions \{d,x\} and \{d,y\} . Indeed, since the witness Z was drunk, this is compatible with either X or Y being the murder. On the other hand, the union of the two logic programs P and P^{\prime} yields an unexpected prediction: the alibi ‘ a\leftarrow ’ is not overwritten by Z being drunk ‘ d\leftarrow ’, leaving \{a,d\} as the only possible solution. Updating an existing program by simply adding rules may yield unexpected outcomes. Facts (e.g. ‘ a\leftarrow ’ in P ) cannot be overwritten by incoming information, while their corresponding arguments (e.g. a\in F ) can. This behavior of LPs is fundamentally in contrast with the way in which non-monotonicity is encoded in abstract argumentation: an argument can always be attacked by new ones. In this work, we carefully analyze the relationship between logic programming and abstract argumentation, with a particular interest in dynamic contexts. As a first step, we recall and extend equivalence results for classes of logic programs and abstract argumentation frameworks. Subsequently, motivated by the mismatch above, we introduce a novel notion of update for a restricted class of LPs, called Rule Refinement, that resolves the issue by mimicking precisely the existing notion for Dung-style AFs. We further extend Rule Refinement to the wider class of atomic logic programs (where no positive literal occurs in the body), which is shown to capture strong equivalence in claim-augmented AFs. 2 Preliminaries Logic Programming We consider normal logic programs with negation-as-failure \mathtt{not} , consisting of rules r of the form ‘ n:c\leftarrow a_{1},\dots,a_{k},\mathtt{not}\,b_{1},\dots,\mathtt{not}\,b_{m}. ’ read as ‘ c if a_{1} and \dots and a_{k} and \mathtt{not}\,b_{1} and \dots and \mathtt{not}\,b_{m} ’. Here, n\in\mathbb{N} is the identifier of the rule r in the program; we refer to it with id(r)=n . Further, a_{i} , b_{i} and c are ordinary atoms; \mathcal{L}(P) is the set of all atoms occurring in P