Author name cluster

Sergio Flesca

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers

2 author rows

AIJ Journal 2026 Journal Article

Revisiting the notions of extension and acceptance over incomplete abstract argumentation frameworks

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

We revisit the completion-based reasoning over incomplete Abstract Argumentation Frameworks (iAAFs), whose core is the notion of i-extension under the possible or necessary perspective, i. e. a set of arguments that, in some collective way, prove coherent and justified in at least one or in every completion, respectively. In particular, we show that, under the possible perspective, i-extensions exhibit a counterintuitive behavior, as they do not ensure conflict-freeness. Thus, we introduce the alternative notion of i*-extension, that not only fixes this behavior, but has also a positive computational impact: under various semantics of extensions, moving from i- to i*- extensions makes the complexity of the verification problem under the possible perspective move from NP-complete to P. Starting from this, we revisit the notion of accepted argument and define it as an argument belonging to at least one or every i*-extension, depending on whether the credulous or skeptical perspective is adopted. We show that this new definition does not in general coincide with the one in the literature (that is not based on the notion of i- or i*- extension), and can provide the analyst with a different perspective for reasoning over the justification of arguments in the presence of incompleteness. In this regard, we have thoroughly investigated the differences of the revisited acceptance problem with the acceptance problem in the literature, also in terms of computational complexity.

Details DOI

IJCAI Conference 2025 Conference Paper

Robustness in Single-Audience Value-based Abstract Argumentation: Complexity Results

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

We address the context of Single-Audience Value-Based Abstract Argumentation Framework (AVAF), where the arguments are labeled with the social values that they promote and the activation/deactivation of the attacks depends on the audience profile (expressed as a set of preferences between the social values). Herein, we introduce a new notion of robustness for measuring the sensitivity of the outcome of the reasoning to the extent of changes in the audience profile. In particular, for a set of arguments S or a single argument a, we define the robustness degree of the status of S or a as the maximum number k* of deletions/insertions of preferences from/into the audience profile that are tolerable, in the sense that S remains an extension (or a non-extension) or a accepted (or unaccepted) after performing at most k* deletions/insertions. We introduce the decision problems related to the computation of the robustness degree and focus on thoroughly investigating their computational complexity.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Quantitative Reasoning over Incomplete Abstract Argumentation Frameworks

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro
Giuseppina Monterosso

We introduce PERCVER and PERCACC, the problems asking for the percentages of the completions of an incomplete Abstract Argumentation Framework (iAAF) where a set of arguments S is an extension and an argument a is accepted, respectively. These problems give insights into the status of S and a more precise than the “traditional” verification and acceptance tests under the possible and necessary perspectives, that decide if S is an extension and a is accepted in at least one or every completion, respectively. As a first contribution, we investigate the relationship between the proposed framework and probabilistic AAFs (prAAFs) under the constellations approach (that, at first sight, seem to be suitable for starightforwardly encoding the quantitative reasoning underlying PERCVER and PERCACC). In this regard, we show that translating an iAAF into an equivalent prAAF requires a heavy computational cost: this backs the study of PERCVER and PERCACC as new distinguished problems. Then, we investigate the complexity of PERCVER and PERCACC, and we identify interesting islands of tractability.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Incomplete Bipolar Argumentation Frameworks

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

We introduce Incomplete Bipolar Argumentation Frameworks (iBAFs), the extension of Dung’s Abstract Argumentation Frameworks (AAFs) allowing the simultaneous presence of supports (borrowed from BAFs – Bipolar AAFs) and of uncertain elements of the argumentation graph (borrowed from iAAFs – incomplete AAFs). We investigate the computational complexity of verification problem (under the possible perspective) and the acceptance problem, by studying its sensitivity to the semantics of supports and the semantics of extensions. On the one hand, we show that adding supports on top of incompleteness does not affect the complexity of the acceptance. On the other hand, surprisingly, we show that the joint use of bipolarity and incompleteness has a deep impact on the complexity of the verification: for the semantics under which the verification over AAFs is polynomial-time solvable, although moving from AAFs to BAFs or to iAAFs does not change the complexity, the complexity of the verification over iBAFs may increase up to NP-complete.

Details

AIJ Journal 2023 Journal Article

Taking into account “who said what” in abstract argumentation: Complexity results

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

We propose a new paradigm for reasoning over abstract argumentation frameworks where the “who said what” relation, associating each argument with the set of agents who claimed it, is taken into account, along with possible information on the trustworthiness of the agents. Specifically, we extend the traditional reasoning based on the classical verification and acceptance problems and introduce a reasoning paradigm investigating how the “robustness” of a set of arguments S (in terms of being an extension or not) or of an argument a (in terms of being accepted or not) can change if what has been claimed by some agents is ignored (as if these agents were removed from the dispute modeled by the argumentation framework). In this regard, we address the problems of searching the “minimum extent” of the removal of agents that makes a set S an extension or an argument a accepted. Compared with the case where only the “yes/no” answer of the traditional verification and acceptance problems are available, the knowledge of such a minimum provides the analyst with further insights allowing them to better judge the robustness of S and a. We consider the above minimization problems in two variants, where the agents are associated with a measure of their trustworthiness or not and provide a thorough characterization of their complexities.

Details DOI

IJCAI Conference 2022 Conference Paper

Abstract Argumentation Frameworks with Marginal Probabilities

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

In the context of probabilistic AAFs, we intro- duce AAFs with marginal probabilities (mAAFs) requiring only marginal probabilities of argu- ments/attacks to be specified and not relying on the independence assumption. Reasoning over mAAFs requires taking into account multiple probability distributions over the possible worlds, so that the probability of extensions is not determined by a unique value, but by an interval. We focus on the problems of computing the max and min probabil- ities of extensions over mAAFs under Dung’s se- mantics, characterize their complexity, and provide closed formulas for polynomial cases.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Reasoning over Argument-Incomplete AAFs in the Presence of Correlations

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

We introduce "argument-incomplete Abstract Argumentation Frameworks with dependencies", that extend the traditional abstract argumentation reasoning to the case where some arguments are uncertain and correlated through logical dependencies (such as mutual exclusion, implication, etc. ). We characterize the complexities of the problems DSAT of deciding the satisfiability of the dependencies and PDVER of verifying extensions, and show how they depend on the forms of dependencies and, for PDVER, also on the semantics of the extensions.

PDF Details DOI

KR Conference 2021 Conference Paper

Reasoning over Attack-incomplete AAFs in the Presence of Correlations

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

Attack-Incomplete Abstract Argumentation Frameworks (att- iAAFs) are a popular extension of AAFs where attacks are marked as uncertain when they are not unanimously per- ceived by different agents reasoning on the same arguments. We here extend att-iAAFs with the possibility of specifying correlations involving the uncertain attacks. This feature sup- ports a unified and more precise representation of the differ- ent scenarios for the argumentation, where, for instance, it can be stated that an attack α has to be considered only if an attack β is considered, or that α and β are alternative, and so on. In order to provide a user-friendly language for spec- ifying the correlations, we allow the argumentation analyst to express them in terms of a set of elementary dependen- cies, using common logical operators (namely, OR, NAND, CHOICE, ⇒). In this context, we focus on the problem of verifying extensions under the possible perspective, and study the sensitivity of its computational complexity to the forms of correlations expressed and the semantics of the extensions.

PDF Details DOI

ECAI Conference 2020 Conference Paper

Embedding the Trust Degrees of Agents in Abstract Argumentation

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

We propose a new paradigm for reasoning over abstract argumentation frameworks where the trustworthiness of the agents is taken into account. In particular, we study the problems of computing the minimum trust degree τ * such that, if we discard the arguments said only by agents whose trust degree is not greater than τ *, a given set of arguments S (resp. , argument a), that is not necessarily an extension (resp. , (credulously) accepted) over the original argumentation framework, becomes an extension (resp. , (credulously) accepted). Solving these problems helps reason on how the robustness of sets of arguments and single arguments depends on what is considered trustworthy or not. We thoroughly characterize the computational complexity of the considered problems, along with some variants where a different aggregation mechanism is used to decide the arguments to discard.

Details

IJCAI Conference 2020 Conference Paper

Revisiting the Notion of Extension over Incomplete Abstract Argumentation Frameworks

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

We revisit the notion of i-extension, i. e. , the adaption of the fundamental notion of extension to the case of incomplete Abstract Argumentation Frameworks. We show that the definition of i-extension raises some concerns in the "possible" variant, e. g. , it allows even conflicting arguments to be collectively considered as members of an (i-)extension. Thus, we introduce the alternative notion of i*-extension overcoming the highlighted problems, and provide a thorough complexity characterization of the corresponding verification problem. Interestingly, we show that the revisitation not only has beneficial effects for the semantics, but also for the complexity: under various semantics, the verification problem under the possible perspective moves from NP-complete to P.

PDF Details DOI

AIJ Journal 2019 Journal Article

Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

The complexity of the probabilistic counterparts of the classical verification and acceptance problems is investigated over probabilistic Abstract Argumentation Frameworks (prAAFs), in a setting more general than that considered in the current literature, where the complexity has been characterized only under the assumption of independence between arguments/defeats. The complexity of the problems is shown to range from FP to F P # P -complete, with F P ‖ N P -complete cases, depending on the semantics of the extensions, the representation paradigm used for encoding the prAAF, and the imposed correlations between arguments/defeats, thus providing a thorough analysis of the sensitivity to several aspects. In this regard, in order to allow the study of the impact of different forms of correlations between arguments/defeats on the complexity, a new form of prAAF is introduced, called gen. It is based on the well-known paradigm of world-set descriptors and world-set sets for representing probabilities, and it allows the correlations to be easily and explicitly expressed. Interestingly, the introduction of gen is shown to be also a standalone contribution as a powerful representation paradigm for prAAFs, owing to its high expressiveness, compactness, and the possibility to support user-friendly mechanisms for defining correlations.

Details DOI

IJCAI Conference 2019 Conference Paper

Complexity of Fundamental Problems in Probabilistic Abstract Argumentation: Beyond Independence (Extended Abstract)

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

The complexity of the probabilistic counterparts of the verification and acceptance problems is investigated over probabilistic Abstract Argumentation Frameworks (prAAFs), in a setting more general than the literature, where the complexity has been characterized only under independence between arguments/defeats. The complexity of these problems is shown to depend on the semantics of the extensions, the way of encoding the prAAF, and the correlations between arguments/defeats. In this regard, in order to study the impact of different correlations between arguments/defeats on the complexity, a new form of prAAF is introduced, called gen. It is based on the well-known paradigm of world-set sets, and it allows the correlations to be easily distinguishable.

PDF Details

IJCAI Conference 2018 Conference Paper

Probabilistic bipolar abstract argumentation frameworks: complexity results

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

Probabilistic Bipolar Abstract Argumentation Frameworks (prBAFs), combining the possibility of specifying supports between arguments with a probabilistic modeling of the uncertainty, are considered, and the complexity of the fundamentalproblem of computing extensions' probabilities is addressed. The most popular semantics of supports and extensions are considered, as well as different paradigms for defining the probabilistic encoding of the uncertainty. Interestingly, the presence of supports, which does not alter the complexity of verifying extensions in the deterministic case, is shown to introduce a new source of complexity in some probabilistic settings, for which tractable cases are also identified.

PDF Details

ECAI Conference 2016 Conference Paper

Computing Extensions' Probabilities in Probabilistic Abstract Argumentation: Beyond Independence

Bettina Fazzinga
Sergio Flesca
Filippo Furfaro

We characterize the complexity of the problem of computing the probabilities of the extensions in probabilistic abstract argumentation. We consider all the most popular semantics of extensions (admissible, stable, preferred, complete, grounded, ideal-set, ideal and semi-stable) and different forms of correlations that can be defined between arguments and defeats. We show that the complexity of the problem ranges from FP to FP#P-complete, with FP||NP-complete cases, depending on the semantics of the extensions and the imposed correlations.

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

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

I&C Journal 2006 Journal Article

Weighted path queries on semistructured databases

Sergio Flesca
Filippo Furfaro
Sergio Greco

Path queries have been extensively used to query semistructured data, such as the Web and XML documents. In this paper we introduce weighted path queries, an extension of path queries enabling several classes of optimization problems (such as the computation of shortest paths) to be easily expressed. Weighted path queries are based on the notion of weighted regular expression, i. e. , a regular expression whose symbols are associated to a weight. We characterize the problem of answering weighted path queries and provide an algorithm for computing their answer. We also show how weighted path queries can be effectively embedded into query languages for XML data to express in a simple and compact form several meaningful research problems.

Details DOI

LPAR Conference 2001 Conference Paper

The Elog Web Extraction Language

Robert Baumgartner
Sergio Flesca
Georg Gottlob

Abstract This paper illustrates some aspects of the visual wrapper generation tool Lixto and describes its internal declarative logic-based language Elog. In particular, it gives an example scenarioand contains a detailed description of predicates including their input/output behavior and introduces several new conditions. Additionally, entity relationship diagrams of filters and patterns are depicted and some words on the implementation are issued. Finally, some possible ramifications are discussed.

Details