Stefano Bistarelli

AAAI Conference 2025 Conference Paper

Fast Computing of Dung Semantics in Acyclic Probabilistic Argumentation Frameworks

• Stefano Bistarelli
• Victor David
• Pierre Monnin
• Francesco Santini
• Carlo Taticchi

This paper presents fast and exact methods for computing the probability of an argument’s acceptance using Dung’s semantics in the Constellation paradigm of Abstract Argumentation. For (directed) Singly-Connected Graphs (SCGs), the problem can now be solved in linearithmic time instead of being exponential in the number of attacks, as reported in the literature. Moreover, in the more general case of Directed Acyclic Graphs (DAGs), we provide an algorithm whose time complexity is linearithmic in the product of the out-degree of dependent arguments, i.e., arguments reaching the argument considered for acceptance through multiple paths in the graph. We theoretically show that this complexity is lower than the lower bound of the (exact) Constellation method, which is also supported by empirical results. Our approach to DAGs is also compared with the (approximate) Monte-Carlo method, which is stopped when exact results are obtained. Within this time constraint, Monte-Carlo still outputs significant errors, underlying the fast computation of our approach.

JELIA Conference 2021 Conference Paper

Introducing a Tool for Concurrent Argumentation

• Stefano Bistarelli
• Carlo Taticchi

Abstract Agent-based modelling languages naturally implement concurrency for handling complex interactions between communicating agents. On the other hand, the field of Argumentation Theory lacks of instruments to explicitly model concurrent behaviours. In this paper we introduce a tool for dealing with concurrent argumentation processes and that can be used, for instance, to model agents debating, negotiating and persuading. The tool implements operations as expansion, contraction and revision. We also provide a web interface exposing the functionalities of the tool and allowing for a more careful study of concurrent processes.

FLAP Journal 2021 Journal Article

Weighted Argumentation.

• Stefano Bistarelli
• Francesco Santini

When dealing with Abstract Argumentation, having preference values on arguments/attacks clearly brings more information to a framework, which can be considered as a directed graph. One of the advantages is the possibility to define a different notion of defence, checking also if the associated preference is stronger than the preference of the considered attack. In the real-world, such values can be represented by “likes” in social-networks, or generic votes in favour of attacks. We focus on qualitative/quantitative preference values on attacks, which indicate their (relative) strength and can measure an argument-pair inconsistency degree. Once assembled, also by moving values from arguments to attacks, it is then possible to redefine semantics, relax the notion of weighted acceptability, and check well-known properties as in Dung’s frameworks, e.g., if a framework is well-founded.

JELIA Conference 2019 Conference Paper

A Possible World View and a Normal Form for the Constellation Semantics

• Stefano Bistarelli
• Theofrastos Mantadelis

Abstract After Dung’s founding work in Abstract Argumentation Frameworks there has been a growing interest in extending the Dung’s semantics in order to describe more complex or real life situations. Several of these approaches take the direction of weighted or probabilistic extensions. One of the most prominent probabilistic approaches is that of constellation Probabilistic Abstract Argumentation Frameworks. In this paper, we introduce the probabilistic attack normal form for the constellation semantics; and we prove that the probabilistic attack normal form is sufficient to represent any Probabilistic Abstract Argumentation Framework of the constellation semantics.

JELIA Conference 2019 Conference Paper

Well-Foundedness in Weighted Argumentation Frameworks

• Stefano Bistarelli
• Francesco Santini 0001

Abstract We revise classical properties of Abstract Argumentation Frameworks in presence of weights on attacks. We focus on the notion of well-foundedness originally provided by P. M. Dung in his pioneering work. We generalise it by considering sequences of Set-maximal Attack sets, instead of a plain sequence of arguments: such sets include all the arguments attacking a previous set in the sequence. By using a parametric framework based on an algebraic structure, we are able to study different proposals of weighted defence in the literature, and consequently relate their well-foundedness. We generalise such a property to any weighted defence, but also to original Dung’s defence. Finally, we provide conditions for the uniqueness of the preferred and existence of the stable extensions.

KR Conference 2018 Short Paper

On Well-foundedness and Other Properties in (Weighted) Abstract Argumentation Frameworks

• Stefano Bistarelli
• Francesco Santini

LPAR Conference 2017 Conference Paper

A Quantitative Partial Model-Checking Function and Its Optimisation

• Stefano Bistarelli
• Fabio Martinelli
• Ilaria Matteucci
• Francesco Santini 0001

Partial Model-Checking (PMC) is an efficient tool to reduce the combinatorial explosion of a state-space, arising in the verification of loosely-coupled software systems. At the same time, it is useful to consider quantitative temporal-modalities. This allows for checking whether satisfying such a desired modality is too costly, by comparing the final score consisting of how much the system spends to satisfy the policy, to a given threshold. We stir these two ingredients together in order to provide a Quantitative PMC function (QPMC), based on the algebraic structure of semirings. We design a method to extract part of the weight during QPMC, with the purpose to avoid the evaluation of a modality as soon as the threshold is crossed. Moreover, we extend classical heuristics to be quantitative, and we investigate the complexity of QPMC. Keyword: Partial Model Checking, Semirings, Optimisation, Quantitative Modal Logic Quantitative Process Algebra, Quantitative Evaluation of Systems.

JELIA Conference 2016 Conference Paper

A Relaxation of Internal Conflict and Defence in Weighted Argumentation Frameworks

• Stefano Bistarelli
• Fabio Rossi
• Francesco Santini 0001

Abstract In Weighted Abstract Argumentation Frameworks (WAAFs), weights on attacks bring more information. An advantage is the possibility to define a different notion of defence, which also checks if the weight associated with defence is compared with the weight of attacks. We study and merge together two different relaxations of classically crisp-concepts in WAAFs: one is related to a new notion of weighted defence (defence can be stronger or weaker at will), while the second one is related to how much inconsistency one is willing to tolerate inside an extension (which can be not totally conflict-free now). These two relaxations are strictly related and influence each other: allowing a small conflict may lead to have more arguments in an extension, and consequently result in a stronger or weaker defence. We model weights with a semiring structure, which can be instantiated to different metrics used in the literature ( e. g. , fuzzy WAAFs).

TCS Journal 2016 Journal Article

Theoretical Computer Science in Italy

• Stefano Bistarelli
• Andrea Formisano

ECAI Conference 2014 Conference Paper

A First Comparison of Abstract Argumentation Reasoning-Tools

• Stefano Bistarelli
• Fabio Rossi
• Francesco Santini 0001

We compare three different implementations of reasoning tools dedicated to Abstract Argumentation Frameworks. These systems are ASPARTIX, ConArg2, and Dung-O-Matic. They have been tested over three different random graph-models, corresponding to the Erdos-Renyi model, Kleinberg small-world model, and scale-free Barabasi model.

ECAI Conference 2010 Conference Paper

A Common Computational Framework for Semiring-based Argumentation Systems

• Stefano Bistarelli
• Francesco Santini 0001

We suggest semirings as a mean to parametrically represent “weighted” Argumentation frameworks (AF): different kinds of preference levels related to arguments, e. g. a score representing a “fuzziness”, a “cost” or a probability level of each argument, can be represented by choosing different semirings. The novel idea is to provide a common computational and quantitative framework where attacks (and/or supports) have an associated weight and, consequently, also the computation of the classical Dung's semantics has an associated weight representing how much inconsistency we tolerate in the solution. The proposed semiring-based AF is then casted into a Soft Constraint Satisfaction Problem. Adding suitable sets of constraints permits to characterize the solution of the soft CSP as the desired Dung semantics. This allows for the application of the several solution techniques developed for Soft CSPs to AFs.

ECAI Conference 2006 Conference Paper

Bipolar Preference Problems

• Stefano Bistarelli
• Maria Silvia Pini
• Francesca Rossi 0001
• Kristen Brent Venable

ECAI Conference 2006 Conference Paper

Enhancing Constraints Manipulation in Semiring-Based Formalisms

• Stefano Bistarelli
• Fabio Gadducci

Many “semiring-like” structures are used in Soft Constraint Satisfaction Problems (SCSPs). We review a few properties of semirings that are useful for dealing with soft constraints, highlighting the differences between alternative proposals in the literature. We then extend the semiring structure by adding the notion of division as a weak inverse operation of product. In particular, division is needed to apply constraint relaxation when the product operation of the semiring is not idempotent. The division operator is introduced via residuation and it is also able to deal with partial orders, generalizing the approach given for Valued CSPs.

IJCAI Conference 2003 Conference Paper

Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search

• Stefano Bistarelli
• Philippe Codognet
• H K C Hui
• J. H. M. Lee

We provide a reformulation of the constraint hierarchies (CHs) framework based on the notion of error indicators. Adapting the generalized view of local consistency in semiring-based constraint satisfaction problems (SCSPs), we define constraint hierarchy k-consistency (CH-k-C) and give a CH- 2-C enforcement algorithm. We demonstrate how the CH-2-C algorithm can be seamlessly integrated into the ordinary branch-and-bound algorithm to make it a finite domain CH solver. Experimentation confirms the efficiency and robustness of our proposed solver prototype. Unlike other finite domain CH solvers, our proposed method works for both local and global comparators. In addition, our solver can support arbitrary error functions.

AIJ Journal 2002 Journal Article

Abstracting soft constraints: Framework, properties, examples

• Stefano Bistarelli
• Philippe Codognet
• Francesca Rossi

Soft constraints are very flexible and expressive. However, they are also very complex to handle. For this reason, it may be reasonable in several cases to pass to an abstract version of a given soft constraint problem, and then to bring some useful information from the abstract problem to the concrete one. This will hopefully make the search for a solution, or for an optimal solution, of the concrete problem, faster. In this paper we propose an abstraction scheme for soft constraint problems and we study its main properties. We show that processing the abstracted version of a soft constraint problem can help us in finding good approximations of the optimal solutions, or also in obtaining information that can make the subsequent search for the best solution easier. We also show how the abstraction scheme can be used to devise new hybrid algorithms for solving soft constraint problems, and also to import constraint propagation algorithms from the abstract scenario to the concrete one. This may be useful when we don't have any (or any efficient) propagation algorithm in the concrete setting.

IJCAI Conference 1997 Conference Paper

Semiring-based Constraint Logic Programming

• Stefano Bistarelli
• Ugo Montanari
• Francesca Rossi

We extend the Constraint Logic Programming (CLP) formalism in order to handle semiringbased constraint systems. This allows us to perform in the same language both constraint solving and optimization. In fact, constraint systems based on semirings are able to model both classical constraint solving and more sophisticated features like uncertainty, probability, fuzzyness, and optimization. We then provide this class of languages with three equivalent semantics: model-theoretic, fixpoint, and proof-theoretic, in the style of CLP programs.

IJCAI Conference 1995 Conference Paper

Constraint Solving over Semirings

• Stefano Bistarelli
• Ugo Montanari
• Francesca Rossi

We introduce a general framework for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a semiring structure, where the set of the semiring specifies the values to be associated to each tuple of values of the variable domain, and the two semiring operations (+ and x) model constraint projection and combination respectively. Local consistency algorithms, as usually used for classical CSPs, can be exploited in this general framework as well, provided that some conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving schemes, thus allowing one both to formally justify many informally taken choices in existing schemes, and to prove that the local consistency techniques can be used also in newly defined schemes.