Author name cluster

Gerald Pfeifer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

2 author rows

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.

Details DOI

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.

JELIA Conference 2004 Conference Paper

New DLV Features for Data Integration

Francesco Calimeri
Manuela Citrigno
Chiara Cumbo
Wolfgang Faber 0001
Nicola Leone
Simona Perri
Gerald Pfeifer

Abstract The DLV system is currently employed in projects on data integration – a challenging application area for Answer Set Programming. The present system description illustrates some new optimization techniques, which significantly enhance the general performance of DLV, and especially in the context of data integration.

Details

JELIA Conference 2004 Conference Paper

Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity

Wolfgang Faber 0001
Nicola Leone
Gerald Pfeifer

Abstract The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modeling power of ASP, in terms of concise problem representations. While many important problems can be encoded using nonrecursive aggregates, some relevant examples lend themselves for the use of recursive aggregates. Previous semantic definitions typically agree in the nonrecursive case, but the picture is less clear for 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 disjunctive programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates). This semantics is a fully declarative, genuine generalization of the answer set semantics for disjunctive logic programming (DLP). It is defined by a natural variant of the Gelfond-Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and demonstrate that it coincides with the standard answer set semantics on aggregate-free programs. Finally we analyze the computational complexity of this language, paying particular attention to the impact of syntactical restrictions on programs.

Details

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.

Details DOI

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.

PDF

AIJ Journal 2003 Journal Article

Enhancing disjunctive logic programming systems by SAT checkers

Christoph Koch
Nicola Leone
Gerald Pfeifer

Disjunctive logic programming (DLP) with stable model semantics is a powerful nonmonotonic formalism for knowledge representation and reasoning. Reasoning with DLP is harder than with normal (∨-free) logic programs, because stable model checking—deciding whether a given model is a stable model of a propositional DLP program—is co-NP-complete, while it is polynomial for normal logic programs. This paper proposes a new transformation ΓM(P), which reduces stable model checking to UNSAT—i. e. , to deciding whether a given CNF formula is unsatisfiable. The stability of a model M of a program P thus can be verified by calling a Satisfiability Checker on the CNF formula ΓM(P). The transformation is parsimonious (i. e. , no new symbol is added), and efficiently computable, as it runs in logarithmic space (and therefore in polynomial time). Moreover, the size of the generated CNF formula never exceeds the size of the input (and is usually much smaller). We complement this transformation with modular evaluation results, which allow for efficient handling of large real-world reasoning problems. The proposed approach to stable model checking has been implemented in DLV—a state-of-the-art implementation of DLP. A number of experiments and benchmarks have been run using SATZ as Satisfiability checker. The results of the experiments are very positive and confirm the usefulness of our techniques.

Details DOI

JELIA Conference 2002 Conference Paper

Answer Set Planning under Action Costs

Thomas Eiter
Wolfgang Faber 0001
Nicola Leone
Gerald Pfeifer
Axel Polleres

Abstract We present \( \mathcal{K}^c \), which extends the declarative planning language \( \mathcal{K} \) by action costs and optimal plans that minimize overall action costs (cheapest plans). As shown, this novel language allows for expressing some nontrivial planning tasks in an elegant way. Furthermore, it flexibly allows for representing planning problems under other optimality criteria as well, such as computing “fastest” plans (with the least number of steps), and refinement combinations of cheap and fast plans. Our experience is encouraging and supports the claim that answer set planning may be a valuable approach to advanced planning systems in which intricate planning tasks can be naturally specified and effectively solved.

Details

NMR Workshop 2002 Conference Paper

Pruning operators for answer set programming systems

Francesco Calimeri
Wolfgang Faber 0001
Nicola Leone
Gerald Pfeifer

Answer Set Programming (ASP) is a novel paradigm in Logic Programming, which allows for solving problems in a simple and highly declarative way. The language of ASP (function-free disjunctive logic programming) is very expressive and supports the representation of problems of high computational complexity (specifically, all problems in the complexity class UP = NPNP). Importantly, the ASP encoding of a large variety of problems is often very concise, simple, and elegant. In this paper, we explain the computational process performed by ASP systems, with a focus on search space pruning, which is crucial for efficiency. We analyze the properties of two main pruning operators, namely (Fitting’s operator and Well-founded operator), discuss their peculiarities and differences with respect to efficiency and effectiveness. We design an intelligent strategy for combining the two operators, which exploits the advantages of both. We implement our approach in the ASP system DLV, and perform some experiments. The experiments show interesting results, and evidence how the choice of the pruning operator affects the performance of ASP systems.

Details

JELIA Conference 2002 Conference Paper

The DLV K Planning System: Progress Report

Thomas Eiter
Wolfgang Faber 0001
Nicola Leone
Gerald Pfeifer
Axel Polleres

Abstract The knowledge based planning system DLV K implements answer set planning on top of the DLV system [ 1 ]. It is developed at TU Wien and supports the declarative language K [ 2 ], [ 3 ] and its extension K c [ 5 ]. The language K is syntactically similar to the action language C [ 7 ], but semantically closer to answer set programming (by including default negation, for example). K and K c offer the following distinguishing features:

Details

JELIA Conference 2002 Conference Paper

The DLV System

Nicola Leone
Gerald Pfeifer
Wolfgang Faber 0001
Francesco Calimeri
Tina Dell'Armi
Thomas Eiter
Georg Gottlob
Giovambattista Ianni

Abstract The development of the DLV system has started as a research projectfinanced by FWF (the Austrian Science Funds) in 1996, and has evolved into an international collaboration over the years. Currently, the University of Calabria and TU Wien participate in the project, supported by a scientific-technological collaboration between Italy and Austria. At the time of writing, the latest version of the system has been released on April 12, 2002.

Details