Author name cluster

Francesco Parisi

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.

47 papers

2 author rows

AAAI Conference 2026 Conference Paper

Conditional Probabilistic Bipolar Argumentation Framework: Explanations, Complexity and Approximation

Gianvincenzo Alfano
Sergio Greco
Domenico Mandaglio
Francesco Parisi
Irina Trubitsyna

Recently, there has been an increasing interest in extending Dung's framework with probability theory, leading to the Probabilistic Argumentation Framework (PAF), and with supports in addition to attacks, leading to the Bipolar Argumentation Framework (BAF). In this paper, we introduce the Conditional Probabilistic Bipolar Argumentation Framework (CPBAF), which extends Probabilistic and Bipolar AF by allowing conditional probabilities on arguments, attacks, and on (possibly cyclic) supports. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP^#P-hard and propose polynomial approximation algorithms with bounded additive error for CPBAF where cycles with an odd number of attacks are forbidden.

PDF Details DOI

AIJ Journal 2025 Journal Article

Constraints and lifting-based (conditional) preferences in abstract argumentation

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dealing with controversial information is an important issue in several application contexts. Formal argumentation enables reasoning on arguments for and against a claim to decide on an outcome. Abstract Argumentation Framework (AF) has emerged as a central formalism in argument-based reasoning. In recent years there has been an increasing interest in extending AF to facilitate the knowledge representation and reasoning process. In this paper, we present an extension of AF that allows for the representation of labelled constraints and labelled preferences. A labelled argument is of the form in ( a ), out ( a ), or und ( a ), where a is an argument, whereas in, out, and und denote the acceptance status (i. e. , accepted, rejected, undecided, respectively) of the specified argument. We start by considering an extension of AF with labelled constraints, namely Labelled Constrained AF (LCAF), then we focus on AF with labelled preferences (Labelled Preference-based AF, LPAF for short) and, finally, we introduce a general framework called Labelled Preference-based Constrained AF (LPCAF) that combines AF, labelled constraints, and labelled preferences. We also investigate an extension of AF with labelled conditional (or extended) preferences, namely Labelled extended Preference-based AF (LePAF), and its further combination with labelled constraints (Labelled extended Preference-based Constrained AF, LePCAF for short). Herein, conditional preferences are of the form a > b ← body, where a and b are labelled arguments, whereas body is a propositional formula over labelled arguments. For each framework, we define its syntax and semantics, and investigate the computational complexity of four canonical argumentation problems: existence, verification, and credulous and skeptical acceptance, under the well-known complete, stable, semi-stable, and preferred semantics.

Details DOI

IJCAI Conference 2025 Conference Paper

Credulous Acceptance in High-Order Argumentation Frameworks with Necessities: An Incremental Approach (Abstract Reprint)

Gianvincenzo Alfano
Andrea Cohen
Sebastian Gottifredi
Sergio Greco
Francesco Parisi
Guillermo R. Simari

Argumentation is an important research area in the field of AI. There is a substantial amount of work on different aspects of Dung's abstract Argumentation Framework (AF). Two relevant aspects considered separately so far are: i) extending the framework to account for recursive attacks and supports, and ii) considering dynamics, i. e. , AFs evolving over time. In this paper, we jointly deal with these two aspects. We focus on High-Order Argumentation Frameworks with Necessities (HOAFNs) which allow for attack and support relations (interpreted as necessity) not only between arguments but also targeting attacks and supports at any level. We propose an approach for the incremental evaluation of the credulous acceptance problem in HOAFNs, by “incrementally” computing an extension (a set of accepted arguments, attacks and supports), if it exists, containing a given goal element in an updated HOAFN. In particular, we are interested in monitoring the credulous acceptance of a given argument, attack or support (goal) in an evolving HOAFN. Thus, our approach assumes to have a HOAFN Δ, a goal ϱ occurring in Δ, an extension E for Δ containing ϱ, and an update u establishing some changes in the original HOAFN, and uses the extension for first checking whether the update is relevant; for relevant updates, an extension of the updated HOAFN containing the goal is computed by translating the problem to the AF domain and leveraging on AF solvers. We provide formal results for our incremental approach and empirically show that it outperforms the evaluation from scratch of the credulous acceptance problem for an updated HOAFN.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Even-if Explanations: Formal Foundations, Priorities and Complexity

Gianvincenzo Alfano
Sergio Greco
Domenico Mandaglio
Francesco Parisi
Reza Shahbazian
Irina Trubitsyna

Explainable AI has received significant attention in recent years. Machine learning models often operate as black boxes, lacking explainability and transparency while supporting decision-making processes. Local post-hoc explainability queries attempt to answer why individual inputs are classified in a certain way by a given model. While there has been important work on counterfactual explanations, less attention has been devoted to semifactual ones. In this paper, we focus on local post-hoc explainability queries within the semifactual `even-if' thinking and their computational complexity among different classes of models, and show that both linear and tree-based models are strictly more interpretable than neural networks. After this, we introduce a preference-based framework enabling users to personalize explanations based on their preferences, both in the case of semifactuals and counterfactuals, enhancing interpretability and user-centricity. Finally, we explore the complexity of several interpretability problems in the proposed preference-based framework and provide algorithms for polynomial cases.

PDF Details DOI

KR Conference 2025 Conference Paper

Extending Abstract Argumentation Frameworks with Knowledge Bases

Gianvincenzo Alfano
Sergio Greco
Cristian Molinaro
Francesco Parisi
Irina Trubitsyna

Dung's abstract Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning more intuitive and expressive. In this paper, we present the Knowledge-based Argumentation Framework (KAF), an extension of AF with a Knowledge Base (KB) expressed in DL-Lite, which includes concept and role instances describing the topology of an AF, besides additional knowledge on the domain. The KAF semantics is given by a set of KAF extensions, each consisting of an extension of the underlying AF together with a ``pertinent'' subset of the original KB, which is obtained by discarding assertions referring to arguments that have been ruled out in the AF extension. Then, the framework is further expanded into the Constrained KAF (CKAF), where a set of restricted relational calculus formulae is used for reasoning over `feasible' subframeworks that satisfy the formulae and minimally differ from the original framework. We thoroughly investigate the computational complexity of classical reasoning problems under popular argumentation semantics, and show that well-known AF-based frameworks are special cases of CKAF.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Featured Argumentation Framework: Semantics and Complexity

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dung's Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning tasks more intuitive and/or expressive. We present a novel extension of AF called Featured AF (FAF), where each argument has associated a set of features expressed by means of unary and binary facts. In such a context, a query is expressed by means of a conjunctive relational calculus formula which is evaluated over the extensions of the FAF. Then, this framework is further expanded into the so-called Extended FAF (EFAF), where a first-order logic formula (FOL) is used for reasoning over `feasible' subframeworks that satisfy the FOL formula and minimally differ from the original framework. We investigate the computational complexity of verification and acceptance problems under several semantics and show that incomplete AF (iAF) frameworks, including correlated iAF and constrained iAF, are special cases of EFAF.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

On Measuring Inconsistency in Graph Databases with Regular Path Constraints (Abstract Reprint)

John Grant
Francesco Parisi

Real-world data are often inconsistent. Although a substantial amount of research has been done on measuring inconsistency, this research concentrated on knowledge bases formalized in propositional logic. Recently, inconsistency measures have been introduced for relational databases. However, nowadays, real-world information is always more frequently represented by graph-based structures which offer a more intuitive conceptualization than relational ones. In this paper, we explore inconsistency measures for graph databases with regular path constraints, a class of integrity constraints based on a well-known navigational language for graph data. In this context, we define several inconsistency measures dealing with specific elements contributing to inconsistency in graph databases. We also define some rationality postulates that are desirable properties for an inconsistency measure for graph databases. We analyze the compliance of each measure with each postulate and find various degrees of satisfaction; in fact, one of the measures satisfies all the postulates. Finally, we investigate the data and combined complexity of the calculation of all the measures as well as the complexity of deciding whether a measure is lower than, equal to, or greater than a given threshold. It turns out that for a majority of the measures these problems are tractable, while for the other different levels of intractability are exhibited.

PDF Details DOI

AIJ Journal 2024 Journal Article

Abstract argumentation frameworks with strong and weak constraints

Gianvincenzo Alfano
Sergio Greco
Domenico Mandaglio
Francesco Parisi
Irina Trubitsyna

Dealing with controversial information is an important issue in several application contexts. Formal argumentation enables reasoning on arguments for and against a claim to decide on an outcome. Dung's abstract Argumentation Framework (AF) has emerged as a central formalism in argument-based reasoning. Key aspects of the success and popularity of Dung's framework include its simplicity and expressiveness. Integrity constraints help to express domain knowledge in a compact and natural way, thus keeping easy the modeling task even for problems that otherwise would be hard to encode within an AF. In this paper, we first explore two intuitive semantics based on Kleene and Lukasiewicz logics, respectively, for AF augmented with (strong) constraints—the resulting argumentation framework is called Constrained AF (CAF). Then, we propose a new argumentation framework called Weak constrained AF (WAF) that enhances CAF with weak constraints. Intuitively, these constraints can be used to find “optimal” solutions to problems defined through CAF. We provide a detailed complexity analysis of CAF and WAF, showing that strong constraints do not increase the expressive power of AF in most cases, while weak constraints systematically increase the expressive power of CAF (and AF) under several well-known argumentation semantics.

Details DOI

AAAI Conference 2024 Conference Paper

Complexity of Credulous and Skeptical Acceptance in Epistemic Argumentation Framework

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dung’s Argumentation Framework (AF) has been extended in several directions. Among the numerous proposed extensions, three of them seem to be of particular interest and have correlations between them. These extensions are: constrained AF (CAF), where AF is augmented with (strong) constraints; epistemic AF (EAF), where AF is augmented with epistemic constraints; and incomplete AF (iAF), where arguments and attacks can be uncertain. While the complexity and expressiveness of CAF and iAF have been studied, that of EAF has not been explored so far. In this paper we investigate the complexity and expressivity of EAF. To this end, we first introduce the Labeled CAF (LCAF), a variation of CAF where constraints are defined over the alphabet of labeled arguments. Then, we investigate the complexity of credulous and skeptical reasoning and show that: i) EAF is more expressive than iAF (under preferred semantics), ii) although LCAF is a restriction of EAF where modal operators are not allowed, these frameworks have the same complexity, iii) the results for LCAF close a gap in the characterization of the complexity of CAF. Interestingly, even though EAF has the same complexity as LCAF, it allows modeling domain knowledge in a more natural and easy-to-understand way.

PDF Details DOI

KR Conference 2024 Conference Paper

Counterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Explainable Artificial Intelligence and Formal Argumentation have received significant attention in recent years. Argumentation frameworks are useful for representing knowledge and reasoning on it. Counterfactual and semifactual explanations are interpretability techniques that provide insights into the outcome of a model by generating alternative hypothetical instances. While there has been important work on counterfactual and semifactual explanations for Machine Learning (ML) models, less attention has been devoted to these kinds of problems in argumentation. In this paper, we explore counterfactual and semifactual reasoning in abstract Argumentation Framework. We investigate the computational complexity of counterfactual- and semifactual-based reasoning problems, showing that they are generally harder than classical argumentation problems such as credulous and skeptical acceptance. Finally, we show that counterfactual and semifactual queries can be encoded in weak-constrained Argumentation Framework, and provide a computational strategy through ASP solvers.

PDF Details DOI

AIJ Journal 2024 Journal Article

Credulous acceptance in high-order argumentation frameworks with necessities: An incremental approach

Gianvincenzo Alfano
Andrea Cohen
Sebastian Gottifredi
Sergio Greco
Francesco Parisi
Guillermo R. Simari

Argumentation is an important research area in the field of AI. There is a substantial amount of work on different aspects of Dung's abstract Argumentation Framework (AF). Two relevant aspects considered separately so far are: i) extending the framework to account for recursive attacks and supports, and i i ) considering dynamics, i. e. , AFs evolving over time. In this paper, we jointly deal with these two aspects. We focus on High-Order Argumentation Frameworks with Necessities (HOAFNs) which allow for attack and support relations (interpreted as necessity) not only between arguments but also targeting attacks and supports at any level. We propose an approach for the incremental evaluation of the credulous acceptance problem in HOAFNs, by “incrementally” computing an extension (a set of accepted arguments, attacks and supports), if it exists, containing a given goal element in an updated HOAFN. In particular, we are interested in monitoring the credulous acceptance of a given argument, attack or support (goal) in an evolving HOAFN. Thus, our approach assumes to have a HOAFN Δ, a goal ϱ occurring in Δ, an extension E for Δ containing ϱ, and an update u establishing some changes in the original HOAFN, and uses the extension for first checking whether the update is relevant; for relevant updates, an extension of the updated HOAFN containing the goal is computed by translating the problem to the AF domain and leveraging on AF solvers. We provide formal results for our incremental approach and empirically show that it outperforms the evaluation from scratch of the credulous acceptance problem for an updated HOAFN.

Details DOI

IJCAI Conference 2024 Conference Paper

General Epistemic Abstract Argumentation Framework: Semantics and Complexity

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Epistemic Abstract Argumentation Framework (EAAF) extends Dung's framework (AAF)---a central formalism in AI for modeling disputes among agents---by allowing the representation of epistemic knowledge. In particular, EAAF augments AAF with weak and strong epistemic attacks whose intuitive meaning is that an argument a defeats an argument b by means of a weak (resp. strong) epistemic attack if a is true in every (resp. at least one) extension. So far, the semantics of EAAF has been defined only for a restricted class of frameworks, namely acyclic EAAF, where epistemic attacks do not occur in any cycle. In this paper, we provide an intuitive semantics for (general) EAAF that naturally extends that for AAF as well as that for acyclic EAAF. After providing some fundamental properties and giving an algorithm that enables the computation of EAAF semantics, by relying on state-of-the-art AAF-solvers, we investigate the complexity of canonical argumentation problems.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

On General Epistemic Abstract Argumentation Frameworks

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Epistemic Abstract Argumentation Framework (EAAF) extends Dung’s framework (AAF) by allowing the representation of epistemic attacks. So far, the semantics of EAAF has been defined only for a restricted class of frameworks, namely acyclic EAAF, where epistemic attacks do not occur in any cycle. In this paper, we provide an intuitive semantics for (general) EAAF that naturally extends that for AAF as well as that for acyclic EAAF.

PDF

AIJ Journal 2024 Journal Article

On measuring inconsistency in graph databases with regular path constraints

John Grant
Francesco Parisi

Details DOI

AAAI Conference 2023 Conference Paper

Abstract Argumentation Framework with Conditional Preferences

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dung's abstract Argumentation Framework (AF) has emerged as a central formalism in the area of knowledge representation and reasoning. Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way. Preference-based AF (PAF) has been proposed to extend AF with preferences of the form a > b, whose intuitive meaning is that argument a is better than b. In this paper we generalize PAF by introducing conditional preferences of the form a > b \leftarrow body that informally state that a is better than b whenever the condition expressed by body is true. The resulting framework, namely Conditional Preference-based AF (CPAF), extends the PAF semantics under three well-known preference criteria, i.e. democratic, elitist, and KTV. After introducing CPAF, we study the complexity of the verification problem (deciding whether a set of arguments is a ``best'' extension) as well as of the credulous and skeptical acceptance problems (deciding whether a given argument belongs to any or all ``best'' extensions, respectively) under multiple-status semantics (that is, complete, preferred, stable, and semi-stable semantics) for the above-mentioned preference criteria.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Complexity of Verification and Existence Problems in Epistemic Argumentation Framework

Gianvincenzo Alfano
Sergio Greco
Domenico Mandaglio
Francesco Parisi
Irina Trubitsyna

Dung’s Argumentation Framework (AF) has been extended in several directions. An interesting extension, among others, is the Epistemic AF (EAF) which allows representing the agent’s belief by means of epistemic constraints. In particular, an epistemic constraint is a propositional formula over labeled arguments (e. g. in(a), out(c)) extended with the modal operators K and M that intuitively state that the agent believes that a given formula is certainly or possibly true, respectively. In this paper, focusing on EAF, we investigate the complexity of the possible and necessary variants of three canonical problems in abstract argumentation: verification, existence, and non-empty existence. Moreover, we explore the relationship between EAF and incomplete AF (iAF), an extension of AF where arguments and attacks may be uncertain. Our complexity analysis shows that the verification problem in iAF can be naturally reduced to the verification in EAF, while it turns out that a similar result cannot hold for the necessary (non-empty) existence problem.

Details

AAMAS Conference 2023 Conference Paper

Epistemic Abstract Argumentation Framework: Formal Foundations, Computation and Complexity

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dung’s Abstract Argumentation Framework (AAF) has emerged as a central formalism in AI for modeling disputes among agents. In this paper, we introduce an extension of Dung’s framework, called Epistemic Abstract Argumentation Framework (EAAF), which enhances AAF by allowing the representation of some pieces of epistemic knowledge. We generalize the concept of attack in AAF, introducing strong and weak epistemic attacks in EAAF, whose intuitive meaning is that an attacked argument is epistemically accepted only if the attacking argument is possibly or certainly rejected, respectively. We provide an intuitive semantics for EAAF that naturally extends that for AAF, and give an algorithm that enables the computation of epistemic extensions by using AAF-solvers. Finally, we analyze the complexity of the following argumentation problems: verification, i. e. checking whether a set of arguments is an epistemic extension; existence, i. e. checking whether there is at least one (non-empty) epistemic extension; and acceptance, i. e. checking whether an argument is epistemically accepted, under well-known argumentation semantics (i. e. grounded, complete, and preferred).

PDF

AIJ Journal 2023 Journal Article

Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks

Gianvincenzo Alfano
Marco Calautti
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dung's Argumentation Framework (AF) has been extended in several directions, including the possibility of representing uncertainty about the existence of arguments and attacks. In this regard, two main proposals have been introduced in the literature: Probabilistic Argumentation Framework (PrAF) and Incomplete Argumentation Framework (iAF). PrAF is an extension of AF with probability theory, thus representing quantified uncertainty. In contrast, iAF represents unquantified uncertainty, that is it can be seen as a special case where we only know that some elements (arguments or attacks) are uncertain. In this paper, we first address the problem of computing the probability that a given argument is accepted in PrAF. This is carried out by introducing the concept of probabilistic explanation for any given (probabilistic) extension. We show that the complexity of the problem is FP # P -hard and propose polynomial approximation algorithms with bounded additive error for PrAFs where odd-length cycles are forbidden. We investigate the approximate complexity of the related FP # P -hard problems of credulous and skeptical acceptance in PrAF, showing that they are generally harder than the problem of computing the probability that a given argument is accepted. Next we consider iAF and, after showing some equivalence properties among classes of iAFs, we study iAF as a special case of PrAF where uncertain elements have associated a probability equal to 1/2. Finally, given this result, we investigate the relationships between iAF acceptance problems and probabilistic acceptance in PrAF.

Details DOI

AIJ Journal 2023 Journal Article

On measuring inconsistency in definite and indefinite databases with denial constraints

Francesco Parisi
John Grant

Real-world databases are often inconsistent. Although there has been an extensive body of work on handling inconsistency, little work has been done on measuring inconsistency in databases. In this paper, building on work done on measuring inconsistency in propositional knowledge bases, we explore inconsistency measures (IMs) for definite and indefinite databases with denial constraints. We first introduce database IMs that are inspired by well-established methods to quantify inconsistency in propositional knowledge bases, but are tailored to the relational database context where data is generally the reason for inconsistency, not the integrity constraints. Then, we analyze the compliance of the database IMs with rationality postulates for both definite and indefinite databases. Finally, we investigate the complexity of the inconsistency measurement problem as well as of the problems of deciding whether the inconsistency is lower than, greater than, or equal to a given threshold for both the definite and the indefinite cases.

Details DOI

NMR Workshop 2023 Conference Paper

On the Conditional Preference-based Argumentation Framework

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dung’s abstract Argumentation Framework (AF) has emerged as a central formalism in the area of knowledge representation and reasoning. Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way. Preference-based AF (PAF) has been proposed to extend AF with preferences of the form 𝑎 > 𝑏, whose intuitive meaning is that argument 𝑎 is better than 𝑏. In this paper we discuss the recently proposed Conditional Preference-based Argumentation Framework (CPAF) [1] that extends PAF by introducing conditional preferences of the form 𝑎 > 𝑏 ← 𝑏𝑜𝑑𝑦 informally stating that 𝑎 is better than 𝑏 whenever the condition expressed by 𝑏𝑜𝑑𝑦 is true. We discuss CPAF properties and complexity results of the well-known verification and acceptance problems under multiple-status argumentation semantics.

Details

NMR Workshop 2023 Conference Paper

On the Extended Preference-based Constrained Argumentation Framework

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

In recent years there has been an increasing interest in extending Dung’s framework to facilitate the knowledge representation and reasoning process. In this paper, we discuss a recently proposed extension of abstract Argumentation Framework (AF) that allows for the representation of preferences over arguments’ truth values (3-valued preferences) [1]. For instance, we can express a preference stating that extensions where argument 𝑎 is false (i. e. defeated) are preferred to extensions where argument 𝑏 is false. Interestingly, such a framework generalizes the well-known Preference-based AF with no additional cost in terms of computational complexity for most of the classical argumentation semantics. Then, AF is further extended by considering both (3-valued) preferences and 3-valued constraints, that is constraints of the form 𝜙 ⇒ 𝑣 or 𝑣 ⇒ 𝜙, where 𝜙 is a logical formula and 𝑣 is a 3-valued truth value. We discuss the complexity of deciding acceptance of arguments in this context.

Details

IJCAI Conference 2023 Conference Paper

Preferences and Constraints in Abstract Argumentation

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

In recent years there has been an increasing interest in extending Dung's framework to facilitate the knowledge representation and reasoning process. In this paper, we present an extension of Abstract Argumentation Framework (AF) that allows for the representation of preferences over arguments' truth values (3-valued preferences). For instance, we can express a preference stating that extensions where argument a is false (i. e. defeated) are preferred to extensions where argument b is false. Interestingly, such a framework generalizes the well-known Preference-based AF with no additional cost in terms of computational complexity for most of the classical argumentation semantics. Then, we further extend AF by considering both (3-valued) preferences and 3-valued constraints, that is constraints of the form \varphi \Rightarrow v or v \Rightarrow \varphi, where \varphi is a logical formula and v is a 3-valued truth value. After investigating the complexity of the resulting framework, as both constraints and preferences may represent subjective knowledge of agents, we extend our framework by considering multiple agents and study the complexity of deciding acceptance of arguments in this context.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Relative Inconsistency Measures for Indefinite Databases with Denial Constraints

Francesco Parisi
John Grant

Handling conflicting information is an important challenge in AI. Measuring inconsistency is an approach that provides ways to quantify the severity of inconsistency and helps understanding the primary sources of conflicts. In particular, a relative inconsistency measure computes, by some criteria, the proportion of the knowledge base that is inconsistent. In this paper we investigate relative inconsistency measures for indefinite databases, which allow for indefinite or partial information which is formally expressed by means of disjunctive tuples. We introduce a postulate-based definition of relative inconsistency measure for indefinite databases with denial constraints, and investigate the compliance of some relative inconsistency measures with rationality postulates for indefinite databases as well as for the special case of definite databases. Finally, we investigate the complexity of the problem of computing the value of the proposed relative inconsistency measures as well as of the problems of deciding whether the inconsistency value is lower than, greater than, or equal to a given threshold for indefinite and definite databases.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases (Extended Abstract)

John Grant
Maria Vanina Martinez
Cristian Molinaro
Francesco Parisi

We define and investigate new inconsistency measures that are particularly suitable for dealing with inconsistent spatio-temporal information, as they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w. r. t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions, and thus define ``dimension-aware'' counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

PDF Details DOI

IS Journal 2022 Journal Article

Guest Editorial: Reasoning With Inconsistent, Incomplete, and Uncertain Knowledge

Enrico Malizia
Cristian Molinaro
Francesco Parisi

The five papers in this special section focus on the management and analysis of uncertain, incomplete, and inconsistent information. This has become a crucial issue in the development of intelligent systems. Nowadays, such systems have to efficiently manage large amounts of information of different kinds, often represented in different formats and coming from different sources, such as databases, knowledge bases, sensor networks, as well as various data-driven applications. In the presence of such complex and heterogeneous forms of information, incompleteness, inconsistency, and/or inherent uncertainty inevitably arise. These scenarios call for innovative and intelligent approaches that, by leveraging AI techniques, can explicitly represent inconsistency, incompleteness, and uncertainty, and adequately deal with them. Such approaches are crucial to model realworld scenarios, making systems more effective and successful. Moreover, in many domains, knowledge is subject to frequent changes, so handling evolving knowledge is a key feature that knowledge-based systems should provide. In domains having high-impact consequences (e. g. , healthcare and cybersecurity), intelligent systems should support human-in-the-loop models that provide tools to help users to understand and interpret the decisions they suggest, while tackling the challenges of inconsistency, incompleteness, and uncertainty. The AI community has also lately been facing the rising demand of explainable AI systems, which have inevitably to deal with inconsistency, incompleteness, and uncertainty.

Details DOI

AAAI Conference 2022 Conference Paper

Incomplete Argumentation Frameworks: Properties and Complexity

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dung’s Argumentation Framework (AF) has been extended in several directions, including the possibility of representing unquantified uncertainty about the existence of arguments and attacks. The framework resulting from such an extension is called incomplete AF (iAF). In this paper, we first introduce three new satisfaction problems named totality, determinism and functionality, and investigate their computational complexity for both AF and iAF under several semantics. We also investigate the complexity of credulous and skeptical acceptance in iAF under semi-stable semantics—a problem left open in the literature. We then show that any iAF can be rewritten into an equivalent one where either only (unattacked) arguments or only attacks are uncertain. Finally, we relate iAF to probabilistic argumentation framework, where uncertainty is quantified.

PDF Details

IJCAI Conference 2022 Conference Paper

On Preferences and Priority Rules in Abstract Argumentation

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dung's abstract Argumentation Framework (AF) has emerged as a central formalism for argumentation in AI. Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way. In this paper we first investigate the complexity of the verification as well as credulous and skeptical acceptance problems in Preference-based AF (PAF) that extends AF with preferences over arguments. Next, after introducing new semantics for AF where extensions are selected using cardinality (instead of set inclusion) criteria and investigating their complexity, we introduce a framework called AF with Priority rules (AFP) that extends AF with sequences of priority rules. AFP generalizes AF with classical set-inclusion and cardinality based semantics, suggesting that argumentation semantics can be viewed as ways to express priorities among extensions. Finally, we extend AFP by proposing AF with Priority rules and Preferences (AFP^2), where also preferences over arguments can be used to define priority rules, and study the complexity of the above-mentioned problems.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Argumentation Frameworks with Strong and Weak Constraints: Semantics and Complexity

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Dung’s abstract Argumentation Framework (AF) has emerged as a central formalism in formal argumentation. Key aspects of the success and popularity of Dung’s framework include its simplicity and expressiveness. Integrity constraints help to express domain knowledge in a compact and natural way, thus keeping easy the modeling task even for problems that otherwise would be hard to encode within an AF. In this paper, after providing an intuitive semantics based on Lukasiewicz’s logic for AFs with (strong) constraints, called Constrained AFs (CAFs), we propose Weak constrained AFs (WAFs) that enhance CAFs with weak constraints. Intuitively, these constraints can be used to find “optimal” solutions to problems defined through CAFs. We provide a detailed complexity analysis of CAFs and WAFs, showing that strong constraints do not increase the expressive power of AFs in most cases, while weak constraints systematically increase the expressive power of CAFs under several wellknown argumentation semantics.

PDF Details

IJCAI Conference 2021 Conference Paper

Defining the Semantics of Abstract Argumentation Frameworks through Logic Programs and Partial Stable Models (Extended Abstract)

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Extensions of Dung’s Argumentation Framework (AF) include the class of Recursive Bipolar AFs (Rec-BAFs), i. e. AFs with recursive attacks and supports. We show that a Rec-BAF \Delta can be translated into a logic program P_\Delta so that the extensions of \Delta under different semantics coincide with subsets of the partial stable models of P_\Delta.

PDF Details DOI

JAIR Journal 2021 Journal Article

Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases

John Grant
Maria Vanina Martinez
Cristian Molinaro
Francesco Parisi

The problem of managing spatio-temporal data arises in many applications, such as location-based services, environmental monitoring, geographic information systems, and many others. Often spatio-temporal data arising from such applications turn out to be inconsistent, i.e., representing an impossible situation in the real world. Though several inconsistency measures have been proposed to quantify in a principled way inconsistency in propositional knowledge bases, little effort has been done so far on inconsistency measures tailored for the spatio-temporal setting. In this paper, we define and investigate new measures that are particularly suitable for dealing with inconsistent spatio-temporal information, because they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions and thus define “dimension-aware” counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

PDF Details DOI

IS Journal 2021 Journal Article

Guest Editorial Argumentation-Based Reasoning

Francesco Parisi
Gerardo I. Simari

The papers in this special section focus on augmentation-based reasoning. Real-world knowledge-based systems must deal with information coming from different sources, leading to uncertainty due to incompleteness, inconsistency, and/or inherent uncertainty (such as the uncertainty present in very complex systems such as the stock market or the weather). Instead of considering such uncertain information to be useless, knowledge engineers face the challenge of putting it to good use when solving a wide range of problems. Argumentation is a useful approach in this setting: Reasons for and against a claim are analyzed to decide on an outcome, much in the same way as organized human discussions are carried out. 1–5 An important byproduct of such analyses is an accompanying explanation that can be leveraged to decide if there is information that should be used differently, discarded, or there is further information to be contemplated.

Details DOI

AIJ Journal 2021 Journal Article

Incremental computation for structured argumentation over dynamic DeLP knowledge bases

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Gerardo I. Simari
Guillermo R. Simari

Structured argumentation systems, and their implementation, represent an important research subject in the area of Knowledge Representation and Reasoning. Structured argumentation advances over abstract argumentation frameworks by providing the internal construction of the arguments that are usually defined by a set of (strict and defeasible) rules. By considering the structure of arguments, it becomes possible to analyze reasons for and against a conclusion, and the warrant status of such a claim in the context of a knowledge base represents the main output of a dialectical process. Computing such statuses is a costly process, and any update to the knowledge base could potentially have a huge impact if done naively. In this work, we investigate the case of updates consisting of both additions and removals of pieces of knowledge in the Defeasible Logic Programming (DeLP) framework, first analyzing the complexity of the problem and then identifying conditions under which we can avoid unnecessary computations—central to this is the development of structures (e. g. graphs) to keep track of which results can potentially be affected by a given update. We introduce a technique for the incremental computation of the warrant statuses of conclusions in DeLP knowledge bases that evolve due to the application of (sets of) updates. We present the results of a thorough experimental evaluation showing that our incremental approach yields significantly faster running times in practice, as well as overall fewer recomputations, even in the case of sets of updates performed simultaneously.

Details DOI

IS Journal 2021 Journal Article

Incremental Computation in Dynamic Argumentation Frameworks

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi

Dealing with controversial information is a challenging and important task for intelligent systems. Formal argumentation enables reasoning on arguments for and against a claim to decide on an outcome. An argumentation framework often models a dynamic situation where arguments as well as the way they interact frequently change over the time. As a consequence, the sets of accepted arguments (i. e. , extensions under a given semantics) often need to be computed again after performing an update. In this article, we address the problem of efficiently recomputing extensions of dynamic argumentation frameworks. We present an incremental algorithmic solution whose main idea is that of using an initial extension and the update to identify a (potentially small) portion of the argumentation framework, which is sufficient to compute an extension of the whole updated framework.

Details DOI

FLAP Journal 2021 Journal Article

On the Incremental Computation of Semantics in Dynamic Argumentation.

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Gerardo I. Simari
Guillermo Ricardo Simari

Argumentation frameworks often model dynamic situations where arguments and their relationships (e.g., attacks) frequently change over time. As a consequence, the sets of conclusions (e.g., extensions of abstract argumentation frameworks, or warranted literals for structured argumentation frameworks) often need to be computed again after performing an update. However, as most of the argumentation semantics proposed so far suffer from high computational complexity, computing the set of conclusions from scratch is costly in general. In this work, we address the problems of efficiently recomputing extensions of dynamic abstract argumentation frameworks and warranted literals in dynamic defeasible knowledge bases. In particular, we first present an incremental algorithmic solution whose main idea is that of using an initial extension and the update to identify a (potentially small) portion of an abstract argumentation framework, which is sufficient to compute an extension of the updated framework.

Details

ECAI Conference 2020 Conference Paper

Dynamics in Abstract Argumentation Frameworks with Recursive Attack and Support Relations

Gianvincenzo Alfano
Andrea Cohen
Sebastian Gottifredi
Sergio Greco
Francesco Parisi
Guillermo Ricardo Simari

Argumentation is an important topic in the field of AI. There is a substantial amount of work about different aspects of Dung’s abstract Argumentation Framework (AF). Two relevant aspects considered separately so far are extending the framework to account for recursive attacks and supports, and considering dynamics, i. e. , AFs evolving over time. In this paper, we jointly deal with these two aspects. We focus on Attack-Support Argumentation Frameworks (ASAFs) which allow for attack and support relations not only between arguments but also targeting attacks and supports at any level, and propose an approach for the incremental computation of extensions (sets of accepted arguments, attacks and supports) of updated ASAFs. Our approach assumes that an initial ASAF extension is given and uses it for first checking whether updates are irrelevant; for relevant updates, an extension of an updated ASAF is computed by translating the problem to the AF domain and leveraging on AF solvers. We experimentally show our incremental approach outperforms the direct computation of extensions for updated ASAFs.

Details

KR Conference 2020 Conference Paper

Explainable Acceptance in Probabilistic Abstract Argumentation: Complexity and Approximation

Gianvincenzo Alfano
Marco Calautti
Sergio Greco
Francesco Parisi
Irina Trubitsyna

Recently there has been an increasing interest in probabilistic abstract argumentation, an extension of Dung's abstract argumentation framework with probability theory. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP^#P-hard and propose polynomial approximation algorithms with bounded additive error for probabilistic argumentation frameworks where odd-length cycles are forbidden. This is quite surprising since, as we show, such kind of approximation algorithm does not exist for the related FP^#P-hard problem of computing the probability of the credulous acceptance of an argument, even for the special class of argumentation frameworks considered in the paper.

PDF Details DOI

ECAI Conference 2020 Conference Paper

On Measuring Inconsistency in Relational Databases with Denial Constraints

Francesco Parisi
John Grant

Real-world databases are often inconsistent. Although there has been an extensive body of work on handling inconsistency, little work has been done on measuring inconsistency in databases. In this paper, building on work done on measuring inconsistency in propositional knowledge bases, we explore inconsistency measures (IMs) for databases with denial constraints. We first introduce new database IMs that are inspired by well-established methods to quantify inconsistency in propositional knowledge bases, but are tailored to the relational database context where data are generally the reason for inconsistency, not the integrity constraints. Then, we analyze the compliance of the database IMs with rationality postulates, and investigate the complexity of the inconsistency measurement problem as well as of the problems of deciding whether the inconsistency is lower than, greater than, or equal to a given threshold.

Details

IJCAI Conference 2019 Conference Paper

An Efficient Algorithm for Skeptical Preferred Acceptance in Dynamic Argumentation Frameworks

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi

Though there has been an extensive body of work on efficiently solving computational problems for static Dung's argumentation frameworks (AFs), little work has been done for handling dynamic AFs and in particular for deciding the skeptical acceptance of a given argument. In this paper we devise an efficient algorithm for computing the skeptical preferred acceptance in dynamic AFs. More specifically, we investigate how the skeptical acceptance of an argument (goal) evolves when the given AF is updated and propose an efficient algorithm for solving this problem. Our algorithm, called SPA, relies on two main ideas: i) computing a small portion of the input AF, called "context-based" AF, which is sufficient to determine the status of the goal in the updated AF, and ii) incrementally computing the ideal extension to further restrict the context-based AF. We experimentally show that SPA significantly outperforms the computation from scratch, and that the overhead of incrementally maintaining the ideal extension pays off as it speeds up the computation.

PDF Details

KR Conference 2018 Conference Paper

An Incremental Approach to Structured Argumentation over Dynamic Knowledge Bases

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi
Gerardo Ignacio Simari
Guillermo Ricardo Simari

Considering the structure of arguments allows users to analyze reasons for and against a conclusion; the warrant status of such a conclusion in the context of a knowledge base represents the main output of a dialectical process. A naive approach to computing such statuses is costly, and any update to the knowledge base potentially has a huge impact if done in this manner. We study the case of updates consisting of both additions and removals of pieces of knowledge in the Defeasible Logic Programming (DeLP) framework, first analyzing the complexity of the problem and then identifying conditions under which we can avoid unnecessary computations— central to this is the development of data structures to keep track of which results can potentially be affected by a given update. We also present experiments showing that our incremental algorithm yields significantly lower running times in practice, as well as overall fewer recomputations.

IJCAI Conference 2017 Conference Paper

Efficient Computation of Extensions for Dynamic Abstract Argumentation Frameworks: An Incremental Approach

Gianvincenzo Alfano
Sergio Greco
Francesco Parisi

Abstract argumentation frameworks (AFs) are a well-known formalism for modelling and deciding many argumentation problems. Computational issues and evaluation algorithms have been deeply investigated for static AFs, whose structure does not change over the time. However, AFs are often dynamic as a consequence of the fact that argumentation is inherently dynamic. In this paper, we tackle the problem of incrementally computing extensions for dynamic AFs: given an initial extension and an update (or a set of updates), we devise a technique for computing an extension of the updated AF under four well-known semantics (i. e. , complete, preferred, stable, and grounded). The idea is to identify a reduced (updated) AF sufficient to compute an extension of the whole AF and use state-of-the-art algorithms to recompute an extension of the reduced AF only. The experiments reveal that, for all semantics considered and using different solvers, the incremental technique is on average two orders of magnitude faster than computing the semantics from scratch.

PDF Details

FLAP Journal 2016 Journal Article

Computing or Estimating Extensions' Probabilities over Structured Probabilistic Argumentation Frameworks.

Bettina Fazzinga
Sergio Flesca
Francesco Parisi
Adriana Pietramala

Probabilistic argumentation combines Dung’s abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that a set of arguments is an extension according to a given semantics over structured probabilistic argumentation frameworks. We focus on the most popular semantics (i. e. , admissible, stable, complete, grounded, and preferred), for which the problem of computing extension’s probabilities over structured probabilistic argumentation frameworks was shown to be FP#P -complete. Our aim is that of experimentally establishing when, due to the complexity of the problem and the size of the structured probabilistic argumentation framework, estimating the extension’s probabilities is preferable to computing it (as computing the probability cannot be done in reasonable time). To do this, we devise two algorithms: the naive one, which computes the extension’s probabilities, and the Monte-Carlo simulation one, which estimates the extension’s probabilities, and evaluate both algorithms over two datasets to compare their efficiency.

PDF Details

ECAI Conference 2016 Conference Paper

Efficient Computation of Deterministic Extensions for Dynamic Abstract Argumentation Frameworks

Sergio Greco
Francesco Parisi

We address the problem of efficiently computing the extensions of abstract argumentation frameworks (AFs) which are updated by adding/deleting arguments or attacks. We focus on the two most popular 'deterministic' semantics (namely, grounded and ideal) and present two approaches for their incremental computation, well-suited to dynamic applications where updates to an initial AF are frequently performed to take into account new available knowledge.

Details

JELIA Conference 2016 Conference Paper

Incremental Computation of Deterministic Extensions for Dynamic Argumentation Frameworks

Sergio Greco
Francesco Parisi

Abstract We address the problem of efficiently recomputing the extensions of abstract argumentation frameworks (AFs) which are updated by adding/deleting arguments or attacks. In particular, after identifying some properties that hold for updates of AFs under several well-known semantics, we focus on the two most popular ‘deterministic’ semantics (namely, grounded and ideal ) and present two algorithms for their incremental computation, well-suited to dynamic applications where updates to an initial AF are frequently performed to take into account new available knowledge. We experimentally validated the proposed approach.

Details

JAIR Journal 2016 Journal Article

Knowledge Representation in Probabilistic Spatio-Temporal Knowledge Bases

Francesco Parisi
John Grant

We represent knowledge as integrity constraints in a formalization of probabilistic spatio-temporal knowledge bases. We start by defining the syntax and semantics of a formalization called PST knowledge bases. This definition generalizes an earlier version, called SPOT, which is a declarative framework for the representation and processing of probabilistic spatio-temporal data where probability is represented as an interval because the exact value is unknown. We augment the previous definition by adding a type of non-atomic formula that expresses integrity constraints. The result is a highly expressive formalism for knowledge representation dealing with probabilistic spatio-temporal data. We obtain complexity results both for checking the consistency of PST knowledge bases and for answering queries in PST knowledge bases, and also specify tractable cases. All the domains in the PST framework are finite, but we extend our results also to arbitrarily large finite domains.

PDF Details DOI

IJCAI Conference 2013 Conference Paper

On the Complexity of Probabilistic Abstract Argumentation

Bettina Fazzinga
Sergio Flesca
Francesco Parisi

Probabilistic abstract argumentation combines Dung’s abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that a set of arguments is an extension according to a given semantics. We focus on the most popular semantics (i. e. , admissible, stable, complete, grounded, preferred, ideal), and show the following dichotomy result: computing the probability that a set of arguments is an extension is either PTIME or FP#P -complete depending on the semantics adopted. Our PTIME results are particularly interesting, as they hold for some semantics for which no polynomial-time technique was known so far.

PDF Details DOI

AIJ Journal 2010 Journal Article

An AGM-style belief revision mechanism for probabilistic spatio-temporal logics

John Grant
Francesco Parisi
Austin Parker
V.S. Subrahmanian

There is now extensive interest in reasoning about moving objects. A probabilistic spatio-temporal (PST) knowledge base (KB) contains atomic statements of the form “Object o is/was/will be in region r at time t with probability in the interval [ ℓ, u ] ”. In this paper, we study mechanisms for belief revision in PST KBs. We propose multiple methods for revising PST KBs. These methods involve finding maximally consistent subsets and maximal cardinality consistent subsets. In addition, there may be applications where the user has doubts about the accuracy of the spatial information, or the temporal aspects, or about the ability to recognize objects in such statements. We study belief revision mechanisms that allow changes to the KB in each of these three components. Finally, there may be doubts about the assignment of probabilities in the KB. Allowing changes to the probability of statements in the KB yields another belief revision mechanism. Each of these belief revision methods may be epistemically desirable for some applications, but not for others. We show that some of these approaches cannot satisfy AGM-style axioms for belief revision under certain conditions. We also perform a detailed complexity analysis of each of these approaches. Simply put, all belief revision methods proposed that satisfy AGM-style axioms turn out to be intractable with the exception of the method that revises beliefs by changing the probabilities (minimally) in the KB. We also propose two hybrids of these basic approaches to revision and analyze the complexity of these hybrid methods.

Details DOI

KR Conference 2008 Conference Paper

Inconsistency Management Policies

Maria Vanina Martinez
Francesco Parisi
Andrea Pugliese
Gerardo I. Simari
V. S. Subrahmanian

Though there is much work on how inconsistency in databases should be managed, there is good reason to believe that end users will want to bring their domain expertise and needs to bear in how to deal with inconsistencies. In this paper, we propose the concept of Inconsistency Management Policies (IMPs). We show that IMPs are rich enough to specify many types of inconsistency management methods proposed previously, but provide end users with tools that allow them to use the policies that they want. Our policies are also capable of allowing inconsistency to persist in the database or of eliminating more than a minimal subset of tuples involved in the inconsistency. We present a formal axiomatic definition of IMPs and present appropriate complexity results, together with results linking different IMPs together. We extend the relational algebra (RA) to incorporate IMPs and present theoretical results showing how IMPs and classical RA operators interact.