Wolfgang Faber

KR Conference 2025 Conference Paper

Non-deterministic Action Reversibility: Complexity Results

• Jakub Med
• Michael Morak
• Lukáš Chrpa
• Wolfgang Faber

With the recent interest in the reversibility of action effects, i. e. , whether the effects of the action can be undone by applying other actions, the question arose how hard it is to reverse an action in a non-deterministic domain. With the use of phi-reversibility, the paper investigates the computational complexity of weak and strong non-deterministic action reversibility in fully observable non-deterministic domains, showing PSPACE-completeness for all weak variants in question and EXP-hardness and EXP, or NEXP memberships for strong variants.

AAAI Conference 2023 Conference Paper

Evaluating Epistemic Logic Programs via Answer Set Programming with Quantifiers

• Wolfgang Faber
• Michael Morak

In this paper we introduce a simple way to evaluate epistemic logic programs by means of answer set programming with quantifiers, a recently proposed extension of answer set programming. The method can easily be adapted for most of the many semantics that were proposed for epistemic logic programs. We evaluate the proposed transformation on existing benchmarks using a recently proposed solver for answer set programming with quantifiers, which relies on QBF solvers.

AIJ Journal 2021 Journal Article

Paracoherent answer set computation

• Giovanni Amendola
• Carmine Dodaro
• Wolfgang Faber
• Francesco Ricca

Answer Set Programming (ASP) is a well-established paradigm for declarative programming and nonmonotonic reasoning. ASP allows for flexible modeling using rules. ASP rules induce a set of intended models called answer sets. Incoherence, the non-existence of answer sets, is therefore a feature of ASP, indicating that the rules admit no intended models. However, this feature can also be problematic in certain circumstances: errors that cause incoherence are notoriously difficult to debug, and query answering will not provide any meaningful answers for incoherent programs. Paracoherent semantics have been suggested as a remedy. They extend the classical notion of answer sets to draw meaningful conclusions also from incoherent programs. However, paracoherent semantics have essentially been inapplicable in practice, due to the lack of efficient algorithms and implementations. In this paper, this lack is addressed, and several different algorithms to compute semi-stable and semi-equilibrium models are proposed and implemented within an answer set solving framework. A key role in the framework is played by syntactic program transformations that allow for characterizing paracoherent semantics in terms of the answer sets of transformed programs. Apart from existing transformations from the literature, a novel transformation is also proposed, which provides an alternative characterization of paracoherent semantics in terms of (extended) externally supported models. Notably, the new transformation is more compact than the existing ones, and brings performance benefits. An extensive empirical performance comparison among the algorithms on benchmarks from ASP competitions and a real-world use case is given as well. It shows not only that the methods developed in this paper lead to practically effective systems, but also show a clear advantage of the methods that rely on (extended) externally supported models.

KR Conference 2021 Short Paper

Universal and Uniform Action Reversibility

• Lukáš Chrpa
• Wolfgang Faber
• Michael Morak

The problem of action reversibility studies whether effects of a given action can be reversed (or undone) by a sequence of (other) actions. For example, actions whose effects can be reversed cannot lead to dead-ends. In the usual settings, the problem of action reversibility is PSPACE-complete, that is, as hard as deciding plan existence. In this paper, we focus on subclasses of the action reversibility problem, universal and uniform action reversibility, where the former considers all states in which the action in question is applicable, while the latter requires a single reverting action sequence, independent of the considered states. Specifically, we study the relations between projection abstractions and the subclasses of the action reversibility problem and we show that universal uniform reversibility of a given action can be decided on projection consisting of only the variables present in the schema of the action in question.

KR Conference 2020 Conference Paper

On the Reversibility of Actions in Planning

• Michael Morak
• Lukas Chrpa
• Wolfgang Faber
• Daniel Fišer

Checking whether action effects can be undone is an important question for determining, for instance, whether a planning task has dead-ends. In this paper, we investigate the reversibility of actions, that is, when the effects of an action can be reverted by applying other actions, in order to return to the original state. We propose a broad notion of reversibility that generalizes previously defined versions and investigate interesting properties and relevant restrictions. In particular, we propose the concept of uniform reversibility that guarantees that an action can be reverted independently of the state in which the action was applied, using a so-called reverse plan. In addition, we perform an in-depth investigation of the computational complexity of deciding action reversibility. We show that reversibility checking with polynomial-length reverse plans is harder than polynomial-length planning and that, in case of unrestricted plan length, the PSPACE-hardness of planning is inherited. In order to deal with the high complexity of solving these tasks, we then propose several incomplete algorithms that may be used to compute reverse plans for a relevant subset of states.

AAAI Conference 2019 Conference Paper

Strong Equivalence for Epistemic Logic Programs Made Easy

• Wolfgang Faber
• Michael Morak
• Stefan Woltran

Epistemic Logic Programs (ELPs), that is, Answer Set Programming (ASP) extended with epistemic operators, have received renewed interest in recent years, which led to a flurry of new research, as well as efficient solvers. An important question is under which conditions a sub-program can be replaced by another one without changing the meaning, in any context. This problem is known as strong equivalence, and is well-studied for ASP. For ELPs, this question has been approached by embedding them into epistemic extensions of equilibrium logics. In this paper, we consider a simpler, more direct characterization that is directly applicable to the language used in state-of-the-art ELP solvers. This also allows us to give tight complexity bounds, showing that strong equivalence for ELPs remains coNP-complete, as for ASP. We further use our results to provide syntactic characterizations for tautological rules and rule subsumption for ELPs.

AAAI Conference 2018 Conference Paper

Externally Supported Models for Efficient Computation of Paracoherent Answer Sets

• Giovanni Amendola
• Carmine Dodaro
• Wolfgang Faber
• Francesco Ricca

Answer Set Programming (ASP) is a well-established formalism for nonmonotonic reasoning. While incoherence, the non-existence of answer sets for some programs, is an important feature of ASP, it has frequently been criticised and indeed has some disadvantages, especially for query answering. Paracoherent semantics have been suggested as a remedy, which extend the classical notion of answer sets to draw meaningful conclusions also from incoherent programs. In this paper we present an alternative characterization of the two major paracoherent semantics in terms of (extended) externally supported models. This definition uses a transformation of ASP programs that is more parsimonious than the classic epistemic transformation used in recent implementations. A performance comparison carried out on benchmarks from ASP competitions shows that the usage of the new transformation brings about performance improvements that are independent of the underlying algorithms.

AAAI Conference 2017 Conference Paper

On the Computation of Paracoherent Answer Sets

• Giovanni Amendola
• Carmine Dodaro
• Wolfgang Faber
• Nicola Leone
• Francesco Ricca

Answer Set Programming (ASP) is a well-established formalism for nonmonotonic reasoning. An ASP program can have no answer set due to cyclic default negation. In this case, it is not possible to draw any conclusion, even if this is not intended. Recently, several paracoherent semantics have been proposed that address this issue, and several potential applications for these semantics have been identified. However, paracoherent semantics have essentially been inapplicable in practice, due to the lack of efficient algorithms and implementations. In this paper, this lack is addressed, and several different algorithms to compute semi-stable and semi-equilibrium models are proposed and implemented into an answer set solving framework. An empirical performance comparison among the new algorithms on benchmarks from ASP competitions is given as well.

AAAI Conference 2016 Conference Paper

Boolean Functions with Ordered Domains in Answer Set Programming

• Mario Alviano
• Wolfgang Faber
• Hannes Strass

Boolean functions in Answer Set Programming have proven a useful modelling tool. They are usually specified by means of aggregates or external atoms. A crucial step in computing answer sets for logic programs containing Boolean functions is verifying whether partial interpretations satisfy a Boolean function for all possible values of its undefined atoms. In this paper, we develop a new methodology for showing when such checks can be done in deterministic polynomial time. This provides a unifying view on all currently known polynomialtime decidability results, and furthermore identifies promising new classes that go well beyond the state of the art. Our main technique consists of using an ordering on the atoms to significantly reduce the necessary number of model checks. For many standard aggregates, we show how this ordering can be automatically obtained.

IJCAI Conference 2016 Conference Paper

From Non-Convex Aggregates to Monotone Aggregates in ASP

• Mario Alviano
• Wolfgang Faber
• Martin Gebser

In answer set programming, knowledge involving sets of objects collectively is naturally represented by aggregates, which are rewritten into simpler forms known as monotone aggregates by current implementations. However, there is a complexity gap between general and monotone aggregates. In this paper, this gap is filled by means of a polynomial, faithful, and modular translation function, which can introduce disjunction in rule heads. The translation function is now part of the recent version 4. 5 of the grounder Gringo. This paper focuses on the key points of the translation function, and in particular on the mapping from non-convex sums to monotone sums.

IJCAI Conference 2015 Conference Paper

Stable Model Semantics of Abstract Dialectical Frameworks Revisited: A Logic Programming Perspective

• Mario Alviano
• Wolfgang Faber

This paper relates two extensively studied formalisms: abstract dialectical frameworks and logic programs with generalized atoms or similar constructs. While the syntactic similarity is easy to see, also a strong relation between various stable model semantics proposed for these formalisms is shown by means of a unifying framework in which these semantics are restated in terms of program reducts and an immediate consequence operator, where program reducts have only minimal differences. This approach has advantages for both formalisms, as for example implemented systems for one formalism are usable for the other, and properties such as computational complexity do not have to be rediscovered. As a first, concrete result of this kind, one stable model semantics based on program reducts and subset-minimality that reached a reasonable consensus for logic programs with generalized atoms provides a novel, alternative semantics for abstract dialectical frameworks.

AAAI Conference 2013 Conference Paper

Abstract Preference Frameworks — a Unifying Perspective on Separability and Strong Equivalence

• Wolfgang Faber
• Mirosław Truszczyński
• Stefan Woltran

We introduce abstract preference frameworks to study general properties common across a variety of preference formalisms. In particular, we study strong equivalence in preference formalisms and their separability. We identify abstract postulates on preference frameworks, satisfied by most of the currently studied preference formalisms, that lead to characterizations of both properties of interest.

AIJ Journal 2012 Journal Article

Magic Sets for disjunctive Datalog programs

• Mario Alviano
• Wolfgang Faber
• Gianluigi Greco
• Nicola Leone

In this paper, a new technique for the optimization of (partially) bound queries over disjunctive Datalog programs with stratified negation is presented. The technique exploits the propagation of query bindings and extends the Magic Set optimization technique (originally defined for non-disjunctive programs). An important feature of disjunctive Datalog programs is non-monotonicity, which calls for non-deterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the non-deterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined Magic Set methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically. The correctness of the method is established and proved in a formal way thanks to a strong relationship between Magic Sets and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method and the correctness proof also to programs with stratified negation in a natural way. The proposed method has been implemented in the DLV system and various experiments on synthetic as well as on real-world data have been conducted. The experimental results on synthetic data confirm the utility of Magic Sets for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method with respect to the previously proposed Magic Set method for disjunctive Datalog programs. Further experiments on data taken from a real-life application show the benefits of the Magic Set method within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information.

KR Conference 2012 Conference Paper

Strong Equivalence of Qualitative Optimization Problems

• Wolfgang Faber
• Mirek Truszczynski
• Stefan Woltran

Representing and reasoning about preferences in qualitative settings is an important research area for knowledge representation and qualitative decision theory. The main objectives are to design expressive yet intuitive languages to model preferences, and to develop automated methods to reason about formal representations of preferences in these languages. The literature on the subject of preferences is vast. We refer the reader to the special issue of Artificial Intelligence Magazine (Goldsmith and Junker 2008) for a collection of overview articles and references. Understanding when optimization problems are equivalent, in particular, when one can be interchanged with another within any larger context, is fundamental to any preference formalism. Speaking informally, optimization problems P and Q are interchangeable or strongly equivalent when for every optimization problem R (context), P ∪ R and Q ∪ R define the same optimal models. Understanding when one optimization problem is equivalent to another in this sense is essential for preference analysis, modular preference representation, and rewriting techniques to simplify optimization problems into forms more amenable to processing, without changing any of their inherent properties. Let us consider a multi-agent setting, in which agents combine their preferences on some set of alternatives with the goal of identifying optimal ones. Can one agent in the ensemble be replaced with another so that the set of optimal alternatives is unaffected not only now, but also under any extension of the ensemble in the future? Strong equivalence of agents’ optimization problems is precisely what is needed to guarantee this full interchangeability property! The notion of strong equivalence is of general interest, by no means restricted to preference formalisms. In some cases, most notably for classical logic, it coincides with equivalence, the property of having the same models. However, if the semantics is not monotone, that is, extending the theory may introduce new models, not only eliminate some, strong equivalence becomes a strictly stronger concept, and the one to adopt if theories being analyzed are to be placed within a larger context. The nonmonotonicity of the semantics is the salient feature of nonmonotonic logics (Marek and Truszczyński 1993) and strong equivalence of theories in nonmonotonic logics, especially logic programming with the answer-set semantics (Gelfond and Lifschitz 1991), was extensively studied in that set- We introduce the framework of qualitative optimization problems (or, simply, optimization problems) to represent preference theories. The formalism uses separate modules to describe the space of outcomes to be compared (the generator) and the preferences on outcomes (the selector). We consider two types of optimization problems. They differ in the way the generator, which we model by a propositional theory, is interpreted: by the standard propositional logic semantics, and by the equilibrium-model (answer-set) semantics. Under the latter interpretation of generators, optimization problems directly generalize answer-set optimization programs proposed previously. We study strong equivalence of optimization problems, which guarantees their interchangeability within any larger context. We characterize several versions of strong equivalence obtained by restricting the class of optimization problems that can be used as extensions and establish the complexity of associated reasoning tasks. Understanding strong equivalence is essential for modular representation of optimization problems and rewriting techniques to simplify them without changing their inherent properties.

AIJ Journal 2011 Journal Article

Semantics and complexity of recursive aggregates in answer set programming

• Wolfgang Faber
• Gerald Pfeifer
• Nicola Leone

The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modelling power of ASP in terms of natural and concise problem representations. Previous semantic definitions typically agree in the case of non-recursive aggregates, but the picture is less clear for aggregates involved in recursion. Some proposals explicitly avoid recursive aggregates, most others differ, and many of them do not satisfy desirable criteria, such as minimality or coincidence with answer sets in the aggregate-free case. In this paper we define a semantics for programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates) in the full ASP language allowing also for disjunction in the head (disjunctive logic programming — DLP). This semantics is a genuine generalization of the answer set semantics for DLP, it is defined by a natural variant of the Gelfond–Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. This novel transformation is interesting per se also in the aggregate-free case, since it is simpler than the original transformation and does not need to differentiate between positive and negative literals. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and we demonstrate that it coincides with the standard answer set semantics on aggregate-free programs. Moreover, we carry out an in-depth study of the computational complexity of the language. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of aggregates, disjunction, and negation. While the addition of aggregates does not affect the complexity of the full DLP language, it turns out that their presence does increase the complexity of normal (i. e. , non-disjunctive) ASP programs up to the second level of the polynomial hierarchy. However, we show that there are large classes of aggregates the addition of which does not cause any complexity gap even for normal programs, including the fragment allowing for arbitrary monotone, arbitrary antimonotone, and stratified (i. e. , non-recursive) nonmonotone aggregates. The analysis provides some useful indications on the possibility to implement aggregates in existing reasoning engines.

AAAI Conference 2010 Conference Paper

Space Efficient Evaluation of ASP Programs with Bounded Predicate Arities

• Thomas Eiter
• Wolfgang Faber
• Mushthofa Mushthofa

Answer Set Programming (ASP) has been deployed in many applications, thanks to the availability of efficient solvers. Most programs encountered in practice have an important property: Their predicate arities are bounded by a constant, and in this case it is known that the relevant computations can be done using polynomial space. However, all competitive ASP systems rely on grounding, due to which they may use exponential space for these programs. We present three evaluation methods that respect the polynomial space bound and a generic framework architecture for realization. Experimental results for a prototype implementation indicate that the methods are effective. They show not only benign space consumption, but interestingly also good runtime compared to some state of the art ASP solvers.

AAAI Conference 2008 Conference Paper

Magic Sets for Data Integration

• Wolfgang Faber

We present a generalization of the Magic Sets technique to Datalog¬ programs with (possibly unstratified) negation under the stable model semantics, originally defined in (Faber, Greco, & Leone 2005; 2007). The technique optimizes Datalog¬ programs by means of a rewriting algorithm that preserves query equivalence, under the proviso that the original program is consistent. The approach is motivated by recently proposed methods for query answering in data integration and inconsistent databases, which use cautious reasoning over consistent Datalog¬ programs under the stable model semantics. In order to prove the correctness of our Magic Sets transformation, we have introduced a novel notion of modularity for Datalog¬ under the stable model semantics, which is more suitable for query answering than previous module definitions, and which is also relevant per se. A module under this definition guarantees independent evaluation of queries if the full program is consistent. Otherwise, it guarantees soundness under cautious and completeness under brave reasoning.

KR Conference 2008 Conference Paper

Notions of Strong Equivalence for Logic Programs with Ordered Disjunction

• Wolfgang Faber
• Hans Tompits
• Stefan Woltran

Ordered disjunctions have been introduced as a simple, yet expressive approach for representing preferential knowledge by means of logic programs. The semantics for the resulting language is based on the answer-set semantics, but comes in different variants, depending on the particular interpretation of preference aggregation associated to the ordered disjunction connective. While in standard answer-set programming the question of when a program is to be considered equivalent to another received increasing attention in recent years, this problem has not been addressed for programs with ordered disjunctions so far. In this paper, we discuss the concept of strong equivalence in this setting. We introduce different versions of strong equivalence for programs with ordered disjunctions and provide model-theoretic characterisations, extending well-known ones for strong equivalence between ordinary logic programs. Furthermore, we discuss the relationships between the proposed notions and study their computational complexity.

IJCAI Conference 2007 Conference Paper

• Thomas Eiter
• Esra Erdem
• Wolfgang Faber

Reversing actions is the following problem: After executing a sequence of actions, which sequence of actions brings the agent back to the state just before this execution (an action reversal). Notably, this problem is different from a vanilla planning problem since the state we have to get back to is in general unknown. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. It has applications related to plan execution and monitoring in nondeterministic domains, such as recovering from a failed execution by partially undoing the plan, dynamically switching from one executed plan to another, or restarting plans. We formalize action reversal in a logic-based action1 framework and characterize its computational complexity. Since unsurprisingly, the problem is intractable in general, we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be easily applied for expressive action languages such as C+ or K.

IJCAI Conference 2005 Conference Paper

Declarative and Computational Properties of Logic Programs with Aggregates

• Francesco Calimeri
• Wolfgang Faber
• Nicola Leone
• Simona

We investigate the properties of logic programs with aggregates. We mainly focus on programs with monotone and antimonotone aggregates (LPA m, a programs). We define a new notion of unfounded set for LPA m, a programs, and prove that it is a sound generalization of the standard notion of unfounded set for aggregate-free programs. We show that the answer sets of an LPA m, a program are precisely its unfounded-free models. We define a well-founded operator WP for LPA m, a programs; we prove that its total fixpoints are precisely the answer sets of P, and its least fixpoint Wω P (∅) is contained in the intersection of all answer sets (if P admits an answer set). Wω P (∅) is efficiently computable, and for aggregate-free programs it coincides with the well-founded model. We carry out an in-depth complexity analysis in the general framework, including also nonmonotone aggregates. We prove that monotone and antimonotone aggregates do not increase the complexity of cautious reasoning, which remains in co-NP. Nonmonotone aggregates, instead, do increase the complexity by one level in the polynomial hierarchy. Our results allow also to generalize and speedup ASP systems with aggregates.

IJCAI Conference 2005 Conference Paper

Heuristics for Hard ASP Programs

• Wolfgang Faber
• Nicola Leone
• Francesco

We define a new heuristic hDS for ASP, and implement it in the (disjunctive) ASP system DLV. The new heuristic improves the evaluation of ΣP 2 /ΠP 2 hard ASP programs while maintaining the benign behaviour of the well-assessed heuristic of DLV on NP problems. We experiment with the new heuristic on QBFs. hDS significantly outperforms the heuristic of DLV on hard 2QBF problems. We compare also the DLV system (with the new heuristic hDS) to three prominent QBF solvers. The results of the comparison, performed on instances used in the last QBF competition, indicate that ASP systems can be faster than QBF systems on ΣP 2 /ΠP 2 -hard problems.

IJCAI Conference 2005 Conference Paper

Strong Equivalence for Logic Programs with Preferences

• Wolfgang Faber
• Kathrin

Recently, strong equivalence for Answer Set Programming has been studied intensively, and was shown to be beneficial for modular programming and automated optimization. In this paper we define the novel notion of strong equivalence for logic programs with preferences. Based on this definition we give, for several semantics for preference handling, necessary and sufficient conditions for programs to be strongly equivalent. These results provide a clear picture of the relationship of these semantics with respect to strong equivalence, which differs considerably from their relationship with respect to answer sets. Finally, based on these results, we present for the first time simplification methods for logic programs with preferences.

KR Conference 2004 Conference Paper

Complexity of Model Checking and Bounded Predicate Arities for Non-ground Answer Set Programming

• Thomas Eiter
• Wolfgang Faber
• Michael Fink
• Gerald Pfeifer
• Stefan Woltran

Answer Set Programming has become a host for expressing knowledge representation problems, which reinforces the interest in efficient methods for computing answer sets of a logic program. While for propositional programs, the complexity of this task has been amply studied and is well-understood, less attention has been paid to the case of non-ground programs, which is much more important from a KR language perspective. Existing Answer Set Programming systems employ different representations of models, but the consequences of these representations for answer set computation and reasoning tasks have not been analyzed in detail. In this paper, we present novel complexity results on answer set checking for non-ground programs under two methods for representing answer sets and a variety of syntactic restrictions. In particular, we consider set-based and bitmap-based representations, which are popular in implementations of Answer Set Programming systems. Based on these results, we also derive new complexity results for the canonical reasoning tasks over answer sets, under the assumption that predicate arities are bounded by some constant. Our results imply that in such a setting - which appears to be a reasonable assumption in practice - more efficient implementations than those currently available may be feasible.

AIJ Journal 2003 Journal Article

A logic programming approach to knowledge-state planning, II: The system

• Thomas Eiter
• Wolfgang Faber
• Nicola Leone
• Gerald Pfeifer
• Axel Polleres

In Part I of this series of papers, we have proposed a new logic-based planning language, called K. This language facilitates the description of transitions between states of knowledge and it is well suited for planning under incomplete knowledge. Nonetheless, K also supports the representation of transitions between states of the world (i. e. , states of complete knowledge) as a special case, proving to be very flexible. In the present Part II, we describe the DLV K planning system, which implements K on top of the disjunctive logic programming system DLV. This novel planning system allows for solving hard planning problems, including secure planning under incomplete initial states (often called conformant planning in the literature), which cannot be solved at all by other logic-based planning systems such as traditional satisfiability planners. We present a detailed comparison of the DLV K system to several state-of-the-art conformant planning systems, both at the level of system features and on benchmark problems. Our results indicate that, thanks to the power of knowledge-state problem encoding, the DLV K system is competitive even with special purpose conformant planning systems, and it often supplies a more natural and simple representation of the planning problems.

IJCAI Conference 2003 Conference Paper

Aggregate Functions in Disjunctive Logic Programming: Semantics, Complexity, and Implementation in DLV

• Tina DelVArmi
• Wolfgang Faber
• Giuseppe Ielpa
• Nicola Leone
• Gerald Pfeifer

Disjunctive Logic Programming (DLP) is a very expressive formalism: it allows to express every property of finite structures that is decidable in the complexity class E^ (NPN H ). Despite the high expressiveness of DLP, there are some simple properties, often arising in real-world applications, which cannot be encoded in a simple and natural manner. Among these, properties requiring to apply some arithmetic operators (like sum, times, count) on a set of elements satisfying some conditions, cannot be naturally expressed in DLP. To overcome this deficiency, in this paper we extend DLP by aggregate functions. We formally define the semantics of the new language, named DLP-4. We show the usefulness of the new constructs on relevant knowledge-based problems. We analyze the computational complexity of DLP"4, showing that the addition of aggregates does not bring a higher cost in that respect. We provide an implementation of the DLP-4 language in DLV- the state-of-theart DLP system - and report on experiments which confirm the usefulness of the proposed extension also for the efficiency of the computation.