Author name cluster

Giovanni Amendola

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.

18 papers

2 author rows

AIJ Journal 2022 Journal Article

Answers set programs for non-transferable utility games: Expressiveness, complexity and applications

Giovanni Amendola
Gianluigi Greco
Pierfrancesco Veltri

Coalitional games are mathematical models suited to study payoff distribution problems in cooperative scenarios. In abstract terms, a coalitional game can be specified by explicitly listing all possible—in fact, exponentially many—coalitions with their associated distributions. This naïve representation, however, quickly becomes infeasible over games involving many agents, thereby calling for suitable compact representations, that is, encoding mechanisms that (on some specific classes of games of interest) take an amount of space that grows polynomially with the number of agents. To date, a plethora of compact encodings have been already introduced and analyzed from the algorithm and computational viewpoints. Despite their specific technical differences, these encodings typically share the assumption that the utility associated with a coalition can be freely transferred among agents. Indeed, designing encoding mechanisms for the non-transferable utility (NTU) setting is a research issue that has been largely unexplored so far. The paper addresses this issue by proposing a compact encoding for representing and reasoning about the outcomes of NTU coalitional games founding on answer set programming. By exploiting the expressiveness of this well-known knowledge representation formalism, it is shown that the proposed representation can succinctly encode several games of interest within a wide range of application domains. Computational issues arising in the setting have been studied too, by addressing questions related to certain payoff distributions enjoying desirable stability properties. Eventually, a prototype system supporting the proposed framework has been implemented by leveraging a state-of-the-art answer set engine, and results of a thorough experimental activity conducted on top of it have been discussed.

Details DOI

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.

Details DOI

JELIA Conference 2021 Conference Paper

Testing in ASP: Revisited Language and Programming Environment

Giovanni Amendola
Tobias Berei
Francesco Ricca

Abstract Unit testing frameworks are nowadays considered a best practice, foregone in almost all modern software development processes, to achieve rapid development of correct specifications. The first unit testing specification language for Answer Set Programming (ASP) was proposed in 2011 as a feature of the ASPIDE development environment. Later, a more portable unit testing language was included in the LANA annotation language. In this paper we propose a revisited unit testing specification language that allows one to inline tests within ASP program and an ASP-based test execution mechanism. Moreover, we present a programming environment supporting test driven development (TDD) of ASP programs with our language.

Details

IJCAI Conference 2020 Conference Paper

A Formal Approach for Cautious Reasoning in Answer Set Programming (Extended Abstract)

Giovanni Amendola
Carmine Dodaro
Marco Maratea

The issue of describing in a formal way solving algorithms in various fields such as Propositional Satisfiability (SAT), Quantified SAT, Satisfiability Modulo Theories, Answer Set Programming (ASP), and Constraint ASP, has been relatively recently solved employing abstract solvers. In this paper we deal with cautious reasoning tasks in ASP, and design, implement and test novel abstract solutions, borrowed from backbone computation in SAT. By employing abstract solvers, we also formally show that the algorithms for solving cautious reasoning tasks in ASP are strongly related to those for computing backbones of Boolean formulas. Some of the new solutions have been implemented in the ASP solver WASP, and tested.

PDF Details DOI

AIJ Journal 2020 Journal Article

New models for generating hard random boolean formulas and disjunctive logic programs

Giovanni Amendola
Francesco Ricca
Miroslaw Truszczynski

We propose two models of random quantified boolean formulas and their natural random disjunctive logic program counterparts. The models extend the standard models of random k-CNF formulas and the Chen-Interian model of random 2QBFs. The first model controls the generation of programs and QSAT formulas by imposing a specific structure on rules and clauses, respectively. The second model is based on a family of QSAT formulas in a non-clausal form. We provide theoretical bounds for the phase transition region in our models, and show experimentally the presence of the easy-hard-easy pattern and its alignment with the location of the phase transition. We show that boolean formulas and logic programs from our models are significantly harder than those obtained from the standard k-CNF and Chen-Interian models, and that their combination yields formulas and programs that are “super-hard” to evaluate. We also provide evidence suggesting that formulas from one of our models are well suited for assessing solvers tuned to real-world instances. Finally, it is noteworthy that, to the best of our knowledge, our models and results on random disjunctive logic programs are the first of their kind.

Details DOI

JELIA Conference 2019 Conference Paper

Algorithm Selection for Paracoherent Answer Set Computation

Giovanni Amendola
Carmine Dodaro
Wolfgang Faber 0001
Luca Pulina
Francesco Ricca

Abstract Answer Set Programming (ASP) is a well-established AI formalism rooted in nonmonotonic reasoning. Paracoherent semantics for ASP have been proposed to derive useful conclusions also in the absence of answer sets caused by cyclic default negation. Recently, several different algorithms have been proposed to implement them, but no algorithm is always preferable to the others in all instances. In this paper, we apply algorithm selection techniques to devise a more efficient paracoherent answer set solver combining existing algorithms. The effectiveness of the approach is demonstrated empirically running our system on existing benchmarks.

Details

JELIA Conference 2019 Conference Paper

Extending Bell Numbers for Parsimonious Chase Estimation

Giovanni Amendola
Cinzia Marte

Abstract Ontology-Based Query Answering (OBQA) consists in querying databases by taking ontological knowledge into account. We focus on a logical framework based on existential rules or tuple generating dependencies (TGDs), also known as Datalog \(^\pm \), which collects the basic decidable classes of TGDs, and generalizes several ontology specification languages, such as Description Logics. A fundamental notion to find certain answers to a query is the chase. This tool has been widely used to deal with different problems in databases, as it has the fundamental property of constructing a universal model. Recently, the so-called “parsimonious” chase procedure has been introduced. For some classes, it is sound and complete, and the termination is always guaranteed. However, no precise bound has been provided so far. To this end, we exploit the Bell number definition to count the exact maximal number of atoms generating by the parsimonious chase procedure.

Details

KR Conference 2018 Conference Paper

A generator of hard 2QBF formulas and ASP programs

Giovanni Amendola
Francesco Ricca
Mirek Truszczynski

The availability of generators of random instances of boolean formulas has had a major impact on solver technology for KR formalisms such as SAT, QBF and ASP. Recently, we proposed new models of random QSAT formulas in non-clausal form, as well as the first model of random disjunctive logic programs. Our models support generating instances of substantial hardness. Here, we present a tool that generates formulas/programs from the new models in a variety of output formats including (Q)DIMACS, QCIR, and ASPCore 2. 0.

IJCAI Conference 2018 Conference Paper

Enhancing Existential Rules by Closed-World Variables

Giovanni Amendola
Nicola Leone
Marco Manna
Pierfrancesco Veltri

Existential rules generalize Datalog with existential quantification in the head. Natively, Datalog is interpreted under a closed-world semantics, while existential rules typically employ the open-world assumption. The interpretation domain in the latter case is enlarged by infinitely many "anonymous" individuals. Then, in any rule, each variable ranges over all individuals, even if not needed or required. In this paper, we enhance existential rules by closed-world variables to consciously reason on the properties of "known" (non-anonymous) and arbitrary individuals in different ways. Accordingly, we uniformly generalize the basic classes of existential rules that ensure decidability of ontology-based query answering. For them, after observing that decidability is preserved, we prove that a strict increase in expressiveness is gained, and in most cases the computational complexity is not altered.

PDF Details

IJCAI Conference 2018 Conference Paper

Explainable Certain Answers

Giovanni Amendola
Leonid Libkin

When a dataset is not fully specified and can represent many possible worlds, one commonly answers queries by computing certain answers to them. A natural way of defining certainty is to say that an answer is certain if it is consistent with query answers in all possible worlds, and is furthermore the most informative answer with this property. However, the existence and complexity of such answers is not yet well understood even for relational databases. Thus in applications one tends to use different notions, essentially the intersection of query answers in possible worlds. However, justification of such notions has long been questioned. This leads to two problems: are certain answers based on informativeness feasible in applications? and can a clean justification be provided for intersection-based notions? Our goal is to answer both. For the former, we show that such answers may not exist, or be very large, even in simple cases of querying incomplete data. For the latter, we add the concept of explanations to the notion of informativeness: it shows not only that one object is more informative than the other, but also says why this is so. This leads to a modified notion of certainty: explainable certain answers. We present a general framework for reasoning about them, and show that for open and closed world relational databases, they are precisely the common intersection-based notions of certainty.

PDF Details

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 deﬁnition 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.

PDF Details

IJCAI Conference 2018 Conference Paper

Finite Controllability of Conjunctive Query Answering with Existential Rules: Two Steps Forward

Giovanni Amendola
Nicola Leone
Marco Manna

Reasoning with existential rules typically consists of checking whether a Boolean conjunctive query is satisfied by all models of a first-order sentence having the form of a conjunction of Datalog rules extended with existential quantifiers in rule-heads. To guarantee decidability, five basic decidable classes - linear, weakly-acyclic, guarded, sticky, and shy - have been singled out, together with several generalizations and combinations. For all basic classes, except shy, the important property of finite controllability has been proved, ensuring that a query is satisfied by all models of the sentence if, and only if, it is satisfied by all of its finite models. This paper takes two steps forward: (i) devise a general technique to facilitate the process of (dis)proving finite controllability of an arbitrary class of existential rules; and (ii) specialize the technique to complete the picture for the five mentioned classes, by showing that also shy is finitely controllable.

PDF Details

IJCAI Conference 2017 Conference Paper

Generating Hard Random Boolean Formulas and Disjunctive Logic Programs

Giovanni Amendola
Francesco Ricca
Miroslaw Truszczynski

We propose a model of random quantified boolean formulas and their natural random disjunctive logic program counterparts. The model extends the standard models for random SAT and 2QBF. We provide theoretical bounds for the phase transition region in the new model, and show experimentally the presence of the easy-hard-easy pattern. Importantly, we show that the model is well suited for assessing solvers tuned to real-world instances. Moreover, to the best of our knowledge, our model and results on random disjunctive logic programs are the first of their kind.

PDF Details

AAAI Conference 2017 Conference Paper

Minimal Undefinedness for Fuzzy Answer Sets

Mario Alviano
Giovanni Amendola
Rafael Pealoza

Fuzzy Answer Set Programming (FASP) combines the nonmonotonic reasoning typical of Answer Set Programming with the capability of Fuzzy Logic to deal with imprecise information and paraconsistent reasoning. In the context of paraconsistent reasoning, the fundamental principle of minimal undeﬁnedness states that truth degrees close to 0 and 1 should be preferred to those close to 0. 5, to minimize the ambiguity of the scenario. The aim of this paper is to enforce such a principle in FASP through the minimization of a measure of undeﬁnedness. Algorithms that minimize undeﬁnedness of fuzzy answer sets are presented, and implemented.

PDF Details

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 identiﬁed. However, paracoherent semantics have essentially been inapplicable in practice, due to the lack of efﬁcient 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.

PDF Details

IJCAI Conference 2016 Conference Paper

Modeling and Reasoning about NTU Games via Answer Set Programming

Giovanni Amendola
Gianluigi Greco
Nicola Leone
Pierfrancesco Veltri

A compact representation for non-transferable utility games founding on answer set programming is proposed. The representation is fully expressive, in that it can capture all games defined over a finite set of alternatives. Moreover, due to the knowledge representation capabilities of answer set programs, it can easily accommodate the definition of games within a wide range of application domains, ranging from scheduling, to routing and planning, just to name a few. The computational complexity of the proposed framework is studied, in particular, by focusing on the core as the prototypical solution concept. A system supporting the basic reasoning tasks arising therein is also made available, and results of experimental activity are discussed.

PDF Details

AIJ Journal 2016 Journal Article

Semi-equilibrium models for paracoherent answer set programs

Giovanni Amendola
Thomas Eiter
Michael Fink
Nicola Leone
João Moura

The answer set semantics may assign a logic program to model, due to logical contradiction or unstable negation, which is caused by cyclic dependency of an atom on its negation. While logical contradictions can be handled with traditional techniques from paraconsistent reasoning, instability requires other methods. We consider resorting to a paracoherent semantics, in which 3-valued interpretations are used where a third truth value besides true and false expresses that an atom is believed true. This is at the basis of the semi-stable model semantics, which was defined using a program transformation. In this paper, we give a model-theoretic characterization of semi-stable models, which makes the semantics more accessible. Motivated by some anomalies of semi-stable model semantics with respect to basic epistemic properties, we propose an amendment that satisfies these properties. The latter has both a transformational and a model-theoretic characterization that reveals it as a relaxation of equilibrium logic, the logical reconstruction of answer set semantics, and is thus called the semi-equilibrium model semantics. We consider refinements of this semantics to respect modularity in the rules, based on splitting sets, the major tool for modularity in modeling and evaluating answer set programs. In that, we single out classes of canonical models that are amenable for customary bottom-up evaluation of answer set programs, with an option to switch to a paracoherent mode when lack of an answer set is detected. A complexity analysis of major reasoning tasks shows that semi-equilibrium models are harder than answer sets (i. e. , equilibrium models), due to a global minimization step for keeping the gap between true and believed true atoms as small as possible. Our results contribute to the logical foundations of paracoherent answer set programming, which gains increasing importance in inconsistency management, and at the same time provide a basis for algorithm development and integration into answer set solvers.

Details DOI

JELIA Conference 2014 Conference Paper

Modular Paracoherent Answer Sets

Giovanni Amendola
Thomas Eiter
Nicola Leone

Abstract The answer set semantics may assign a logic program no model due to classic contradiction or cyclic negation. The latter can be remedied by resorting to a paracoherent semantics given by semi-equilibrium ( SEQ ) models, which are 3-valued interpretations that generalize the logical reconstruction of answer sets given by equilibrium models. While SEQ -models have interesting properties, they miss modularity in the rules, such that a natural modular (bottom up) evaluation of programs is hindered. We thus refine SEQ -models using splitting sets, the major tool for modularity in modeling and evaluating answer set programs. We consider canonical models that are independent of any particular splitting sequence from a class of splitting sequences, and present two such classes whose members are efficiently recognizable. Splitting SEQ -models does not make reasoning harder, except for deciding model existence in presence of constraints (without constraints, split SEQ -models always exist).

Details