Wyniki wyszukiwania - BazTech

1

Look-back Techniques for ASP Programs with Aggregates

Faber W., Leone N., Maratea M., Ricca F.

Fundamenta Informaticae

|

2011

|

Vol. 107, nr 4

379-413

EN

The introduction of aggregates has been one of the most relevant language extensions to Answer Set Programming (ASP). Aggregates are very expressive, they allow to represent many problems in a more succinct and elegant way compared to aggregate-free programs. A significant amount of research work has been devoted to aggregates in the ASP community in the last years, and relevant research results on ASP with aggregates have been published, on both theoretical and practical sides. The high expressiveness of aggregates (eliminating aggregates often causes a quadratic blow-up in program size) requires suitable evaluation methods and optimization techniques for an efficient implementation. Nevertheless, in spite of the above-mentioned research developments, aggregates are treated in a quite straightforward way in most ASP systems. In this paper, we explore the exploitation of look-back techniques for an efficient implementation of aggregates. We define a reason calculus for backjumping in ASP programs with aggregates. Furthermore, we describe how these reasons can be used in order to guide look-back heuristics for programs with aggregates. We have implemented both the new reason calculus and the proposed heuristics in the DLV system, and have carried out an experimental analysis on publicly available benchmarks which shows significant performance benefits

2

A Logic-Based System for e-Tourism

Ricca F., Dimasi A., Grasso G., Ielpa S.M., Iiritano S., Manna M., Leone N.

Fundamenta Informaticae

|

2011

|

Vol. 105, nr 1/2

35-55

EN

In this paper we present a successful application of logic programming for e-tourism: the iTravel system. The system exploits two technologies that are based on the state-of-the-art computational logic system DLV: (i) a system for ontology representation and reasoning, called OntoDLV; and, (ii) HLX a semantic information-extraction tool. The core of iTravel is an ontology which models the domain of tourism offers. The ontology is automatically populated by extracting the information contained in the tourism leaflets produced byε tour operators. A set of specifically devised logic programs is used to reason on the information contained in the ontology for selecting the holiday packages that best fit the customer needs. An intuitive web-based user interface eases the task of interacting with the system for both the customers and the operators of a travel agency.

3

Normal Form Nested Programs

Bria A., Faber W., Leone N.

Fundamenta Informaticae

|

2009

|

Vol. 96, nr 3

271-295

EN

Disjunctive logic programming under the answer set semantics (DLP, ASP) has been acknowledged as a versatile formalism for knowledge representation and reasoning during the last decades. Lifschitz, Tang, and Turner have introduced an extended language of DLP, called Nested Logic Programming (NLP), in 1999 [12]. It often allows for more concise representations by permitting a richer syntax in rule heads and bodies. However, that language is propositional and thus does not allow for variables, one of the strengths of DLP. In this paper, we introduce a language similar to NLP, called Normal Form Nested (NFN) programs, which does allow for variables, and present the syntax and semantics. However, with the introduction of variables an important issue arises: domain independence, the question of whether the semantics of a program is independent of the considered domain (given that it is sufficiently rich). Domain independence, originally studied for logic-based database query languages, is desirable because it guarantees that the semantics remains equal if unrelated information is added and also ensures finiteness of intended models even if infinite domains are considered. With the presence of variables, NFN programs in general are not domain independent. We study this issue in depth and define the class of safe NFN programs, which are guaranteed to be domain independent. Moreover, we show that for those NFN programs, which are also NLPs, our semantics coincides with the one of [12], while keeping the standard meaning of answer sets on DLP programs with variables. We also show that our semantics coincides with Herbrand stable models as defined in [6] of formulas corresponding to NFN programs. Finally, we provide an algorithm which transforms NFN programs into DLP programs in a correct and efficient way. We have implemented this algorithm, which provides an effective implementation of the NFN language, using existing DLP systems as a back-end.

4

Pruning Operators for Disjunctive Logic Programming Systems

Calimeri F., Faber W., Pfeifer G., Leone N.

Fundamenta Informaticae

|

2006

|

Vol. 71, nr 2,3

183-214

EN

Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning. The language of DLP is very expressive and supports the representation of problems of high computational complexity (specifically, all problems in the complexity class \SigmaP2 = \NP\NP). The DLP encoding of a large variety of problems is often very concise, simple, and elegant. In this paper, we explain the computational process commonly performed by DLP systems, with a focus on search space pruning, which is crucial for the efficiency of such systems. We present two suitable operators for pruning (Fitting's and Well-founded), discuss their peculiarities and differences with respect to efficiency and effectiveness. We design an intelligent strategy for combining the two operators, exploiting the advantages of both. We implement our approach in DLV - the state-of-the-art DLP system - and perform some experiments. These experiments show interesting results, and evidence how the choice of the pruning operator affects the performance of DLP systems.