On Abstracting over the Irrelevant in Answer Set Programming

Generalization is an important ability that allows humans to tackle complex problems by identifying common problem structures and omitting irrelevant details. Whereas such ability comes naturally to humans, it has proved challenging to establish within AI systems. Although different research communities have tackled this challenge, their focus has usually been set on developing efficient algorithms for concrete problems, and a general theoretical understanding of the generalization ability is still lacking. In the context of Answer Set Programming (ASP), a well-established knowledge representation and reasoning paradigm for solving highly combinatorial search problems, research on generalization has primarily focused on forgetting and projection, two related operations that aim at the omission of irrelevant details, while abstraction, an operation that aims at providing a higher-level view on the common solution and problem structures, has largely been overlooked. In this paper, we develop the theoretical foundation for generalized reasoning through abstraction in ASP, focusing on the notion of abstraction through vocabulary clustering. We formally characterize when abstraction is possible, semantically define the desired result, investigate syntactic operators to obtain such abstractions, and study the computational complexity of this problem.