Author name cluster

Ester Zumpano

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.

7 papers

2 author rows

IS Journal 2022 Journal Article

Computing Abductive Explanations

Luciano Caroprese
Ester Zumpano
Bart Bogaerts

We study the computation of constrained explanations in the framework of abductive logic programming. A general characteristic of abductive reasoning is the existence of multiple abductive explanations. Therefore, identifying a subclass of “preferred explanations” is a relevant problem. A typical approach is to “prefer” explanations that are, in some sense, simple. Several concepts of simplicity were considered in the literature, most notably those based on minimality with respect to inclusion and cardinality. We adopt, as a measure of the quality of an explanation, its degree of arbitrariness that can be briefly described as the number of arbitrary assumptions that have been made to derive the explanation. The more arbitrary the explanation, the less appealing it is, with explanations having no arbitrariness, called constrained, being the preferred ones. In this article, we present a technique that, for a special class of theories, computes constrained explanations. It is based on a rewriting of the theory and the observation into a disjunctive logic program with negation so that the constrained explanations correspond to a subset of its stable models. The proposed technique lays the foundation for using ASP solvers to compute constrained explanations.

Details DOI

JELIA Conference 2012 Conference Paper

The View-Update Problem for Indefinite Databases

Luciano Caroprese
Irina Trubitsyna
Miroslaw Truszczynski
Ester Zumpano

Abstract This paper introduces and studies a declarative framework for updating views over indefinite databases. An indefinite database is a database with null values that are represented, following the standard database approach, by a single null constant. The paper formalizes views over such databases as indefinite deductive databases, and defines for them several classes of database repairs that realize view-update requests. Most notable is the class of constrained repairs. Constrained repairs change the database “minimally” and avoid making arbitrary commitments. They narrow down the space of alternative ways to fulfill the view-update request to those that are grounded, in a certain strong sense, in the database, the view and the view-update request.

Details

JELIA Conference 2006 Conference Paper

On the Semantics of Logic Programs with Preferences

Sergio Greco
Irina Trubitsyna
Ester Zumpano

Abstract This work is a contribution to realizing prioritized reasoning in logic programming in the presence of preference relations involving atoms. In more details, the case of dynamic preferences is investigated and a semantics interpreting each preference rule as a tool for representing a choice over alternative options is proposed. The technique, providing a new interpretation for prioritized logic programs, is inspired by the one proposed by Sakama and Inoue in [19] and enriched with the use of structural information of preference rules as proposed by Brewka et al. in [6]. Specifically, the analysis of the logic program is carried out together with the analysis of preferences in order to determine the choice order and the sets of comparable models. The proposed approach is compared with those in [6, 19]. Complexity analysis is also performed showing that the use of additional information does not increase the complexity of computing preferred stable models.

Details

JELIA Conference 2002 Conference Paper

Complexity and Algorithms for the Matching of Bag and Set Terms

Gianluigi Greco
Ester Zumpano

Abstract Bounded bag and set terms are complex terms in which every element can be a constant or a variable. These types of complex terms have been introduced in several logic languages, such as LDL, Coral and Godel, in order to increase their expressive power, and they have been recently used to define logic languages for database integration. The paper addresses the problem of computing the set of matchers of two bag (or set) terms, by providing a general complexity analysis and a closed formula for determining the number of matchers for tractable cases. An algorithm for the general problem and optimal algorithms for tractable cases are also provided.

Details

LPAR Conference 2002 Conference Paper

Query Optimization of Disjunctive Databases with Constraints through Binding Propagation

Gianluigi Greco
Sergio Greco
Irina Trubitsyna
Ester Zumpano

Abstract In this paper we present a technique for the optimization of bound queries over disjunctive deductive databases with constraints, i. e. rules defining properties which have to be satisfied by all instances over database schema. The technique we propose, allows the binding propagation into disjunctive queries with a set of constraints; thus, reducing the size of the data relevant to answer the query it, consequently, minimizes both the complexity of computing a single model and the whole number of models to be considered. The main contribution of this work consists in the extension of previous techniques by considering Datalog programs with both disjunctive heads and constraints. In particular, by considering weak constraints the technique is also suitable for dealing with optimization problems. Several experiments have confirmed the value of the technique.

Details

LOPSTR Conference 2002 Conference Paper

Translating Datalog-Like Optimization Queries into ILOG Programs

Gianluigi Greco
Sergio Greco
Irina Trubitsyna
Ester Zumpano

Abstract This paper presents a logic language, called \( \mathcal{N}\mathcal{P}{\mathbf{ }}Datalog \) suitable for expressing NP search and optimization problems. The ‘search’ language extends stratified Datalog with constraints and allows disjunction to define nondeterministically partitions of relations. It’s well known that \( \mathcal{N}\mathcal{P} \) search problems can be formulated as unstratified DATALOG queries under nondeterministic stable model semantics so that each stable model corresponds to a possible solution. \( \mathcal{N}\mathcal{P} \) optimization problems are then formulated by adding a max (or min ) construct to select the stable model (thus, the solution) which maximizes (resp. , minimizes) the result of a polynomial function applied to the answer relation. The problem in using DATALOG ¬ to express search and optimization problems is that the unrestricted negation in programs is often neither simple nor intuitive and, besides, it does not allow to discipline the expressive power. Thus, we consider restricted forms of negation which force user to write programs in a more disciplined way without loosing of expressive power. More specifically, we consider the language \( \mathcal{N}\mathcal{P}{\mathbf{ }}Datalog \) which extends DATALOG ¬ s with two simple forms of unstratified negation embedded into built-in constructs: head disjunction and constraints. Thus the core of our language is stratified Datalog extended with two constructs allowing nondeterministic selections and with query goals enforcing conditions to be satisfied by stable models.

Details

LPAR Conference 2000 Conference Paper

Querying Inconsistent Databases

Sergio Greco
Ester Zumpano

Abstract In this paper we consider the problem of answering queries consistently in the presence of inconsistent data, i. e. data violating integrity constraints. We propose a technique based on the rewriting of integrity constraints into disjunctive rules with two di. erent forms of negation (negation as failure and classical negation). The disjunctive program can be used i) to generate ‘repairs’ for the database and ii) to produce consistent answers, i. e. maximal set of atoms which do not violate the constraints. We show that our technique is sound, complete and more general than techniques previously proposed.

Details