Paper accepted to Journal of Artificial Intelligence Research

20.8.2019
The work proposes novel form of synthesis in the context of abstract argumentation, a topical area of AI research, and both analysis the complexity of the problem and developed first algorithm solutions for the problem based on Boolean satisfiability (SAT) solvers.

The paper Synthesizing Argumentation Frameworks from Examples co-authored by Andreas Niskanen and Matti Järvisalo of the Constraint Reasoning and Optimization group together with  Johannes P. Wallner (Vienna University of Technology, Austria) has been accepted for publication in Journal of Artificial Intelligence Research (JAIR), a leading journal in the general area of artificial intelligence research. The article considerably extends a conference paper from 2016 that received the Runner-up Best Student Paper Award at ECAI 2016, 22nd European Conference on Artificial Intelligence.

Abstract of the accepted JAIR article:

Argumentation is today a topical area of artificial intelligence (AI) research. Abstract argumentation, with argumentation frameworks (AFs) as the underlying knowledge representation formalism, is a central viewpoint to argumentation in AI. Indeed, from the perspective of AI and computer science, understanding computational and representational aspects of AFs is key in the study of  argumentation. 

Realizability of AFs has been recently proposed as a central notion for  analyzing the expressive  power of AFs under different semantics. In this work, we propose and study the AF synthesis problem as a natural extension of realizability,  addressing some of the shortcomings arising from the relatively stringent definition of realizability. In particular, realizability gives means of establishing exact conditions on when a given collection of  subsets of arguments has an AF with exactly the given collection as its set of extensions under a specific argumentation semantics. However, in various settings within the study of dynamics of argumentation---including  revision and aggregation of AFs---non-realizability can naturally occur. To accommodate such settings, our notion of AF synthesis seeks to construct, or synthesize, AFs that are semantically closest to the  knowledge at hand even when no AFs exactlyrepresenting the knowledge exist. Going beyond defining the AF synthesis problem, we study both theoretical and practical aspects of the problem. In particular, we (i) prove NP-completeness of AF synthesis under several semantics, (ii) study basic properties of the problem in relation to realizability,  (iii) develop algorithmic solutions to NP-hard AF synthesis using the constraint optimization paradigms of maximum satisfiability and answer set programming,  (iv) empirically evaluate our algorithms on different forms of AF synthesis instances, as well as (v) discuss variants and generalizations of AF synthesis.