Monday, November 25, 2013 at 16h30 in Celestijnenlaan 200A (auditorium 00.225)
The Complexity Landscape of Recursive Definitions Involving Generalized Atoms in Answer Set Programming
by Wolfgang Faber (University of Huddersfield, UK)
In recent years, Answer Set Programming (ASP), logic programming under the stable model or answer set semantics, has seen several extensions by generalizing the notion of an atom in these programs: be it aggregate atoms, HEX atoms, generalized quantifiers, or abstract constraints, the idea is to have more complicated satisfaction patterns in the lattice of Herbrand interpretations than traditional, simple atoms. In this talk, we will first provide an introduction to Answer Set Programming, subsequently focussing on the extension by generalized atoms. It is known that allowing for generalized atoms can increase the complexity of reasoning tasks, even if the evaluation of the generalized atoms is polynomial. We present recent results that map the precise boundary of this complexity gap under the two main semantics considered in the literature. We also discuss several practical implications of these results.