Author name cluster

Sergio Greco

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.

45 papers

2 author rows

AAAI Conference 2026 System Paper

ARGUS: Towards End-to-End Argument Mining with Large Language Models

Ettore Caputo
Sergio Greco
Lucio La Cava

We present ARGUS, an end-to-end Argument Mining (AM) tool that exploits Large Language Models (LLMs) to automatically perform all core AM tasks, i.e., Argument Component Segmentation, Classification, Relation Identification, and Relation Classification. Furthermore, ARGUS builds the corresponding argumentation framework (AF) and seamlessly integrates symbolic solvers to compute extensions and perform formal reasoning. ARGUS is designed to ensure broad flexibility and usability, supporting any open-source or commercial LLMs and symbolic solvers, providing a ready-to-use platform for exploring neuro-symbolic approaches to argumentation in both research and practical applications.

PDF Details DOI

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

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

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

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

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

AIJ Journal 2022 Journal Article

Preference-based inconsistency-tolerant query answering under existential rules

Marco Calautti
Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Ontology-mediated query answering (OMQA) emerged as a paradigm to enhance querying of data sources with an ontology that encodes background knowledge. In applications involving large amounts of data from multiple data sources, it might well be the case that inconsistency arises, making standard query answering useless, since everything is entailed by an inconsistent knowledge base. Being able to provide meaningful query answers in the presence of inconsistency is thus a critical issue to make OMQA systems successful in practice. The problem of querying inconsistent knowledge has attracted a great deal of interest over the years. Different inconsistency-tolerant semantics of query answering have been proposed, that is, approaches to answer queries in a meaningful way despite the knowledge at hand being inconsistent. Most of the semantics in the literature are based on the notion of repair, that is, a “maximal” consistent subset of the database. In general, there can be several repairs, so it is often natural and desirable to express preferences among them. In this paper, we propose a framework for querying inconsistent knowledge bases under user preferences for existential rule languages. Specifically, we introduce preference rules, a declarative formalism which enable users to express (i) preferences over both the database and the knowledge that can be derived from it via an ontology, and (ii) preconditions for preferences to hold. We then define two notions of preferred repairs which take preference rules into account. This naturally leads us to introducing preference-aware counterparts of popular inconsistency-tolerant semantics, where only preferred repairs are considered for query answering. We provide a thorough analysis of the data and combined complexity of different relevant problems for a wide range of existential rule languages.

Details DOI

TCS Journal 2022 Journal Article

Query answering over inconsistent knowledge bases: A probabilistic approach

Marco Calautti
Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Consistent query answering (CQA) is a widely accepted paradigm for querying inconsistent knowledge bases (KBs). A consistent answer to a query is a tuple that is an answer to the query over every repair of the KB, which is in turn a consistent KB whose extensional knowledge “minimally” differs from the original one's. This coarse-grained classification of answers into consistent and non-consistent ones lacks any information about their degree of consistency, i. e. , how likely it is that a tuple is an answer to the query, when considering all the repaired KBs. To overcome this limitation, we consider a fine-grained notion of repair for KBs with equality-generating dependencies (EGDs), based on attribute-level updates, and exploit this notion to propose a probabilistic CQA approach, which associates a confidence to each answer, thereby providing more informative query answers. We first show that computing the query answer confidence is # P -hard. Then, in the light of this intractability result, we study the existence of efficient randomized, approximation schemes. In particular, we show that absolute error approximation schemes always exist in the general case, while more refined relative error approximation schemes, i. e. , fully polynomial-time, randomized approximation schemes (FPRAS) exist when assuming that the constraints of the knowledge base are primary keys. Finally, we extend our framework to knowledge bases with tuple-generating dependencies (TGDs) and generalize our approximability results to the new setting, and prove additional inapproximability results.

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

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

IS Journal 2021 Journal Article

Incremental Skeptical Preferred Acceptance in Dynamic Argumentation Frameworks

Gianvincenzo Alfano
Sergio Greco

In this article, we tackle the problem of efficiently recomputing the skeptical acceptance of dynamic argumentation frameworks under the well-known preferred semantics. We discuss an incremental algorithmic solution whose main idea is that of exploiting the initial knowledge (including the update to perform) in order to identify a potentially small portion of the argumentation framework. Such a portion is sufficient to compute the skeptical preferred acceptance of a goal argument w. r. t. the whole updated framework. We also discuss on how similar ideas extend to more general argumentation frameworks.

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

KR Conference 2020 Conference Paper

Preference-based Inconsistency-Tolerant Query Answering under Existential Rules

Marco Calautti
Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Query answering over inconsistent knowledge bases is a problem that has attracted a great deal of interest over the years. Different inconsistency-tolerant semantics have been proposed, and most of them are based on the notion of repair, that is, a "maximal" consistent subset of the database. In general, there can be several repairs, so it is often natural and desirable to express preferences among them. In this paper, we propose a framework for querying inconsistent knowledge bases under user preferences for existential rule languages. We provide generalizations of popular inconsistency-tolerant semantics taking preferences into account and study the data and combined complexity of different relevant problems.

PDF Details DOI

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 2018 Conference Paper

Computing Approximate Query Answers over Inconsistent Knowledge Bases

Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Consistent query answering is a principled approach for querying inconsistent knowledge bases. It relies on the notion of a "repair", that is, a maximal consistent subset of the facts in the knowledge base. One drawback of this approach is that entire facts are deleted to resolve inconsistency, even if they may still contain useful "reliable" information. To overcome this limitation, we propose a new notion of repair allowing values within facts to be updated for restoring consistency. This more fine-grained repair primitive allows us to preserve more information in the knowledge base. We also introduce the notion of a "universal repair", which is a compact representation of all repairs. Then, we show that consistent query answering in our framework is intractable (coNP-complete). In light of this result, we develop a polynomial time approximation algorithm for computing a sound (but possibly incomplete) set of consistent query answers.

PDF Details

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

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

IJCAI Conference 2015 Conference Paper

Logic Program Termination Analysis Using Atom Sizes

Marco Calautti
Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Recent years have witnessed a great deal of interest in extending answer set programming with function symbols. Since the evaluation of a program with function symbols might not terminate and checking termination is undecidable, several classes of logic programs have been proposed where the use of function symbols is limited but the program evaluation is guaranteed to terminate. In this paper, we propose a novel class of logic programs whose evaluation always terminates. The proposed technique identifies terminating programs that are not captured by any of the current approaches. Our technique is based on the idea of measuring the size of terms and atoms to check whether the rule head size is bounded by the body, and performs a more fine-grained analysis than previous work. Rather than adopting an all-ornothing approach (either we can say that the program is terminating or we cannot say anything), our technique can identify arguments that are “limited” (i. e. , where there is no infinite propagation of terms) even when the program is not entirely recognized as terminating. Identifying arguments that are limited can support the user in the problem formulation and help other techniques that use limited arguments as a starting point. Another useful feature of our approach is that it is able to leverage external information about limited arguments. We also provide results on the correctness, the complexity, and the expressivity of our technique.

PDF Details

IJCAI Conference 2013 Conference Paper

Bounded Programs: A New Decidable Class of Logic Programs with Function Symbols

Sergio Greco
Cristian Molinaro
Irina Trubitsyna

While function symbols are widely acknowledged as an important feature in logic programming, they make common inference tasks undecidable. To cope with this problem, recent research has focused on identifying classes of logic programs imposing restrictions on the use of function symbols, but guaranteeing decidability of common inference tasks. This has led to several criteria, called termination criteria, providing sufficient conditions for a program to have finitely many stable models, each of finite size. This paper introduces the new class of bounded programs which guarantees the aforementioned property and strictly includes the classes of programs determined by current termination criteria. Different results on the correctness, the expressiveness, and the complexity of the class of bounded programs are presented.

PDF Details DOI

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

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