Characterizing Realizability in Abstract Argumentation
This work addresses a foundational problem in knowledge representation for AI, providing a modular and extensible solution that is incremental in nature.
The paper tackles the problem of realizability in abstract argumentation, introducing a general framework and algorithm to decide if a given set of interpretations can be realized by a knowledge base for various formalisms and semantics, with implementation in answer set programming yielding novel expressiveness results.
Realizability for knowledge representation formalisms studies the following question: given a semantics and a set of interpretations, is there a knowledge base whose semantics coincides exactly with the given interpretation set? We introduce a general framework for analyzing realizability in abstract dialectical frameworks (ADFs) and various of its subclasses. In particular, the framework applies to Dung argumentation frameworks, SETAFs by Nielsen and Parsons, and bipolar ADFs. We present a uniform characterization method for the admissible, complete, preferred and model/stable semantics. We employ this method to devise an algorithm that decides realizability for the mentioned formalisms and semantics; moreover the algorithm allows for constructing a desired knowledge base whenever one exists. The algorithm is built in a modular way and thus easily extensible to new formalisms and semantics. We have also implemented our approach in answer set programming, and used the implementation to obtain several novel results on the relative expressiveness of the abovementioned formalisms.