arXiv:0812.1462v1 [cs.AI] 8 Dec 2008

# Logic Programs With Propositional Connectives And Aggregates

Paolo Ferraris Google Inc 1600 Anphitheatre Pkwy Mountain View CA 94043, USA
otto@cs.utexas.edu October 23, 2018

## Abstract 1

Answer set programming (ASP) is a logic programming paradigm that can be used to solve complex combinatorial search problems. Aggregates are an ASP construct that plays an important role in many applications. Defining a satisfactory semantics of aggregates turned out to be a difficult problem, and in this paper we propose a new approach, based on an analogy between aggregates and propositional connectives. First, we extend the definition of an answer set/stable model to cover arbitrary propositional theories; then we define aggregates on top of them both as primitive constructs and as abbreviations for formulas. Our definition of an aggregate combines expressiveness and simplicity, and it inherits many theorems about programs with nested expressions, such as theorems about strong equivalence and splitting.

## 1 Introduction

Answer set programming (ASP) is a logic programming paradigm that can be used to solve complex combinatorial search problems ([Marek and Truszczy´nski, 1999]), ([Niemel¨a, 1999]). ASP is based on the stable model semantics [Gelfond and Lifschitz, 1988] for logic programs: programming in ASP consists in writing a logic program whose stable models (also called answer sets) represent the solution to our problem. ASP
has been used, for instance, in planning [Dimopoulos *et al.*, 1997; Lifschitz, 1999],
model checking [Liu *et al.*, 1998; Heljanko and Niemel¨a, 2001], product configuration [Soininen and Niemel¨a, 1998], logical cryptanalysis [Hietalahti *et al.*, 2000],
workflow specification [Trajcevski *et al.*, 2000; Koksal *et al.*, 2001], reasoning about