Catálogo de publicaciones - libros

We describe the design of the system, an implementation of the preferred answer set semantics for ordered logic programs. The basic algorithm we propose computes the extended answer sets of a simple program using an intuitive 9-valued lattice, called . During the computation, this lattice is employed to keep track of the status of the literals and the rules while evolving to a solution. It turns out that the basic algorithm needs little modification in order to be able to compute the preferred answer sets of an ordered logic program. We illustrate the system using an example from diagnostic reasoning and we present some preliminary benchmark results comparing with existing answer set solvers such as and .

A critical issue in the design of logic programming systems is their memory performance, both in terms of total memory usage and locality in memory accesses. BEAM, as most modern Prolog systems, requires both good emulator design and good memory performance for best performance. We report on a detailed study of the memory management techniques used on our sequential implementation of the EAM. We address questions like how effective are the techniques the BEAM uses to recover and reuse memory space, how garbage collection affects performance and how to classify and unify variables in a EAM environment. We also propose a finer variable allocation scheme to reduce memory overheads that is quite effective at reducing memory pressure, with only a small overhead.

In this paper, we present a for . With this aim, we define a constraint system for handling (points, lines, polygons and regions) and constraints on them (equalities and inequalities, memberships, metric, topological and structural constraints), and provide a suitable theory for this constraint system. The constraint solver is presented in the form of . These transformation rules handle a special kind of constraints used for , enabling an solving of spatial constraints.

An unsatisfiable set of constraints is minimal if all its (strict) subsets are satisfiable. The task of type error diagnosis requires finding all minimal unsatisfiable subsets of a given set of constraints (representing an error), in order to generate the best explanation of the error. Similarly circuit error diagnosis requires finding all minimal unsatisfiable subsets in order to make minimal diagnoses. In this paper we present a new approach for efficiently determining all minimal unsatisfiable sets for any kind of constraints. Our approach makes use of the duality that exists between minimal unsatisfiable constraint sets and maximal satisfiable constraint sets. We show how to incrementally compute both these sets, using the fact that the complements of the maximal satisfiable constraint sets are the hitting sets of the minimal unsatisfiable constraint sets. We experimentally compare our technique to the best known method on a number of large type problems and show that considerable improvements in running time are obtained.

Truth values associated to fuzzy variables can be represented in an ordeal of different flavors, such as real numbers, percentiles, intervals, unions of intervals, and continuous or discrete functions on different domains. Many of the most interesting fuzzy problems deal with a discrete range of truth values. In this work we represent these ranges using Constraint Logic Programming over Finite Domains (CLP()). This allows to produce finite enumerations of constructive answers instead of complicated, hardly self-explanatory, constraints expressions. Another advantage of representing fuzzy models through finite domains is that some of the existing techniques and algorithms of the field of distributed constraint programming can be borrowed. In this paper we exploit these considerations in order to create a new generation of collaborative fuzzy agents in a distributed environment.

Generic programming is accepted by the functional programming community as a valuable tool for program development. Several functional languages have adopted the generic scheme of type-indexed values. This scheme works by specialization of a generic function to a concrete type. However, the generated code is extremely inefficient compared to its hand-written counterpart. The performance penalty is so big that the practical usefulness of generic programming is compromised. In this paper we present an optimization algorithm that is able to completely eliminate the overhead introduced by the specialization scheme for a large class of generic functions. The presented technique is based on consumer–producer elimination as exploited by fusion, a standard general purpose optimization method. We show that our algorithm is able to optimize many practical examples of generic functions.

Program inversion is a fundamental concept in programtransformation. We describe the principles behind an automatic program inverter, which we developed for a first-order functional language, and show several inverse programs automatically produced by our system. The examples belong to different application areas, including encoding and decoding, printing and parsing, and bidirectional data conversion. The core of the system uses a stack-based language, local inversion, and eliminates nondeterminism by applying methods from parsing theory.

In this article we investigate a novel execution paradigm – ML-like pattern-matching – for XML query processing. We show that such a paradigm is well adapted for a common and frequent set of queries and advocate that it constitutes a candidate for efficient execution of XML queries far better than the current XPath-based query mechanisms. We support our claim by comparing performances of XPath-based queries with pattern based ones, and by comparing the latter with the two efficiency-best XQuery processor we are aware of.

The goal of this paper is to improve the type error messages in the presence of type classes, in particular for the non-expert user. As a language feature, type classes are very pervasive, and strongly influence what is reported and when, even in relatively simple programs. We propose four type class directives, and specialized type rules, to lend high-level support to compilers to improve the type error messages. Both have been implemented, and can be used to easily modify the behavior of the type inference process.