@article{
	11391_1420339,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {A novel weighted defence and its relaxation in abstract argumentation},
	year = {2018},
	journal = {INTERNATIONAL JOURNAL OF APPROXIMATE REASONING},
	volume = {92},
	abstract = {When dealing with Weighted Abstract Argumentation, having weights on attacks clearly brings more information. The advantage, for instance, is the possibility to define a different notion of defence, checking also if the weight associated with it is stronger than the attack weight. In this work we study two different relaxations, one related to the new weighted defence we propose, by checking the difference between the composition of inward and outward attack-weights. The second one is related to how much inconsistency we are willing to tolerate inside an extension; such amount is computed by aggregating the costs of the attacks between any two arguments both inside an extension. These two relaxations are strictly linked: allowing a small conflict may lead to have more arguments into an extension, and consequently result in a stronger or weaker defence. Weights are represented by a semiring structure, which can be instantiated to different metrics used in the literature (e.g., costs, probabilities, fuzzy levels).},
	keywords = {Abstract Argumentation Frameworks; Inconsistency tolerance; Relaxation; Semirings; Weighted attacks; Software; Theoretical Computer Science; Artificial Intelligence; Applied Mathematics},
	doi = {10.1016/j.ijar.2017.10.006},	
	pages = {66--86}
}

When dealing with Weighted Abstract Argumentation, having weights on attacks clearly brings more information. The advantage, for instance, is the possibility to define a different notion of defence, checking also if the weight associated with it is stronger than the attack weight. In this work we study two different relaxations, one related to the new weighted defence we propose, by checking the difference between the composition of inward and outward attack-weights. The second one is related to how much inconsistency we are willing to tolerate inside an extension; such amount is computed by aggregating the costs of the attacks between any two arguments both inside an extension. These two relaxations are strictly linked: allowing a small conflict may lead to have more arguments into an extension, and consequently result in a stronger or weaker defence. Weights are represented by a semiring structure, which can be instantiated to different metrics used in the literature (e.g., costs, probabilities, fuzzy levels).

@inbook{
	11391_1417228,
	author = {Bistarelli, Stefano and Ceberio, Martine and Henderson, Joel A. and Santini, Francesco},
	title = {Abstract argumentation frameworks to promote fairness and rationality in multi-experts multi-criteria decision making},
	year = {2018},
	publisher = {Springer International Publishing},
	volume = {100},
	booktitle = {Studies in Systems, Decision and Control},
	abstract = {In this work, we propose to model Multi-Experts Multi-CriteriaDecision-Making (MEMCDM) problems using Abstract Argumentation Frameworks. We specifically design our model so as to ensure fairness and rationality in the decision-making process. For instance, when, of two expert’s decisions, one is unfair, we impose an attack between these two decisions, forcing one of the two decisions out of the argumentation network’s resulting extensions. Similarly, we specifically put irrational decisions in opposition to force one out. In doing so, we aim to enable the prediction of decisions that are themselves fair and rational. Our model is illustrated on a toy example.},
	keywords = {Computer Science (miscellaneous); Decision Sciences (miscellaneous); 2001; Automotive Engineering; Control and Systems Engineering; Control and Optimization; Social Sciences (miscellaneous)},
	url = {www.springer.com/series/13304},
	doi = {10.1007/978-3-319-61753-4_2},	
	pages = {7--19}
}

In this work, we propose to model Multi-Experts Multi-CriteriaDecision-Making (MEMCDM) problems using Abstract Argumentation Frameworks. We specifically design our model so as to ensure fairness and rationality in the decision-making process. For instance, when, of two expert’s decisions, one is unfair, we impose an attack between these two decisions, forcing one of the two decisions out of the argumentation network’s resulting extensions. Similarly, we specifically put irrational decisions in opposition to force one out. In doing so, we aim to enable the prediction of decisions that are themselves fair and rational. Our model is illustrated on a toy example.

@conference{
	11391_1427783,
	author = {Bistarelli, Stefano and Parroccini, Matteo and Santini, Francesco},
	title = {Visualising bitcoin flows of ransomware: WannaCry one week later},
	year = {2018},
	publisher = {CEUR-WS},
	volume = {2058},
	booktitle = {CEUR Workshop Proceedings},
	abstract = {Because of its pseudo-anonimity and decentralisation characteristics, bitcoin payments are often a tool utilised by ransomware: this kind of malware infects a victim computer by encrypting some/all its data and/or denying the access to it. Then, the victim has to pay a given amount of bitcoins to see all the blocked functionalities restored. The goal of this paper is to visualise these bitcoin transactions, and in particular we focus on the effects of one of such ransomware, i.e., WannaCry, one/two weeks after its diffusion. We exploit Block Chain Vis, a tool for visualising flows of bitcoins through the use of Visual Analytics.},
	keywords = {Computer Science (all)},
	url = {http://ceur-ws.org/Vol-2058/}
}

Because of its pseudo-anonimity and decentralisation characteristics, bitcoin payments are often a tool utilised by ransomware: this kind of malware infects a victim computer by encrypting some/all its data and/or denying the access to it. Then, the victim has to pay a given amount of bitcoins to see all the blocked functionalities restored. The goal of this paper is to visualise these bitcoin transactions, and in particular we focus on the effects of one of such ransomware, i.e., WannaCry, one/two weeks after its diffusion. We exploit Block Chain Vis, a tool for visualising flows of bitcoins through the use of Visual Analytics.

@inbook{
	11391_1420696,
	author = {Garbayo, Luciana and Ceberio, Martine and Bistarelli, Stefano and Henderson, Joel},
	title = {On modeling multi-experts multi-criteria decision-making argumentation and disagreement: Philosophical and computational approaches reconsidered},
	year = {2018},
	publisher = {Springer International Publishing},
	volume = {100},
	booktitle = {Studies in Systems, Decision and Control},
	abstract = {In this article we suggest that the research area of epistemology of disagreement should be critically applied to the problem of describing multi-experts multi-criteria decision-making (ME-MCDM), while providing an epistemic conceptualization of experts as epistemic peers. We explore some preliminary outcomes of using Dung’s computational framework for argumentation in ME-MCDM with conceptual considerations on the role of formal constraints and rationality approaches for epistemic peer disagreement, such as provided by David Christensen [2], inclusive of epistemic and pragmatic rationality, synchronic and diachronic rationality, and global and local aspects thereof},
	url = {www.springer.com/series/13304},
	doi = {10.1007/978-3-319-61753-4_10},	
	pages = {67--75}
}

In this article we suggest that the research area of epistemology of disagreement should be critically applied to the problem of describing multi-experts multi-criteria decision-making (ME-MCDM), while providing an epistemic conceptualization of experts as epistemic peers. We explore some preliminary outcomes of using Dung’s computational framework for argumentation in ME-MCDM with conceptual considerations on the role of formal constraints and rationality approaches for epistemic peer disagreement, such as provided by David Christensen [2], inclusive of epistemic and pragmatic rationality, synchronic and diachronic rationality, and global and local aspects thereof

@article{
	11391_1425840,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {Not only size, but also shape counts: Argumentation solvers are benchmark-sensitive},
	year = {2018},
	journal = {JOURNAL OF LOGIC AND COMPUTATION},
	volume = {28},
	abstract = {We test different solvers dedicated to the solution of classical problems in Argumentation, as enumeration/existence of extensions, and sceptical/credulous acceptance of arguments. We handle a subset of the solvers tested in ICCMA15, and a superset of graphs used in the same competition. The goal is to provide considerations that can help future comparisons and competitions as ICCMA15. We offer a detailed report of this comparison from the point of view of different graphs, solvers, problems and timeouts. We show that the characteristics of graphs impact on the performance of solvers and on their final ranking. In addition, we extract other general considerations, e.g., reducing the computation timeout does not change the same ranking.},
	keywords = {argumentation; benchmark; graph models; reasoning tools; Theoretical Computer Science; Software; Arts and Humanities (miscellaneous); Hardware and Architecture; Logic},
	url = {http://logcom.oxfordjournals.org/},
	doi = {10.1093/logcom/exx031},	
	pages = {85--117}
}

We test different solvers dedicated to the solution of classical problems in Argumentation, as enumeration/existence of extensions, and sceptical/credulous acceptance of arguments. We handle a subset of the solvers tested in ICCMA15, and a superset of graphs used in the same competition. The goal is to provide considerations that can help future comparisons and competitions as ICCMA15. We offer a detailed report of this comparison from the point of view of different graphs, solvers, problems and timeouts. We show that the characteristics of graphs impact on the performance of solvers and on their final ranking. In addition, we extract other general considerations, e.g., reducing the computation timeout does not change the same ranking.

@article{
	11391_1357705,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {On merging two trust-networks in one with bipolar preferences},
	year = {2017},
	journal = {MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE},
	volume = {27},
	abstract = {In this paper, we study weighted trust-networks (but also unweighted), where each edge is associated with either a positive or a negative score. Hence, we consider a distrust relationship as well, allowing a user to rate poor experiences with other individuals in his web of acquaintances. We propose an algorithm to compose two of such networks in a single one, in order to merge the knowledge obtained in two different communities of individuals (possibly partially-overlapping), through two different trust management-systems. Our algorithm is based on semiring algebraic-structures, in order to have a parametric computational-framework. Such composition can be adopted whenever two trust-based communities (with the same scope) need to be amalgamated: for instance, two competitor-companies that need to unify the trust-based knowledge on their (sub-) suppliers.},
	doi = {10.1017/S0960129515000092},	
	pages = {215--233}
}

In this paper, we study weighted trust-networks (but also unweighted), where each edge is associated with either a positive or a negative score. Hence, we consider a distrust relationship as well, allowing a user to rate poor experiences with other individuals in his web of acquaintances. We propose an algorithm to compose two of such networks in a single one, in order to merge the knowledge obtained in two different communities of individuals (possibly partially-overlapping), through two different trust management-systems. Our algorithm is based on semiring algebraic-structures, in order to have a parametric computational-framework. Such composition can be adopted whenever two trust-based communities (with the same scope) need to be amalgamated: for instance, two competitor-companies that need to unify the trust-based knowledge on their (sub-) suppliers.

@article{
	11391_1398932,
	author = {Benedetti, Irene and Bistarelli, Stefano},
	title = {From Argumentation Frameworks to Voting Systems and Back},
	year = {2017},
	journal = {FUNDAMENTA INFORMATICAE},
	volume = {150},
	abstract = {Formal voting theories are established and can be used to determine if a voting system is fair or not in order to preserve democracy. There are a lot of voting systems described in the literature, with several properties, useful in many contexts. The Argumentation Framework is based on the exchange and the evaluation of interacting arguments which may represent information of various kinds. We show that Argumentation Frameworks can be interpreted within a voting theory and considered as voting methods. Using a mapping that associates an argument to a candidate and attacks to votes, we define a bidirectional mapping between the two theories and investigate how fairness criteria defined for voting systems can be re-interpreted within Argumentation Framework. We also show how voting ballots can be seen as suitable semantics for Argumentation Frameworks.},
	doi = {10.3233/FI-2017-1459},	
	pages = {25--48}
}

Formal voting theories are established and can be used to determine if a voting system is fair or not in order to preserve democracy. There are a lot of voting systems described in the literature, with several properties, useful in many contexts. The Argumentation Framework is based on the exchange and the evaluation of interacting arguments which may represent information of various kinds. We show that Argumentation Frameworks can be interpreted within a voting theory and considered as voting methods. Using a mapping that associates an argument to a candidate and attacks to votes, we define a bidirectional mapping between the two theories and investigate how fairness criteria defined for voting systems can be re-interpreted within Argumentation Framework. We also show how voting ballots can be seen as suitable semantics for Argumentation Frameworks.

@conference{
	11391_1417230,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {A hasse diagram for weighted sceptical semantics with a unique-status grounded semantics},
	year = {2017},
	publisher = {Springer Verlag},
	volume = {10377},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	abstract = {We provide an initial study on the Hasse diagram that represents the partial order -w.r.t. set inclusion- among weighted sceptical semantics in Argumentation: grounded, ideal, and eager. Being our framework based on a parametric structure of weights, we can directly compare weighted and classical approaches. We define a unique-status weighted grounded semantics, and we prove that the lattice of stronglyadmissible extensions becomes a semi-lattice.},
	keywords = {Theoretical Computer Science; Computer Science (all)},
	url = {http://springerlink.com/content/0302-9743/copyright/2005/},
	doi = {10.1007/978-3-319-61660-5_6},	
	pages = {49--56}
}

We provide an initial study on the Hasse diagram that represents the partial order -w.r.t. set inclusion- among weighted sceptical semantics in Argumentation: grounded, ideal, and eager. Being our framework based on a parametric structure of weights, we can directly compare weighted and classical approaches. We define a unique-status weighted grounded semantics, and we prove that the lattice of stronglyadmissible extensions becomes a semi-lattice.

@conference{
	11391_1419867,
	author = {Bistarelli, Stefano and Di Noia, Tommaso and Mongiello, Marina and Nocera, Francesco},
	title = {PrOnto: An Ontology Driven Business Process Mining Tool},
	year = {2017},
	publisher = {Elsevier B.V.},
	journal = {PROCEDIA COMPUTER SCIENCE},
	volume = {112},
	booktitle = {Knowledge-Based and Intelligent Information & Engineering Systems: Proceedings of the 21st International Conference, KES-20176-8 September 2017, Marseille, France},
	keywords = {activity diagram; business process mining; ontology; Computer Science (all)},
	url = {http://www.sciencedirect.com/science/journal/18770509},
	doi = {10.1016/j.procs.2017.08.002},	
	pages = {306--315}
}

@conference{
	11391_1409310,
	author = {Bistarelli, Stefano and Martinelli, Fabio and Matteucci, Ilaria and Santini, Francesco},
	title = {A formal and run-time framework for the adaptation of local behaviours to match a global property},
	year = {2017},
	publisher = {Springer Verlag},
	volume = {10231},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	abstract = {We address the problem of automatically identifying what local properties the agents of a Cyber Physical System have to satisfy to guarantee a global required property φ. To enrich the picture, we consider properties where, besides qualitative requirements on the actions to be performed, we assume a weight associated with them: quantitative properties are specified through a weighted modal-logic. We propose both a formal machinery based on a Quantitative Partial Model Checking function on contexts, and a run-time machinery that algorithmically tries to check if the local behaviours proposed by the agents satisfy φ. The proposed approach can be seen as a run-time decomposition, privacysensitive in the sense agents do not have to disclose their full behaviour.},
	keywords = {Computer software; Embedded systems; Machinery; Model checking, Local property; Modal logic; Partial model checking; Runtimes},
	url = {http://springerlink.com/content/0302-9743/copyright/2005/},
	doi = {10.1007/978-3-319-57666-4_9},	
	pages = {134--152}
}

We address the problem of automatically identifying what local properties the agents of a Cyber Physical System have to satisfy to guarantee a global required property φ. To enrich the picture, we consider properties where, besides qualitative requirements on the actions to be performed, we assume a weight associated with them: quantitative properties are specified through a weighted modal-logic. We propose both a formal machinery based on a Quantitative Partial Model Checking function on contexts, and a run-time machinery that algorithmically tries to check if the local behaviours proposed by the agents satisfy φ. The proposed approach can be seen as a run-time decomposition, privacysensitive in the sense agents do not have to disclose their full behaviour.

@conference{
	11391_1417229,
	author = {Bistarelli, Stefano and Mantilacci, Marco and Santancini, Paolo and Santini, Francesco},
	title = {An end-to-end voting-system based on Bitcoin},
	year = {2017},
	publisher = {Association for Computing Machinery},
	volume = {128005},
	booktitle = {Proceedings of the ACM Symposium on Applied Computing},
	abstract = {In this work we re-adapt the Bitcoin e-payment system and propose it as a decentralised end-to-end voting platform (from voters to candidates). We describe the main architectural choices behind the implementation, which consists of the pre-voting, voting, and post-voting phases. The resulting implementation is completely decentralised: it is possible to directly cast a vote in the block-chain without any collecting intermediate-level. All the votes can be verified by anyone reading such a public ledger. We also exploit digital asset coins to directly keep track of votes (through the Open Asset Protocol), and we show the election cost for n voters.},
	keywords = {Bitcoin; Electronic voting; Verifiable voting-system; Software},
	doi = {10.1145/3019612.3019841},	
	pages = {1836--1841}
}

In this work we re-adapt the Bitcoin e-payment system and propose it as a decentralised end-to-end voting platform (from voters to candidates). We describe the main architectural choices behind the implementation, which consists of the pre-voting, voting, and post-voting phases. The resulting implementation is completely decentralised: it is possible to directly cast a vote in the block-chain without any collecting intermediate-level. All the votes can be verified by anyone reading such a public ledger. We also exploit digital asset coins to directly keep track of votes (through the Open Asset Protocol), and we show the election cost for n voters.

@conference{
	11391_1420338,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Go with the -bitcoin- flow, with visual analytics},
	year = {2017},
	publisher = {Association for Computing Machinery},
	volume = {130521},
	booktitle = {ACM International Conference Proceeding Series},
	abstract = {Bitcoin is a cryptocurrency and a peer-to-peer payment system, where transactions directly take place between pseudo-anonymous users, without any centralised authority. Bitcoin pseudo-anonymity can be -also- a cover for financing crime or for money laundering, as the existence of some illegal markets on the Dark Web proves. Since the block-chain (i.e., the public ledger where transactions are registered) is an example of Big Data, a straightforward visualisation is not much informative. For this reason, we employ techniques from Visual Analytics to filter out undesired information in order to obtain a tool to visually analyse the transactions and help its analysis.},
	keywords = {Analysis tool; Bitcoin; Visual analytics; Human-Computer Interaction; Computer Networks and Communications; 1707; Software},
	url = {http://portal.acm.org/},
	doi = {10.1145/3098954.3098972},	
	pages = {1--6}
}

Bitcoin is a cryptocurrency and a peer-to-peer payment system, where transactions directly take place between pseudo-anonymous users, without any centralised authority. Bitcoin pseudo-anonymity can be -also- a cover for financing crime or for money laundering, as the existence of some illegal markets on the Dark Web proves. Since the block-chain (i.e., the public ledger where transactions are registered) is an example of Big Data, a straightforward visualisation is not much informative. For this reason, we employ techniques from Visual Analytics to filter out undesired information in order to obtain a tool to visually analyse the transactions and help its analysis.

@inbook{
	11391_1423107,
	author = {Bistarelli, Stefano and Giacomin, Massimiliano and Pazienza, Andrea},
	title = {Preface of the 1st Workshop on Advances In Argumentation In Artificial Intelligence, AI^3 2017},
	year = {2017},
	publisher = {CEUR-WS},
	volume = {2012},
	booktitle = {CEUR Workshop Proceedings},
	keywords = {Argumentation, computer science},
	url = {http://ceur-ws.org/}
}

@conference{
	11391_1431560,
	author = {Bistarelli, Stefano and Giuliodori, Paolo and Mugnai, Dimitri},
	title = {A community payment scheme for consciousness energy usage},
	year = {2017},
	publisher = {Institute of Electrical and Electronics Engineers Inc.},
	volume = {2017-},
	booktitle = {2017 AEIT International Annual Conference: Infrastructures for Energy and ICT: Opportunities for Fostering Innovation, AEIT 2017},
	keywords = {energy behaviour change; fair cost division; payment scheme; Shapley value; Energy Engineering and Power Technology; Biomedical Engineering; Renewable Energy, Sustainability and the Environment},
	doi = {10.23919/AEIT.2017.8240545},	
	pages = {1--6}
}

@misc{
	11391_1391865,
	author = {Bistarelli, Stefano and Formisano, Andrea},
	title = {Theoretical Computer Science in Italy},
	year = {2016},
	publisher = {Elsevier},
	address = {Amsterdam, Netherlands},
	journal = {THEORETICAL COMPUTER SCIENCE},
	volume = {629},
	keywords = {Theoretical Computer Science; Computer Science (all)},
	url = {http://www.journals.elsevier.com/theoretical-computer-science/},
	doi = {10.1016/j.tcs.2016.04.010},	
	pages = {1--1}
}

@conference{
	11391_1398837,
	author = {Bistarelli, Stefano and Culmone, Rosario and Giuliodori, Paolo and Mugnoz, Stefano},
	title = {A mechanism design approach for allocation of commodities},
	year = {2016},
	publisher = {CEUR-WS},
	volume = {1720},
	booktitle = {CEUR Workshop Proceedings},
	abstract = {We deploy a mechanism design approach for allocating a divisible commodity (electricity in our example) among consumers. We
consider each consumer with an associated personal valuation function of the energy resource during a certain time interval. We aim to select the
optimal consumption profile for every user avoiding consumption peaks when the total required energy could exceed the energy production. The
mechanism will be able to drive users in shifting energy consumptions in different hours of the day. We start by presenting a very basic Vickrey-
Clarke-Groves mechanism, we discuss its weakness and propose several more complex variants. This is an extended abstract, for additional details we provide a technical report},
	url = {http://ceur-ws.org/Vol-1720/short10.pdf},
	pages = {275--279}
}

We deploy a mechanism design approach for allocating a divisible commodity (electricity in our example) among consumers. We consider each consumer with an associated personal valuation function of the energy resource during a certain time interval. We aim to select the optimal consumption profile for every user avoiding consumption peaks when the total required energy could exceed the energy production. The mechanism will be able to drive users in shifting energy consumptions in different hours of the day. We start by presenting a very basic Vickrey- Clarke-Groves mechanism, we discuss its weakness and propose several more complex variants. This is an extended abstract, for additional details we provide a technical report

@misc{
	11391_1395417,
	author = {Bistarelli, Stefano and Formisano, Andrea and Maratea, Marco},
	title = {RCRA 2016
International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion},
	year = {2016},
	publisher = {CEUR-WS.org},
	volume = {1745},
	abstract = {This volume contains the papers presented at RCRA 2016, the 23rd RCRA International Workshop on “Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion” held on November 28, 2016 in Genova.},
	url = {http://ceur-ws.org/Vol-1745/},
	pages = {1--104}
}

This volume contains the papers presented at RCRA 2016, the 23rd RCRA International Workshop on “Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion” held on November 28, 2016 in Genova.

@conference{
	11391_1398691,
	author = {Bistarelli, Stefano and Santini, Francesco and Martinelli, Fabio and Matteucci, Ilaria},
	title = {Automated adaptation via Quantitative Partial Model Checking},
	year = {2016},
	publisher = {Association for Computing Machinery},
	volume = {04-08-},
	booktitle = {Proceedings of the ACM Symposium on Applied Computing},
	abstract = {We propose a formal framework to model an automated adaptation protocol based on Quantitative Partial Model Checking (QPMC). An agent seeks the collaboration of a second agent to satisfy some (fixed) condition on the actions to be executed. The provided protocol allows the two agents to automatically agree by iteratively applying QPMC.},
	keywords = {Adaptation; Partial model checking, multi-agent systems; Software},
	doi = {10.1145/2851613.2851955},	
	pages = {1993--1996}
}

We propose a formal framework to model an automated adaptation protocol based on Quantitative Partial Model Checking (QPMC). An agent seeks the collaboration of a second agent to satisfy some (fixed) condition on the actions to be executed. The provided protocol allows the two agents to automatically agree by iteratively applying QPMC.

@conference{
	11391_1398697,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {A relaxation of internal conflict and defence in weighted argumentation frameworks},
	year = {2016},
	publisher = {Springer Verlag},
	volume = {10021},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	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).},
	keywords = {Theoretical Computer Science; Computer Science (all)},
	url = {http://springerlink.com/content/0302-9743/copyright/2005/},
	doi = {10.1007/978-3-319-48758-8_9},	
	pages = {127--143}
}

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).

@conference{
	11391_1398698,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {A collective defence against grouped attacks for weighted abstract argumentation frameworks},
	year = {2016},
	publisher = {AAAI Press},
	booktitle = {Proceedings of the 29th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2016},
	abstract = {Adding weights or preferences to Abstract Argumentation Frameworks can help disentangle semantics from otherwise all-equivalent attacks. Having such information makes possible to distil the set of found extensions by reducing their number. In this work we provide a new definition of weighted defence: according to it, all the attacks from an argument to a set of arguments are considered with a single global weight, i.e., attacks are grouped together. This provides a coherent view w.r.t. defence, which is usually “collective” in the literature. Moreover, we model weighted defences from related works in the same algebraic framework: this allows us to compare all the different proposals together.},
	keywords = {Software; Artificial Intelligence; Computer Networks and Communications},
	pages = {638--643}
}

Adding weights or preferences to Abstract Argumentation Frameworks can help disentangle semantics from otherwise all-equivalent attacks. Having such information makes possible to distil the set of found extensions by reducing their number. In this work we provide a new definition of weighted defence: according to it, all the attacks from an argument to a set of arguments are considered with a single global weight, i.e., attacks are grouped together. This provides a coherent view w.r.t. defence, which is usually “collective” in the literature. Moreover, we model weighted defences from related works in the same algebraic framework: this allows us to compare all the different proposals together.

@conference{
	11391_1398838,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {ConArg: A Tool for Classical and Weighted Argumentation},
	year = {2016},
	publisher = {IOS Press},
	booktitle = {Frontiers in Artificial Intelligence and Applications},
	abstract = {ConArg is a tool for solving different problems related to extension-based semantics: e.g., enumeration of extensions, sceptical and credulous acceptance of arguments. We have extended it in order to deal with Weighted Abstract Argumentation Frameworks, where each attack is associated with a strength score. Classical notions of defence and conflict-freeness have been redefined with the purpose to have different (weighted) degrees of their relaxation. The ultimate aim is to let an agent choose between a higher internal consistency or a stronger defence.},
	doi = {10.3233/978-1-61499-686-6-463},	
	pages = {463--464}
}

ConArg is a tool for solving different problems related to extension-based semantics: e.g., enumeration of extensions, sceptical and credulous acceptance of arguments. We have extended it in order to deal with Weighted Abstract Argumentation Frameworks, where each attack is associated with a strength score. Classical notions of defence and conflict-freeness have been redefined with the purpose to have different (weighted) degrees of their relaxation. The ultimate aim is to let an agent choose between a higher internal consistency or a stronger defence.

@misc{
	11391_1399092,
	author = {Bistarelli, Stefano and Formisano, Andrea and Maratea, Marco and Torroni, Paolo},
	title = {Special issue of the 22nd RCRA international workshop on "Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion"},
	year = {2016},
	publisher = {IOS Press},
	address = {;Nieuwe Hemweg 6B},
	journal = {FUNDAMENTA INFORMATICAE},
	volume = {149},
	keywords = {Theoretical Computer Science; Algebra and Number Theory; Information Systems; Computational Theory and Mathematics},
	url = {http://www.iospress.nl/},
	doi = {10.3233/FI-2016-1440},	
	pages = {v--vii}
}

@inbook{
	11391_1431179,
	author = {Bistarelli, Stefano and Formisano, Andrea and Maratea, Marco},
	title = {Preface},
	year = {2016},
	publisher = {CEUR-WS},
	volume = {1745},
	booktitle = {CEUR Workshop Proceedings},
	keywords = {Computer Science (all)},
	url = {http://ceur-ws.org/}
}

@article{
	11391_1342078,
	author = {Bistarelli, Stefano and Gabbrielli, Maurizio and Meo, MARIA CHIARA and Santini, Francesco},
	title = {Timed soft concurrent constraint programs: An interleaved and a parallel approach},
	year = {2015},
	journal = {THEORY AND PRACTICE OF LOGIC PROGRAMMING},
	volume = {15},
	abstract = {We propose a timed and soft extension of Concurrent Constraint Programming. The time extension is based on the hypothesis of bounded asynchrony: The computation takes a bounded period of time and is measured by a discrete global clock. Action prefixing is then considered as the syntactic marker that distinguishes a time instant from the next one. Supported by soft constraints instead of crisp ones, tell and ask agents are now equipped with a preference (or consistency) threshold, which is used to determine their success or suspension. In this paper, we provide a language to describe the agents' behavior, together with its operational and denotational semantics, for which we also prove the compositionality and correctness properties. After presenting a semantics using maximal parallelism of actions, we also describe a version for their interleaving on a single processor (with maximal parallelism for time elapsing). Coordinating agents that need to take decisions on both preference values and time events may benefit from this language.},
	keywords = {interleaving, parallelism, Soft Concurrent Constraint Programming, Timed Concurrent Constraint Programming},
	doi = {10.1017/S1471068414000106},	
	pages = {1--743}
}

We propose a timed and soft extension of Concurrent Constraint Programming. The time extension is based on the hypothesis of bounded asynchrony: The computation takes a bounded period of time and is measured by a discrete global clock. Action prefixing is then considered as the syntactic marker that distinguishes a time instant from the next one. Supported by soft constraints instead of crisp ones, tell and ask agents are now equipped with a preference (or consistency) threshold, which is used to determine their success or suspension. In this paper, we provide a language to describe the agents' behavior, together with its operational and denotational semantics, for which we also prove the compositionality and correctness properties. After presenting a semantics using maximal parallelism of actions, we also describe a version for their interleaving on a single processor (with maximal parallelism for time elapsing). Coordinating agents that need to take decisions on both preference values and time events may benefit from this language.

@article{
	11391_1357699,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {A Comparative Test on the Enumeration of Extensions in Abstract Argumentation},
	year = {2015},
	journal = {FUNDAMENTA INFORMATICAE},
	volume = {140},
	abstract = {We compare four different implementations of reasoning-tools dedicated to Abstract Argumentation Frameworks. These systems are ArgTools, ASPARTIX, ConArg2, and Dung-O-Matic. They have been tested over three different models of randomly-generated graph models, corresponding to the Erdős-Rényi model, the Kleinberg small-world model, and the scale-free Barabasi-Albert model. This first comparison is useful to study the behaviour of these tools over networks with different topologies (also small-world): we scale the number of arguments to check the limits of today’s systems. Such results can be used to guide further improvements of ConArg2 (our tool), but also different tools.},
	keywords = {SEMANTICS, FRAMEWORKS},
	doi = {10.3233/FI-2015-1254},	
	pages = {263--278}
}

We compare four different implementations of reasoning-tools dedicated to Abstract Argumentation Frameworks. These systems are ArgTools, ASPARTIX, ConArg2, and Dung-O-Matic. They have been tested over three different models of randomly-generated graph models, corresponding to the Erdős-Rényi model, the Kleinberg small-world model, and the scale-free Barabasi-Albert model. This first comparison is useful to study the behaviour of these tools over networks with different topologies (also small-world): we scale the number of arguments to check the limits of today’s systems. Such results can be used to guide further improvements of ConArg2 (our tool), but also different tools.

@conference{
	11391_1357834,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco and Taticchi, Carlo},
	title = {Towards visualising security with arguments},
	year = {2015},
	publisher = {CEUR-WS.org},
	volume = {1459},
	booktitle = {CILC 2015 Italian Conference on Computational Logic},
	abstract = {Argumentation has been proved as a simple yet powerful approach to manage conicts in reasoning with the purpose to find subsets of surviving arguments. Our intent is to exploit such form of resolution to visually support the administration of security in complex systems. For instance, in case threat countermeasures are in conict (also with assets) and only some of them can be selected.},
	url = {http://ceur-ws.org/Vol-1459/paper28.pdf},
	pages = {197--201}
}

Argumentation has been proved as a simple yet powerful approach to manage conicts in reasoning with the purpose to find subsets of surviving arguments. Our intent is to exploit such form of resolution to visually support the administration of security in complex systems. For instance, in case threat countermeasures are in conict (also with assets) and only some of them can be selected.

@misc{
	11391_1357836,
	author = {Bistarelli, Stefano and Formisano, Andrea and Maratea, Marco},
	title = {RCRA 2015
Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion},
	year = {2015},
	volume = {1451},
	url = {http://ceur-ws.org/Vol-1451/proceedings.pdf},
	pages = {1--90}
}

@conference{
	11391_1357792,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {Testing Credulous and Sceptical Acceptance in Small-World Networks},
	year = {2015},
	publisher = {CEUR-WS.org},
	volume = {1451},
	booktitle = {Proceedings of the 22nd RCRA International Workshop on ExperimentalEvaluation of Algorithms for Solving Problems with Combinatorial Explosion2015 (RCRA 2015) A workshop of the XIV International Conferenceof the Italian Association for Artificial Intelligence (AI*IA 2015),Ferrara, Italy, September 22, 2015.},
	abstract = {In this paper we test how efficiently state-of-the art solvers are capable of solving credulous and sceptical argument-acceptance for lower-order extensions. As our benchmark we consider two different random graph-models to obtain random Abstract Argumentation Frameworks with small-world characteristics: Kleinberg andWatt-Strogatz.We test two reasoners, i.e., ConArg2 and dynPARTIX, on such benchmark, by comparing their performance on NP/co-NP-complete decision problems related to argument acceptance in admissible, complete, and stable semantics.},
	url = {http://ceur-ws.org/Vol-1451/paper4.pdf},
	pages = {39--46}
}

In this paper we test how efficiently state-of-the art solvers are capable of solving credulous and sceptical argument-acceptance for lower-order extensions. As our benchmark we consider two different random graph-models to obtain random Abstract Argumentation Frameworks with small-world characteristics: Kleinberg andWatt-Strogatz.We test two reasoners, i.e., ConArg2 and dynPARTIX, on such benchmark, by comparing their performance on NP/co-NP-complete decision problems related to argument acceptance in admissible, complete, and stable semantics.

@conference{
	11391_1329112,
	author = {Benedetti, Irene and Bistarelli, Stefano and Piersanti, Paolo},
	title = {On Relating Voting Systems and Argumentation Frameworks},
	year = {2014},
	publisher = {CEUR-WS},
	volume = {1195},
	booktitle = {Proceedings of the 29th Italian Conference on Computational Logic},
	abstract = {In the modern world formal voting theories are becoming established and can be used to determine if a Voting System (VS) is fair or not in order to preserve democracy. The Argumentation Framework (AF) is based on the exchange
and the evaluation of interacting arguments which may represent information of various kinds. We define a bijective mapping between the two theories and investigate how fairness criteria defined for voting systems can be re-interpreted
inside the Argumentation Frameworks.},
	pages = {309--313}
}

In the modern world formal voting theories are becoming established and can be used to determine if a Voting System (VS) is fair or not in order to preserve democracy. The Argumentation Framework (AF) is based on the exchange and the evaluation of interacting arguments which may represent information of various kinds. We define a bijective mapping between the two theories and investigate how fairness criteria defined for voting systems can be re-interpreted inside the Argumentation Frameworks.

@conference{
	11391_1345379,
	author = {Bistarelli, Stefano and Costantino, Gianpiero and Martinelli, Fabio and Santini, Francesco},
	title = {An Improved Role-Based Access to Android Applications with JCHR},
	year = {2014},
	publisher = {IEEE Computer Society},
	booktitle = {Proceedings 9th International Conference on Availability, Reliability and Security, ARES 2014},
	abstract = {In this paper we show how deductive and abductive reasoning in distributed authorisation can be efficiently ported to Android. Such logical-inference processes prove to be important tools due to the intrinsic autonomic-nature of these mobile devices. Both deduction and abduction are represented by using Constraint Handling Rules (CHR), a high-level declarative constraint programming-language, and implemented in JCHR (CHR embedded into Java). To represent credentials we elaborate on RTW, a weighted Role-based Trust-management family of languages: CHR programs are developed after such languages. In general, having weights associated with credentials leads to a more informative reasoning, for instance, access can be granted only if the total uncertainty is less than 20%.},
	doi = {10.1109/ARES.2014.52},	
	pages = {341--348}
}

In this paper we show how deductive and abductive reasoning in distributed authorisation can be efficiently ported to Android. Such logical-inference processes prove to be important tools due to the intrinsic autonomic-nature of these mobile devices. Both deduction and abduction are represented by using Constraint Handling Rules (CHR), a high-level declarative constraint programming-language, and implemented in JCHR (CHR embedded into Java). To represent credentials we elaborate on RTW, a weighted Role-based Trust-management family of languages: CHR programs are developed after such languages. In general, having weights associated with credentials leads to a more informative reasoning, for instance, access can be granted only if the total uncertainty is less than 20%.

@conference{
	11391_1345400,
	author = {Bistarelli, Stefano and Ceberio, Martine and Henderson, Joel A. and Santini, Francesco},
	title = {Abstract argumentation frameworks to promote fairness and rationality in multi-experts multi-criteria decision making},
	year = {2014},
	publisher = {CEUR-WS.org},
	volume = {1231},
	booktitle = {Proceedings of the 15th Italian Conference on Theoretical ComputerScience, ,},
	url = {http://ceur-ws.org/Vol-1231/short3.pdf},
	pages = {247--257}
}

@article{
	11391_1345351,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {A Secure Non-monotonic Soft Concurrent Constraint Language},
	year = {2014},
	journal = {FUNDAMENTA INFORMATICAE},
	volume = {134},
	abstract = {We present a fine-grained security model to enforce the access control on the shared constraint store in Concurrent Constraint Programming (CCP) languages. We show the model for a non-monotonic version of Soft CCP (SCCP), that is an extension of CCP where the constraints have a preference level associated with them. Crisp constraints can be modeled in the same framework as well. In the considered non-monotonic soft version (NmSCCP), it is also possible to remove constraints from the store. The language can be used for coordinating agents on a common store of information that represents the set of shared resources. In such scenarios, it is clearly important to enforce the integrity and confidentiality rights on the resources, in order, for instance, to hide part of the information to some agents, or to prevent an agent to consume too many resources. Finally, we present a bisimulation relation to check equivalence between two programs written in this language.},
	keywords = {ACCESS-CONTROL, COORDINATION},
	url = {http://dx.doi.org/10.3233/FI-2014-1102},
	doi = {10.3233/FI-2014-1102},	
	pages = {261--285}
}

We present a fine-grained security model to enforce the access control on the shared constraint store in Concurrent Constraint Programming (CCP) languages. We show the model for a non-monotonic version of Soft CCP (SCCP), that is an extension of CCP where the constraints have a preference level associated with them. Crisp constraints can be modeled in the same framework as well. In the considered non-monotonic soft version (NmSCCP), it is also possible to remove constraints from the store. The language can be used for coordinating agents on a common store of information that represents the set of shared resources. In such scenarios, it is clearly important to enforce the integrity and confidentiality rights on the resources, in order, for instance, to hide part of the information to some agents, or to prevent an agent to consume too many resources. Finally, we present a bisimulation relation to check equivalence between two programs written in this language.

@conference{
	11391_1345517,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {Benchmarking Hard Problems in Random Abstract AFs: The Stable Semantics},
	year = {2014},
	publisher = {IOS Press},
	volume = {266},
	booktitle = {COMPUTATIONAL MODELS OF ARGUMENT},
	abstract = {In this paper we test four different implementations of reasoning tools dedicated to Abstract Argumentation Frameworks. These systems are ASPARTIX, dynPARTIX, Dung-O-Matic, and ConArg2. The tests are executed over three different models of randomly-generated graphs, i.e., the Erds-Renyi model, the Kleinberg small-world model, and the scale-free Barabasi-Albert model. We compare these four tools with the purpose to test the search of all the possible stable extensions. Then we benchmark dynPARTIX and ConArg2 on the credulous and skeptical acceptance of arguments. Finally, we also evaluate ConArg2 to check the existence of a stable extension.},
	url = {http://dx.doi.org/10.3233/978-1-61499-436-7-153},
	doi = {10.3233/978-1-61499-436-7-153},	
	pages = {153--160}
}

In this paper we test four different implementations of reasoning tools dedicated to Abstract Argumentation Frameworks. These systems are ASPARTIX, dynPARTIX, Dung-O-Matic, and ConArg2. The tests are executed over three different models of randomly-generated graphs, i.e., the Erds-Renyi model, the Kleinberg small-world model, and the scale-free Barabasi-Albert model. We compare these four tools with the purpose to test the search of all the possible stable extensions. Then we benchmark dynPARTIX and ConArg2 on the credulous and skeptical acceptance of arguments. Finally, we also evaluate ConArg2 to check the existence of a stable extension.

@conference{
	11391_1345532,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {A First Comparison of Abstract Argumentation Reasoning-Tools},
	year = {2014},
	publisher = {{IOS} Press},
	volume = {263},
	booktitle = {{ECAI} 2014 - 21st European Conference on Artificial Intelligence,18-22 August 2014, Prague, Czech Republic - Including PrestigiousApplications of Intelligent Systems {(PAIS} 2014)},
	abstract = {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 Erdös-Rényi model, Kleinberg small-world model, and scale-free Barabasi model.},
	url = {http://dx.doi.org/10.3233/978-1-61499-419-0-969},
	doi = {10.3233/978-1-61499-419-0-969},	
	pages = {969--970}
}

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 Erdös-Rényi model, Kleinberg small-world model, and scale-free Barabasi model.

@conference{
	11391_1345535,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {Efficient Solution for Credulous/Sceptical Acceptance in Lower-Order Dung's Semantics},
	year = {2014},
	publisher = {IEEE Computer Society},
	booktitle = {26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014},
	abstract = {We provide an extensive testing on how efficiently state-of-the art solvers are capable of solving credulous and sceptical argument-acceptance for lower-order extensions. In fact, as our benchmark we consider three different random graph-models to represent random Abstract Argumentation Frameworks: Barabasi and Erdos-Renyi networks, and, in addition, we also rework balanced trees by randomise their structure, with the purpose to obtain random trees of different height. Therefore, we test two reasoners, i.e., Con Arg2 and dyn PARTIX, on such benchmark, by comparing their performance on NP/co-NP-complete decision problems related to argument acceptance in admissible, complete, and stable semantics.},
	doi = {10.1109/ICTAI.2014.123},	
	pages = {800--804}
}

We provide an extensive testing on how efficiently state-of-the art solvers are capable of solving credulous and sceptical argument-acceptance for lower-order extensions. In fact, as our benchmark we consider three different random graph-models to represent random Abstract Argumentation Frameworks: Barabasi and Erdos-Renyi networks, and, in addition, we also rework balanced trees by randomise their structure, with the purpose to obtain random trees of different height. Therefore, we test two reasoners, i.e., Con Arg2 and dyn PARTIX, on such benchmark, by comparing their performance on NP/co-NP-complete decision problems related to argument acceptance in admissible, complete, and stable semantics.

@conference{
	11391_1345538,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Two trust networks in one: Using bipolar structures to fuse trust and distrust},
	year = {2014},
	publisher = {IEEE Press},
	booktitle = {12th Annual Conference on Privacy, Security and Trust, PST 2014},
	abstract = {In this paper we study weighted trust-networks, where each edge is associated with either a positive or negative score. Hence, we consider a distrust relationship as well, allowing a user to rate poor experiences with other individuals in his web of acquaintances. We propose an algorithm to compose two of such networks in a single one, in order to merge the knowledge obtained in two different communities of individuals (possibly partially-overlapping), through two different trust management-systems. Our algorithm is based on semiring algebraic-structures, in order to have a parametric computational-framework. Such composition can be adopted whenever two trust-based communities (with the same scope) need to be amalgamated: for instance, two competitor-companies that need to unify the trust-based knowledge on their (sub-) suppliers.},
	doi = {10.1109/PST.2014.6890964},	
	pages = {383--390}
}

In this paper we study weighted trust-networks, where each edge is associated with either a positive or negative score. Hence, we consider a distrust relationship as well, allowing a user to rate poor experiences with other individuals in his web of acquaintances. We propose an algorithm to compose two of such networks in a single one, in order to merge the knowledge obtained in two different communities of individuals (possibly partially-overlapping), through two different trust management-systems. Our algorithm is based on semiring algebraic-structures, in order to have a parametric computational-framework. Such composition can be adopted whenever two trust-based communities (with the same scope) need to be amalgamated: for instance, two competitor-companies that need to unify the trust-based knowledge on their (sub-) suppliers.

@misc{
	11391_1345503,
	author = {Bistarelli, Stefano and Formisano, Andrea},
	title = {Proceedings of the 15th Italian Conference on Theoretical Computer
Science, ICTCS2014},
	year = {2014},
	publisher = {CEUR-WS.org},
	volume = {1231},
	url = {http://ceur-ws.org/Vol-1231}
}

@conference{
	11391_1345390,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {Enumerating Extensions on Random Abstract-AFs with ArgTools, Aspartix, ConArg2, and Dung-O-Matic},
	year = {2014},
	publisher = {Springer},
	volume = {8624},
	booktitle = {Proceedings 15th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA 2014},
	doi = {10.1007/978-3-319-09764-0_5},	
	pages = {70--86}
}

@inbook{
	11391_1345404,
	author = {Bistarelli, Stefano and Formisano, Andrea},
	title = {Preface},
	year = {2014},
	publisher = {CEUR-WS.org},
	volume = {1231},
	booktitle = {Proceedings of the 15th Italian Conference on Theoretical ComputerScience, Perugia, Italy, September 17-19, 2014.},
	url = {http://ceur-ws.org/Vol-1231/preface.pdf},
	pages = {i--v}
}

@conference{
	11391_1218491,
	author = {Henderson, Joel and Bistarelli, Stefano and Ceberio, Martine},
	title = {Multi-Experts Multi-Criteria Decision Making},
	year = {2013},
	publisher = {Luigi Pellegrini Editore},
	booktitle = {Proceeding of the international conference «numerical computations: theory and algorithms},
	doi = {10.978.886822/0327},	
}

@article{
	11391_1158897,
	author = {Bistarelli, S. and Faltings, B. and Neagu, N.},
	title = {Interchangeability with thresholds and degradation factors for Soft CSPs},
	year = {2013},
	journal = {ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE},
	volume = {67},
	abstract = {Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce two notions: threshold α and degradation factor δ for substitutability and interchangeability, (αsubstitutability/interchangeability and δsubstitutability/interchangeabi-lity respectively). We show that they satisfy analogous theorems to the ones already known for hard constraints. In αinterchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In δinterchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ. We give efficient algorithms to compute (δ/α)interchangeable sets of values for a large class of SCSPs, and show an example of their application. Through experimental evaluation based on random generated problem we measure first, how often neighborhood interchangeable values are occurring, second, how well they can approximate fully interchangeable ones, and third, how efficient they are when used as preprocessing techniques for branch and bound search.},
	keywords = {Constraint optimization, Constraint satisfaction, Interchangeability, Soft constraints},
	doi = {10.1007/s10472-013-9348-8},	
	pages = {123--163}
}

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce two notions: threshold α and degradation factor δ for substitutability and interchangeability, (αsubstitutability/interchangeability and δsubstitutability/interchangeabi-lity respectively). We show that they satisfy analogous theorems to the ones already known for hard constraints. In αinterchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In δinterchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ. We give efficient algorithms to compute (δ/α)interchangeable sets of values for a large class of SCSPs, and show an example of their application. Through experimental evaluation based on random generated problem we measure first, how often neighborhood interchangeable values are occurring, second, how well they can approximate fully interchangeable ones, and third, how efficient they are when used as preprocessing techniques for branch and bound search.

@misc{
	11391_1158901,
	author = {Bistarelli, Stefano and Monfroy, Eric and O'Sullivan, Barry},
	title = {Proceedings of the 2013 ACM Symposium on Applied Computing - Constraint solving and programming track},
	year = {2013}
}

@article{
	11391_1158898,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Coalitions of Arguments: An Approach with Constraint Programming},
	year = {2013},
	journal = {FUNDAMENTA INFORMATICAE},
	volume = {124},
	abstract = {The aggregation of generic items into coalitions leads to the creation of sets of homogenous entities. In this paper we accomplish this for an input set of arguments, and the result is a partition according to distinct lines of thought, i.e., groups of "coherent" ideas. We extend Dung's Argumentation Framework (AF) in order to deal with coalitions of arguments. The initial set of arguments is partitioned into not-intersected subsets. All the found coalitions show the same property inherited by Dung, e.g., all the coalitions in the partition are admissible (or conflict-free, complete, stable): they are generated according to Dung's principles. Each of these coalitions can be assigned to a different agent. We use Soft Constraint Programming as a formal approach to model and solve such partitions in weighted AFs: semiring algebraic structures can be used to model different optimization criteria for the obtained coalitions. Moreover, we implement and solve the presented problem with JaCoP, a Java constraint solver, and we test the code over a small-world network.},
	keywords = {SMALL-WORLD, FRAMEWORK, NETWORKS, SYSTEMS},
	doi = {10.3233/FI-2013-840},	
	pages = {383--401}
}

The aggregation of generic items into coalitions leads to the creation of sets of homogenous entities. In this paper we accomplish this for an input set of arguments, and the result is a partition according to distinct lines of thought, i.e., groups of "coherent" ideas. We extend Dung's Argumentation Framework (AF) in order to deal with coalitions of arguments. The initial set of arguments is partitioned into not-intersected subsets. All the found coalitions show the same property inherited by Dung, e.g., all the coalitions in the partition are admissible (or conflict-free, complete, stable): they are generated according to Dung's principles. Each of these coalitions can be assigned to a different agent. We use Soft Constraint Programming as a formal approach to model and solve such partitions in weighted AFs: semiring algebraic structures can be used to model different optimization criteria for the obtained coalitions. Moreover, we implement and solve the presented problem with JaCoP, a Java constraint solver, and we test the code over a small-world network.

@conference{
	11391_1158906,
	author = {Bistarelli, Stefano and Rossi, Fabio and Santini, Francesco},
	title = {A First Comparison of Abstract Argumentation Systems: A Computational Perspective},
	year = {2013},
	publisher = {CEUR},
	journal = {CEUR WORKSHOP PROCEEDINGS},
	volume = {1068},
	booktitle = {Proceedings of the 28th Italian Conference on Computational Logic},
	pages = {241--245}
}

@conference{
	11391_1158903,
	author = {Bistarelli, Stefano and Gosti, Giorgio and Santini, Francesco},
	title = {Solving Fuzzy Distributed CSPs: An Approach with Naming Games},
	year = {2013},
	publisher = {Springer-Verlag},
	volume = {7784},
	booktitle = {Declarative Agent Languages and Technologies X - 10th International Workshop, DALT 2012},
	abstract = {Constraint Satisfaction Problems (CSPs) are the formalization of a large range of problems that emerge from computer science. The solving methodology described here is based on Naming Games (NGs). NGs were introduced to represent N agents that have to bootstrap an agreement on a name to give to an object (i.e., a word). In this paper we focus on solving both Fuzzy NGs and Fuzzy Distributed CSPs (Fuzzy DCSPs) with an algorithm inspired by NGs. In this framework, each proposed solution is associated with a preference represented as a fuzzy score. We want the agents to find the solution, which is associated with the highest preference value among all solutions. The two main features that distinguish this methodology from classical Fuzzy DCSPs algorithms are that i) the system can react to small instance changes, and ii) the fact the algorithm does not require a pre-agreed agent/variable ordering.},
	doi = {10.1007/978-3-642-37890-4_7},	
	pages = {116--135}
}

Constraint Satisfaction Problems (CSPs) are the formalization of a large range of problems that emerge from computer science. The solving methodology described here is based on Naming Games (NGs). NGs were introduced to represent N agents that have to bootstrap an agreement on a name to give to an object (i.e., a word). In this paper we focus on solving both Fuzzy NGs and Fuzzy Distributed CSPs (Fuzzy DCSPs) with an algorithm inspired by NGs. In this framework, each proposed solution is associated with a preference represented as a fuzzy score. We want the agents to find the solution, which is associated with the highest preference value among all solutions. The two main features that distinguish this methodology from classical Fuzzy DCSPs algorithms are that i) the system can react to small instance changes, and ii) the fact the algorithm does not require a pre-agreed agent/variable ordering.

@article{
	11391_1002065,
	author = {Bistarelli, Stefano and Martinelli, Fabio and Santini, Francesco},
	title = {A semiring-based framework for the deduction/abduction reasoning in access control with weighted credentials},
	year = {2012},
	journal = {COMPUTERS & MATHEMATICS WITH APPLICATIONS},
	volume = {64},
	abstract = {We present a variant of the Datalog language (we call it Datalog W), which is able to deal with weights on ground facts. The weights are chosen from a semiring algebraic structure. Our goal is to use this language as a semantic foundation for trust-management languages, in order to express trust relationships associated with a preference (e.g., a cost, an uncertainty, a trust or a fuzzy value). We apply Datalog W as the basis to give a uniform semantics to a weighted extension of the RT language family, called RT W. Moreover, we show that we can model the deduction and abduction reasoning with semiring-based soft constraints: deduction can validate or not the access request, while abduction can be used to compute the missing credentials if the access is denied and the level of preference that would grant the access.},
	keywords = {Abduction, Deduction, Role-based Trust-management languages, Soft constraint},
	doi = {10.1016/j.camwa.2011.12.017},	
	pages = {447--462}
}

We present a variant of the Datalog language (we call it Datalog W), which is able to deal with weights on ground facts. The weights are chosen from a semiring algebraic structure. Our goal is to use this language as a semantic foundation for trust-management languages, in order to express trust relationships associated with a preference (e.g., a cost, an uncertainty, a trust or a fuzzy value). We apply Datalog W as the basis to give a uniform semantics to a weighted extension of the RT language family, called RT W. Moreover, we show that we can model the deduction and abduction reasoning with semiring-based soft constraints: deduction can validate or not the access request, while abduction can be used to compute the missing credentials if the access is denied and the level of preference that would grant the access.

@article{
	11391_309893,
	author = {Bistarelli, Stefano and Gadducci, F. and Larrosa, J. and Rollon, E. and Santini, Francesco},
	title = {Local Arc Consistency for Non-Invertible Semirings, with an Application to Multi-Objective Optimization},
	year = {2012},
	journal = {EXPERT SYSTEMS WITH APPLICATIONS},
	volume = {39},
	abstract = {We extend algorithms for local arc consistency proposed in the literature in order to deal with (absorptive) semirings that may not be invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings, such as those obtained from the Cartesian product of two (or more) semirings. One important instance of this class of semirings is adopted for multi-objective CSPs. First, we show how a semiring can be transformed into a novel one where the + operator is instantiated with the least common divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can "safely move" from the binary constraint to the unary one in the arc consistency algorithm. We then propose a local arc consistency algorithm which takes advantage of this LCD operator.},
	keywords = {CONSTRAINT SATISFACTION, SOFT CONSTRAINTS, Invertible semiring, Multi-objective, Arc consistency},
	doi = {10.1016/j.eswa.2011.06.062},	
	pages = {1708--1717}
}

We extend algorithms for local arc consistency proposed in the literature in order to deal with (absorptive) semirings that may not be invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings, such as those obtained from the Cartesian product of two (or more) semirings. One important instance of this class of semirings is adopted for multi-objective CSPs. First, we show how a semiring can be transformed into a novel one where the + operator is instantiated with the least common divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can "safely move" from the binary constraint to the unary one in the arc consistency algorithm. We then propose a local arc consistency algorithm which takes advantage of this LCD operator.

@article{
	11391_176498,
	author = {Bistarelli, S. and Fabio, Fioravanti and Pamela, Peretti and Francesco, Santini},
	title = {Evaluation of complex security scenarios using defense trees and economic indexes},
	year = {2012},
	journal = {JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE},
	volume = {24},
	abstract = {In this article, we present a mixed qualitative and quantitative approach for evaluation of information technology (IT) security investments. For this purpose, we model security scenarios by using defense trees, an extension of attack trees with countermeasures and we use economic quantitative indexes for computing the defender's return on security investment and the attacker's return on attack. We show how our approach can be used to evaluate economic profitability of countermeasures and their deterrent effect on attackers, thus providing decision makers with a useful tool for performing better evaluation of IT security investments during the risk management process.},
	keywords = {security scenarios, defense tree, economic indexes, ROI; ROA},
	doi = {10.1080/13623079.2011.587206},	
	pages = {161--192}
}

In this article, we present a mixed qualitative and quantitative approach for evaluation of information technology (IT) security investments. For this purpose, we model security scenarios by using defense trees, an extension of attack trees with countermeasures and we use economic quantitative indexes for computing the defender's return on security investment and the attacker's return on attack. We show how our approach can be used to evaluate economic profitability of countermeasures and their deterrent effect on attackers, thus providing decision makers with a useful tool for performing better evaluation of IT security investments during the risk management process.

@inbook{
	11391_309493,
	author = {Bistarelli, S. and Martinelli, F. and Roperti, F. and Santini, F.},
	title = {Negotiation on mobile devices using Weighted RTML Credentials},
	year = {2012},
	publisher = {Springer},
	booktitle = {INFORMATION SYSTEMS: CROSSROADS FOR ORGANIZATION, MANAGEMENT, ACCOUNTING AND ENGINEERING},
	abstract = {In this paper we describe an implementation for mobile phones of two important services in logical reasoning, that is deduction and abduction, defined over a set of weighted credentials. The main benefit comes during the process of automated access authorization based on trust: soft constraint operations can be easily adopted to measure the level of trust required for each operation. Moreover, when the level is not sufficient, abduction can be used to compute the missing credentials and the levels that grant the access. We implement a negotiation of credentials between two mobile devices in order to grant the access to the requestor peer, with the use of deduction/abduction services.},
	doi = {10.1007/978-3-7908-2789-7_47},	
	pages = {429--438}
}

In this paper we describe an implementation for mobile phones of two important services in logical reasoning, that is deduction and abduction, defined over a set of weighted credentials. The main benefit comes during the process of automated access authorization based on trust: soft constraint operations can be easily adopted to measure the level of trust required for each operation. Moreover, when the level is not sufficient, abduction can be used to compute the missing credentials and the levels that grant the access. We implement a negotiation of credentials between two mobile devices in order to grant the access to the requestor peer, with the use of deduction/abduction services.

@conference{
	11391_313897,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Modeling and Solving AFs with a Constraint-Based Tool: ConArg},
	year = {2012},
	publisher = {Springer-Verlag},
	volume = {7132},
	booktitle = {Theorie and Applications of Formal Argumentation - First International Workshop, TAFA 2011},
	abstract = {ConArg is a tool based on Constraint Programming which is able to model and solve different problems related to Argumentation Frameworks (AFs). To practically implement the tool, we have used JaCoP, a Java library which provides the user with a Finite Domain Constraint Programming paradigm. Constraint Satisfaction Problems (CSPs) offer a wide number of efficient techniques (as inference and search algorithms) that can tackle the complexity in finding all the possible Dung's conflict-free, admissible, complete and stable extensions in AFs. Moreover, we can use the tool to solve some of the preference-based problems presented in literature. ConArg is able to randomly generate networks with small-world properties in order to find Dung's extensions on such interaction graphs. We present the main features of ConArg and we report the performance in time.},
	doi = {10.1007/978-3-642-29184-5_7},	
	pages = {99--116}
}

ConArg is a tool based on Constraint Programming which is able to model and solve different problems related to Argumentation Frameworks (AFs). To practically implement the tool, we have used JaCoP, a Java library which provides the user with a Finite Domain Constraint Programming paradigm. Constraint Satisfaction Problems (CSPs) offer a wide number of efficient techniques (as inference and search algorithms) that can tackle the complexity in finding all the possible Dung's conflict-free, admissible, complete and stable extensions in AFs. Moreover, we can use the tool to solve some of the preference-based problems presented in literature. ConArg is able to randomly generate networks with small-world properties in order to find Dung's extensions on such interaction graphs. We present the main features of ConArg and we report the performance in time.

@misc{
	11391_310293,
	author = {Bistarelli, S. and Monfroi, E. and O'Sullivan, B.},
	title = {Proceedings of the 2012 ACM Symposium on Applied Computing - Constraint solving and programming track},
	year = {2012},
	publisher = {ACM}
}

@conference{
	11391_313896,
	author = {Bistarelli, S. and Paola, Campli and Santini, F.},
	title = {A Secure Coordination of Agents with Nonmonotonic Soft Concurrent Constraint Programming},
	year = {2012},
	publisher = {ACM Special Interest Group on Applied Computing (SIGAPP),Provincia Autonoma di Trento,Riva del Garda Congressi,COSBI},
	booktitle = {Proceedings of the ACM Symposium on Applied Computing, SAC 2012},
	abstract = {We present a fine-grained security model to enforce the access control on the constraint store in Concurrent Constraint Programming (CCP) languages. We show the model for a nonmonotonic version of Soft CCP (SCCP), that is an extension of CCP which deals with soft constraints, which are constraints that have a preference level associated to them. In the considered nomonotonic version (NMSCCP), the language is equipped with actions that can also remove constraints from the store. The language can be used for coordinating the agents on a common store of information. Clearly, in such scenario, is important to enhance the operations that the agents may perform with security and privacy, in order to limit their behavior, e.g., to hide some information or to prevent an agent to consume too many resources},
	doi = {10.1145/2245276.2232023},	
	pages = {1551--1553}
}

We present a fine-grained security model to enforce the access control on the constraint store in Concurrent Constraint Programming (CCP) languages. We show the model for a nonmonotonic version of Soft CCP (SCCP), that is an extension of CCP which deals with soft constraints, which are constraints that have a preference level associated to them. In the considered nomonotonic version (NMSCCP), the language is equipped with actions that can also remove constraints from the store. The language can be used for coordinating the agents on a common store of information. Clearly, in such scenario, is important to enhance the operations that the agents may perform with security and privacy, in order to limit their behavior, e.g., to hide some information or to prevent an agent to consume too many resources

@misc{
	11391_1039272,
	author = {Agostiniani, L. and Bakkum, G. C. L. M. and Bistarelli, S. and Calderini, A. and Massarelli, R. and Meiser, G.},
	title = {CELIA. Corpus Elettronico delle Lingue dell'Italia Antica},
	year = {2012}
}

@conference{
	11391_1158902,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {ConArg: Argumentation with Constraints},
	year = {2012},
	publisher = {CEUR Workshop Proceedings},
	volume = {918},
	booktitle = {Proceedings of the First International Conference on Agreement Technologies, AT 2012},
	pages = {197--198}
}

@conference{
	11391_1158899,
	author = {Arbab, Farhad and Santini, Francesco and Bistarelli, Stefano and Pirolandi, Daniele},
	title = {Towards a similarity-based web service discovery through soft constraint satisfaction problems},
	year = {2012},
	publisher = {ACM},
	booktitle = {Proceedings of the 2nd International Workshop on Semantic Search over the Web - SSW '12},
	abstract = {In this paper, we focus on the discovery process of Web Services (WSs) by basing the search on the similarities among the service requirements and candidate search results, in order to cope with over-constrained queries or to find satisfactory alternatives for user requirements. This discovery process needs to involve the so-called Soft Constraint Satisfaction Problems (SCSPs). First we represent both WSs and the search query of the user as Rooted Trees, i.e., a particular form of Conceptual Graphs. Then, we find a homomorphism between these two trees as a solution of an SCSP. The main contribution of this paper is the enhanced expressiveness offered by this "softness": in over-constrained scenarios, when a user query cannot be satisfied, classical crisp constraints (i.e., CSP) are not expressive enough to find "close" solutions to meet the users' needs.},
	doi = {10.1145/2494068.2494070},	
	pages = {1--8}
}

In this paper, we focus on the discovery process of Web Services (WSs) by basing the search on the similarities among the service requirements and candidate search results, in order to cope with over-constrained queries or to find satisfactory alternatives for user requirements. This discovery process needs to involve the so-called Soft Constraint Satisfaction Problems (SCSPs). First we represent both WSs and the search query of the user as Rooted Trees, i.e., a particular form of Conceptual Graphs. Then, we find a homomorphism between these two trees as a solution of an SCSP. The main contribution of this paper is the enhanced expressiveness offered by this "softness": in over-constrained scenarios, when a user query cannot be satisfied, classical crisp constraints (i.e., CSP) are not expressive enough to find "close" solutions to meet the users' needs.

@conference{
	11391_925727,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Securely Accessing Shared Resources with Concurrent Constraint Programming},
	year = {2012},
	publisher = {Springer-Verlag},
	volume = {7504},
	booktitle = {10th International Conference on Software Engineering and Formal Methods (SEFM 2012)},
	abstract = {We present a fine-grained security model to enforce the access control on the shared constraint store in Concurrent Constraint Programming (CCP) languages. We show the model for a nonmonotonic version of Soft CCP (SCCP), that is an extension of CCP where the constraints have a preference level associated with them. Crisp constraints can be modeled in the same framework as well. In the considered nonmonotonic soft version (NmSCCP), it is also possible to remove constraints from the store. The language can be used for coordinating agents on a common store of information that represents the set of shared resources. In such scenarios, it is clearly important to enforce the integrity and confidentiality rights on the resources, in order, for instance, to hide part of the information to some agents, or to prevent an agent to consume too many resources},
	doi = {10.1007/978-3-642-33826-7_21},	
	pages = {308--322}
}

We present a fine-grained security model to enforce the access control on the shared constraint store in Concurrent Constraint Programming (CCP) languages. We show the model for a nonmonotonic version of Soft CCP (SCCP), that is an extension of CCP where the constraints have a preference level associated with them. Crisp constraints can be modeled in the same framework as well. In the considered nonmonotonic soft version (NmSCCP), it is also possible to remove constraints from the store. The language can be used for coordinating agents on a common store of information that represents the set of shared resources. In such scenarios, it is clearly important to enforce the integrity and confidentiality rights on the resources, in order, for instance, to hide part of the information to some agents, or to prevent an agent to consume too many resources

@conference{
	11391_1158900,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Semiring-based constraint models and frameworks for security-related scenarios},
	year = {2012},
	publisher = {IEEE},
	booktitle = {2012 7th International Conference on Risks and Security of Internet and Systems (CRiSIS)},
	abstract = {Semiring-based constraint models and frameworks have been extensively used in literature to optimize different security-related metrics, in order to represent trust scores, levels of security and, in general, quantitative information on shared resources to be securely managed. In this tutorial, we summarize four approaches that show an application of these formal models to different security-related problems, as Access Control List-like rights, policy-based access with weighted credentials, propagation of trust on trust-networks, and the cascade vulnerability problem.},
	doi = {10.1109/CRISIS.2012.6378958},	
	pages = {1--4}
}

Semiring-based constraint models and frameworks have been extensively used in literature to optimize different security-related metrics, in order to represent trust scores, levels of security and, in general, quantitative information on shared resources to be securely managed. In this tutorial, we summarize four approaches that show an application of these formal models to different security-related problems, as Access Control List-like rights, policy-based access with weighted credentials, propagation of trust on trust-networks, and the cascade vulnerability problem.

@conference{
	11391_143643,
	author = {Foley, S. N. and Bella, G. and Bistarelli, Stefano},
	title = {Security Protocol Deployment Risk},
	year = {2011},
	publisher = {Springer-Verlag},
	volume = {6615},
	booktitle = {Proceeding Security'08 Proceedings of the 16th International conference on Security protocols},
	abstract = {Security protocol participants are software and/or hardware agents that are - as with any system - potentially vulnerable to failure. Protocol analysis should extend not just to an analysis of the protocol specification, but also to its implementation and configuration in its target environment. However, an in-depth formal analysis that considers the behaviour and interaction of all components in their environment is not feasible in practice. This paper considers the analysis of protocol deployment rather than implementation. Instead of concentrating on detailed semantics and formal verification of the protocol and implementation, we are concerned more with with the ability to trace, at a practical level of abstraction, how the protocol deployment, that is, the configuration of the protocol components, relate to each other and the overall protocol goals. We believe that a complete security verification of a system is not currently achievable in practice and seek some degree of useful feedback from an analysis that a particular protocol deployment is reasonable},
	doi = {10.1007/978-3-642-22137-8_3},	
	pages = {12--20}
}

Security protocol participants are software and/or hardware agents that are - as with any system - potentially vulnerable to failure. Protocol analysis should extend not just to an analysis of the protocol specification, but also to its implementation and configuration in its target environment. However, an in-depth formal analysis that considers the behaviour and interaction of all components in their environment is not feasible in practice. This paper considers the analysis of protocol deployment rather than implementation. Instead of concentrating on detailed semantics and formal verification of the protocol and implementation, we are concerned more with with the ability to trace, at a practical level of abstraction, how the protocol deployment, that is, the configuration of the protocol components, relate to each other and the overall protocol goals. We believe that a complete security verification of a system is not currently achievable in practice and seek some degree of useful feedback from an analysis that a particular protocol deployment is reasonable

@misc{
	11391_166444,
	author = {Bistarelli, Stefano and Monfroy, Eric and O'Sullivan, Barry},
	title = {Proceedings of the 2011 ACM Symposium on Applied Computing - Constraint solving and programming track},
	year = {2011},
	publisher = {ACM}
}

@conference{
	11391_309093,
	author = {Bistarelli, Stefano and Gosti, Giorgio and Santini, Francesco},
	title = {Solving Fuzzy DCSPs with Naming Games},
	year = {2011},
	publisher = {IEEE},
	booktitle = {23rd IEEE International Conference on Tools with Artificial Intelligence},
	abstract = {In this paper we focus on solving Fuzzy Distributed Constraint Satisfaction Problems (Fuzzy DCSPs) with an algorithm for Naming Games (NGs): each word on which the agents have to agree on is associated with a preference represented as a fuzzy score. The solution is the agreed word associated with the highest preference value. The two main features that distinguish this methodology from Fuzzy DCSPs methods are that the system can react to small instance changes and and it does not require pre-agreed agent/variable ordering.},
	doi = {10.1109/ICTAI.2011.159},	
	pages = {605--612}
}

In this paper we focus on solving Fuzzy Distributed Constraint Satisfaction Problems (Fuzzy DCSPs) with an algorithm for Naming Games (NGs): each word on which the agents have to agree on is associated with a preference represented as a fuzzy score. The solution is the agreed word associated with the highest preference value. The two main features that distinguish this methodology from Fuzzy DCSPs methods are that the system can react to small instance changes and and it does not require pre-agreed agent/variable ordering.

@conference{
	11391_166441,
	author = {Bistarelli, Stefano and Pirolandi, Daniele and Santini, Francesco},
	title = {Solving Weighted Argumentation Frameworks with Soft Constraints},
	year = {2011},
	publisher = {Springer-Verlag},
	volume = {6384/2011},
	booktitle = {Javier Larrosa, Barry O'Sullivan},
	abstract = {We suggest soft constraints as a mean to parametrically represent and solve "weighted" Argumentation problems: 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 semiring algebraic structures. The novel idea is to provide a common computational and quantitative framework where the computation of the classical Dung's extensions, e.g. the admissible extension, has an associated score representing "how much good" the set is. Preference values associated to arguments are clearly more informative and can be used to prefer a given set of arguments over others with the same characteristics (e.g. admissibility). Moreover, we propose a mapping from weighted Argumentation Frameworks to Soft Constraint Satisfaction Problems (SCSPs); with this mapping we can compute Dung semantics (e.g. admissible and stable) by solving the related SCSP. To implement this mapping we use JaCoP, a Java constraint solver.},
	doi = {10.1007/978-3-642-19486-3_1},	
	pages = {1--18}
}

We suggest soft constraints as a mean to parametrically represent and solve "weighted" Argumentation problems: 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 semiring algebraic structures. The novel idea is to provide a common computational and quantitative framework where the computation of the classical Dung's extensions, e.g. the admissible extension, has an associated score representing "how much good" the set is. Preference values associated to arguments are clearly more informative and can be used to prefer a given set of arguments over others with the same characteristics (e.g. admissibility). Moreover, we propose a mapping from weighted Argumentation Frameworks to Soft Constraint Satisfaction Problems (SCSPs); with this mapping we can compute Dung semantics (e.g. admissible and stable) by solving the related SCSP. To implement this mapping we use JaCoP, a Java constraint solver.

@conference{
	11391_166438,
	author = {Bistarelli, Stefano. and Campli, P. and Santini, Francesco},
	title = {Finding Partitions of Arguments with Dung’s Properties via SCSPs},
	year = {2011},
	publisher = {ACM Special Interest Group on Applied Computing (SIGAPP),Tunghai University,Taiwan Ministry of Education,Taiwan Bureau of Foreign Trade,Taiwan National Science Council (NSC)},
	booktitle = {Proceedings of the ACM Symposium on Applied Computing},
	abstract = {Forming coalition structures allows agents to join their forces with the aim to achieve a common task. We suggest it would be interesting to look for homogeneous groups which follow distinct lines of thought. For this reason, we extend the Dung Argumentation Framework in order to deal with coalitions of arguments. The initial set of arguments is partitioned into subsets (or coalitions). Each coalition represents a different line of thought, but all the found coalitions show the same property inherited by Dung, e.g. all the coalitions in the partition are admissible (or conflict-free, complete, stable). Some problems in weighted argumentation are NP complete; we use (soft) constraints as a formal approach to reason about coalitions and to model all these problems in the same framework. Semiring algebraic structures can be used to model different optimization criteria for the obtained coalitions. To implement this mapping and practically find its solutions we use JaCoP, a Java constraint solver, and we test the code over a small-world network.},
	doi = {10.1145/1982185.1982384},	
	pages = {913--919}
}

Forming coalition structures allows agents to join their forces with the aim to achieve a common task. We suggest it would be interesting to look for homogeneous groups which follow distinct lines of thought. For this reason, we extend the Dung Argumentation Framework in order to deal with coalitions of arguments. The initial set of arguments is partitioned into subsets (or coalitions). Each coalition represents a different line of thought, but all the found coalitions show the same property inherited by Dung, e.g. all the coalitions in the partition are admissible (or conflict-free, complete, stable). Some problems in weighted argumentation are NP complete; we use (soft) constraints as a formal approach to reason about coalitions and to model all these problems in the same framework. Semiring algebraic structures can be used to model different optimization criteria for the obtained coalitions. To implement this mapping and practically find its solutions we use JaCoP, a Java constraint solver, and we test the code over a small-world network.

@article{
	11391_166442,
	author = {Bistarelli, S. and Pini, M. S. and Rossi, F. and Venable, K. B.},
	title = {Uncertainty in Bipolar Preference Problems},
	year = {2011},
	journal = {JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE},
	volume = {23},
	abstract = {Preferences and uncertainty are common in many real-life problems. In this article, we focus on bipolar preferences and uncertainty modelled via uncontrollable variables, and we assume that uncontrollable variables are specified by possibility distributions over their domains. To tackle such problems, we concentrate on uncertain bipolar problems with totally ordered preferences, and we eliminate the uncertain part of the problem, while making sure that some desirable properties hold about the robustness of the problem and its relationship with the preference of the optimal solutions. We also consider several semantics to order the solutions according to different attitudes with respect to the notions of preference and robustness.},
	keywords = {Soft constraints, Preferences, Uncertainty, Possibility theory, Positive and negative judgements},
	doi = {10.1080/0952813X.2010.524288},	
	pages = {545--575}
}

Preferences and uncertainty are common in many real-life problems. In this article, we focus on bipolar preferences and uncertainty modelled via uncontrollable variables, and we assume that uncontrollable variables are specified by possibility distributions over their domains. To tackle such problems, we concentrate on uncertain bipolar problems with totally ordered preferences, and we eliminate the uncertain part of the problem, while making sure that some desirable properties hold about the robustness of the problem and its relationship with the preference of the optimal solutions. We also consider several semantics to order the solutions according to different attitudes with respect to the notions of preference and robustness.

@conference{
	11391_309293,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {ConArg: A Constraint-based Computational Framework for Argumentation Systems},
	year = {2011},
	publisher = {IEEE},
	booktitle = {Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI},
	abstract = {We propose ConArg, a tool based on Constraint Programming, to model and solve various problems related to the Argumentation research field. Constraint Satisfaction Problems (CSPs) offer a wide number of efficient techniques (as inference and search algorithms) that can tackle the complexity in finding all the possible Dung's conflict-free, admissible, complete, stable, preferred and grounded extensions in Argumentation Frameworks. Moreover, we can use the tool to solve some computationally hard problems presented in [1]. To implement ConArg, we have used JaCoP, a Java library which provides the user with a Finite Domain Constraint Programming paradigm, to model and solve these two problems. ConArg is able to randomly generate two different kinds of small-world networks in order to find Dung's extensions on such interaction graphs. We present the main features of ConArg and the reported performance in time.},
	doi = {10.1109/ICTAI.2011.96},	
	pages = {605--612}
}

We propose ConArg, a tool based on Constraint Programming, to model and solve various problems related to the Argumentation research field. Constraint Satisfaction Problems (CSPs) offer a wide number of efficient techniques (as inference and search algorithms) that can tackle the complexity in finding all the possible Dung's conflict-free, admissible, complete, stable, preferred and grounded extensions in Argumentation Frameworks. Moreover, we can use the tool to solve some computationally hard problems presented in [1]. To implement ConArg, we have used JaCoP, a Java library which provides the user with a Finite Domain Constraint Programming paradigm, to model and solve these two problems. ConArg is able to randomly generate two different kinds of small-world networks in order to find Dung's extensions on such interaction graphs. We present the main features of ConArg and the reported performance in time.

@article{
	11391_309693,
	author = {Bistarelli, S. and Santini, F.},
	title = {A Nonmonotonic Soft Concurrent Constraint Language to Model the negotiation Process},
	year = {2011},
	journal = {FUNDAMENTA INFORMATICAE},
	volume = {111},
	abstract = {We present an extension of the Soft Concurrent Constraint language that allows the nonmonotonic evolution of the constraint store. To accomplish this, we introduce some new operations: retract (c) reduces the current store by c, update(X) (c) transactionally relaxes all the constraints of the store that deal with the variables in the set X, and then adds a constraint c; nask (c) tests if c is not entailed by the store. The new retraction operators also permit to reason about Belief Revision, i.e. the process of changing beliefs to take into account a new piece of information. We present this framework as a possible solution to the negotiation of resources (e. g. web services and network resource allocation) that need a given Quality of Service (QoS). For this reason we also show the the new operators of the language satisfy the Belief Revision postulates [20], which can be used in the negotiation process. The QoS requirements (expressed as semiring levels) of all the parties should converge on a formal agreement through a negotiation process, which specifies the contract that must be enforced.},
	keywords = {Soft Constraint, Constraint, Concurrent Programming, Nonmonotonicity,Belief Revision, Quality of Service, Negotiation},
	doi = {10.3233/FI-2011-563},	
	pages = {257--279}
}

We present an extension of the Soft Concurrent Constraint language that allows the nonmonotonic evolution of the constraint store. To accomplish this, we introduce some new operations: retract (c) reduces the current store by c, update(X) (c) transactionally relaxes all the constraints of the store that deal with the variables in the set X, and then adds a constraint c; nask (c) tests if c is not entailed by the store. The new retraction operators also permit to reason about Belief Revision, i.e. the process of changing beliefs to take into account a new piece of information. We present this framework as a possible solution to the negotiation of resources (e. g. web services and network resource allocation) that need a given Quality of Service (QoS). For this reason we also show the the new operators of the language satisfy the Belief Revision postulates [20], which can be used in the negotiation process. The QoS requirements (expressed as semiring levels) of all the parties should converge on a formal agreement through a negotiation process, which specifies the contract that must be enforced.

@conference{
	11391_1158905,
	author = {Bistarelli, Stefano and Campli, Paola and Santini, Francesco},
	title = {Finding Partitions of Arguments with Dung's Properties via SCSPs},
	year = {2011},
	publisher = {CEUR Workshop Proceedings},
	volume = {810},
	booktitle = {CEUR Workshop Proceedings - 26th Italian Conference on Computational Logic, CILC 2011},
	abstract = {Forming coalition structures allows agents to join their forces to achieve a common task. We suggest it would be interesting to look for homogeneous groups which follow distinct lines of thought. For this reason, we extend the Dung Argumentation Framework in order to deal with coalitions of arguments. The initial set of arguments is partitioned into subsets (or coalitions). Each coalition represents a different line of thought, but all the found coalitions show the same property inherited by Dung, e.g. all the coalitions in the partition are admissible (or conflict-free, complete, stable). Some problems in weighted argumentation are NP complete; we use (soft) constraints as a formal approach to reason about coalitions and to model all these problems in the same framework. Semiring algebraic structures can be used to model different optimization criteria for the obtained coalitions. To implement this mapping and practically find its solutions we use JaCoP, a Java constraint solver, and we test the code over a small-world network.},
	pages = {199--213}
}

Forming coalition structures allows agents to join their forces to achieve a common task. We suggest it would be interesting to look for homogeneous groups which follow distinct lines of thought. For this reason, we extend the Dung Argumentation Framework in order to deal with coalitions of arguments. The initial set of arguments is partitioned into subsets (or coalitions). Each coalition represents a different line of thought, but all the found coalitions show the same property inherited by Dung, e.g. all the coalitions in the partition are admissible (or conflict-free, complete, stable). Some problems in weighted argumentation are NP complete; we use (soft) constraints as a formal approach to reason about coalitions and to model all these problems in the same framework. Semiring algebraic structures can be used to model different optimization criteria for the obtained coalitions. To implement this mapping and practically find its solutions we use JaCoP, a Java constraint solver, and we test the code over a small-world network.

@article{
	11391_121123,
	author = {Bistarelli, Stefano and Montanari, Ugo and Rossi, Francesca and Santini, Francesco},
	title = {Unicast and Multicast QoS Routing with Soft Constraint Logic Programming},
	year = {2010},
	journal = {ACM TRANSACTIONS ON COMPUTATIONAL LOGIC},
	volume = {12},
	abstract = {We present a formal model to represent and solve the unicast/multicast routing problem in networks with quality-of-service (QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or and-or graph (multicast), where the weight on a connector corresponds to the multidimensional cost of sending a packet on the related network link: each component of the weights vector represents a different QoS metric value (e.g., bandwidth). The second step consists in writing this graph as a program in soft-constraint logic programming (SCLP): the engine of this framework is then able to find the best paths/trees by optimizing their costs and solving the constraints imposed on them (e.g. delay ≤ 40 ms), thus finding a solution to QoS routing problems. C-semiring structures are a convenient tool to model QoS metrics. At last, we provide an implementation of the framework over scale-free networks and we suggest how the performance can be improved. The article highlights the expressivity of SCLP.},
	keywords = {Constraints; soft constraints, Preferences, Quality of Service (QoS), Routing, Constraint logic programming (CLP), Soft constraint},
	doi = {10.1145/1838552.1838557},	
}

We present a formal model to represent and solve the unicast/multicast routing problem in networks with quality-of-service (QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or and-or graph (multicast), where the weight on a connector corresponds to the multidimensional cost of sending a packet on the related network link: each component of the weights vector represents a different QoS metric value (e.g., bandwidth). The second step consists in writing this graph as a program in soft-constraint logic programming (SCLP): the engine of this framework is then able to find the best paths/trees by optimizing their costs and solving the constraints imposed on them (e.g. delay ≤ 40 ms), thus finding a solution to QoS routing problems. C-semiring structures are a convenient tool to model QoS metrics. At last, we provide an implementation of the framework over scale-free networks and we suggest how the performance can be improved. The article highlights the expressivity of SCLP.

@article{
	11391_121120,
	author = {Bistarelli, Stefano and Pini, MARIA SILVIA and Rossi, Francesca and Venable, K. BRENT},
	title = {From soft constraints to bipolar preferences: modelling framework and solving issues},
	year = {2010},
	journal = {JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE},
	volume = {22},
	abstract = {Real-life problems present several kinds of preferences. We focus on problems with both positive and negative preferences, which we call bipolar preference problems. Although seemingly specular notions, these two kinds of preferences should be dealt with differently to obtain the desired natural behaviour. We technically address this by generalising the soft constraint formalism, which is able to model problems with one kind of preference. We show that soft constraints model only negative preferences, and we add to them a new mathematical structure which allows to handle positive preferences as well. We also address the issue of the compensation between positive and negative preferences, studying the properties of this operation. Finally, we extend the notion of arc consistency to bipolar problems, and we show how branch and bound (with or without constraint propagation) can be easily adapted to solve such problems.},
	keywords = {Soft constraints, Preferences, Negative and positive judgements},
	doi = {10.1080/09528130903010212},	
	pages = {135--158}
}

Real-life problems present several kinds of preferences. We focus on problems with both positive and negative preferences, which we call bipolar preference problems. Although seemingly specular notions, these two kinds of preferences should be dealt with differently to obtain the desired natural behaviour. We technically address this by generalising the soft constraint formalism, which is able to model problems with one kind of preference. We show that soft constraints model only negative preferences, and we add to them a new mathematical structure which allows to handle positive preferences as well. We also address the issue of the compensation between positive and negative preferences, studying the properties of this operation. Finally, we extend the notion of arc consistency to bipolar problems, and we show how branch and bound (with or without constraint propagation) can be easily adapted to solve such problems.

@article{
	11391_121124,
	author = {Bistarelli, Stefano and Foley, Simon N. and O'Sullivan, Barry and Santini, Francesco},
	title = {Semiring-based Frameworks for Trust Propagation in Small-World Networks and Coalition Formation Criteria},
	year = {2010},
	journal = {SECURITY AND COMMUNICATION NETWORKS},
	volume = {3},
	abstract = {Multitrust provides a flexible approach to encoding trust metrics whereby definitions for trust propagation and aggregation are specified in terms of a semiring. Determining the degree of trust between principals across a trust network (TN) is, in turn, programmed as a (semiring-based) soft-constraint satisfaction problem. In this paper, we consider the use of semiring-based metrics in reasoning about trust between coalition-forming principals. The configurable nature of multitrust makes it well-suited to modeling trust within coalitions: whether adding more principals to a coalition increases trust or decreases trust is captured by the definition of trust aggregation within the semiring.},
	keywords = {And-or graphs, Soft constraint logic programming, Trust network, Trust propagation},
	doi = {10.1002/sec.252},	
	pages = {595--610}
}

Multitrust provides a flexible approach to encoding trust metrics whereby definitions for trust propagation and aggregation are specified in terms of a semiring. Determining the degree of trust between principals across a trust network (TN) is, in turn, programmed as a (semiring-based) soft-constraint satisfaction problem. In this paper, we consider the use of semiring-based metrics in reasoning about trust between coalition-forming principals. The configurable nature of multitrust makes it well-suited to modeling trust within coalitions: whether adding more principals to a coalition increases trust or decreases trust is captured by the definition of trust aggregation within the semiring.

@conference{
	11391_166440,
	author = {Bistarelli, Stefano and Martinelli, Fabio and Santini, Francesco},
	title = {A Formal Framework for Trust Policy Negotiation in Autonomic Systems: Abduction with Soft Constraints},
	year = {2010},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {6407},
	booktitle = {Autonomic and Trusted Computing, 7th International Conference, ATC 2010.},
	pages = {268--282}
}

@conference{
	11391_166439,
	author = {Bistarelli, Stefano and Gadducci, Fabio and Larrosa, Javier and Rollon, Emma and Santini, Francesco},
	title = {Extending Soft Arc Consistency to Non-Invertible Semirings},
	year = {2010},
	publisher = {Springer},
	volume = {6437},
	booktitle = {Advances in Artificial Intelligence - 9th Mexican International Conference on Artificial Intelligence, MICAI 2010},
	abstract = {We extend algorithms for arc consistency proposed in the literature in order to deal with (absorptive) semirings that are not invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings: among other instances, for those semirings obtained as the cartesian product of any family of semirings. The main application is that the new arc consistency algorithm can be used for multi-criteria soft CSPs. To reach this objective, we first show that any semiring can be transformed into a new one where the + operator is instantiated with the Least Common Divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm (when the × operator of the semiring is not idempotent). We then propose an arc consistency algorithm which takes advantage of this LCD operator.},
	doi = {10.1007/978-3-642-16761-4_34},	
	pages = {386--398}
}

We extend algorithms for arc consistency proposed in the literature in order to deal with (absorptive) semirings that are not invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings: among other instances, for those semirings obtained as the cartesian product of any family of semirings. The main application is that the new arc consistency algorithm can be used for multi-criteria soft CSPs. To reach this objective, we first show that any semiring can be transformed into a new one where the + operator is instantiated with the Least Common Divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm (when the × operator of the semiring is not idempotent). We then propose an arc consistency algorithm which takes advantage of this LCD operator.

@misc{
	11391_166443,
	author = {Bistarelli, Stefano and Monfroy, Eric and O'Sullivan, Barry},
	title = {Proceedings of the 2010 ACM Symposium on Applied Computing - Constraint solving and programming track},
	year = {2010}
}

@article{
	11391_166445,
	author = {Bistarelli, S. and Gosti, G.},
	title = {Solving Distributed CSPs Probabilistically},
	year = {2010},
	journal = {FUNDAMENTA INFORMATICAE},
	volume = {105},
	abstract = {Constraint solving problems (CSPs) are the formalization of a large range of problems that emerge fromcomputer science. The solving methodology described here is based on the naming game. The two main features that distinguish this methodology from most distributed constraint solving problem (DCSPs) methods are: the system can react to small instance changes, and it does not require pre-agreed agent/variable ordering. The naming game was introduced to represent N agents that have to bootstrap an agreement on a name to give to an object. The agents do not have a hierarchy, and use a minimal protocol. Still they converge to a consistent state by using a distributed strategy. For this reason, the naming game can be used to untangle DCSPs. It was shown that a distributed system of uniform finite state machines does not solve the ring ordering problem in all the algorithm executions. Our algorithm is a distributed uniform system of agents able to perform random decisions when presented with equivalent alternatives. We show that this algorithm solves the ring ordering problem with a probability one.},
	keywords = {NAMING GAMES, NETWORK,  LANGUAGE},
	doi = {10.3233/FI-2010-358},	
	pages = {57--78}
}

Constraint solving problems (CSPs) are the formalization of a large range of problems that emerge fromcomputer science. The solving methodology described here is based on the naming game. The two main features that distinguish this methodology from most distributed constraint solving problem (DCSPs) methods are: the system can react to small instance changes, and it does not require pre-agreed agent/variable ordering. The naming game was introduced to represent N agents that have to bootstrap an agreement on a name to give to an object. The agents do not have a hierarchy, and use a minimal protocol. Still they converge to a consistent state by using a distributed strategy. For this reason, the naming game can be used to untangle DCSPs. It was shown that a distributed system of uniform finite state machines does not solve the ring ordering problem in all the algorithm executions. Our algorithm is a distributed uniform system of agents able to perform random decisions when presented with equivalent alternatives. We show that this algorithm solves the ring ordering problem with a probability one.

@conference{
	11391_170515,
	author = {Bistarelli, S. and Campli, P. and Santini, F.},
	title = {Finding Partitions of Arguments with Dung’s Properties via SCSPs},
	year = {2010},
	booktitle = {Proceedings of the Eleventh AI*IA Symposium on Artificial Intelligence},
	pages = {201--208}
}

@conference{
	11391_143885,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {A Common Computational Framework for Semiring-based Argumentation Systems},
	year = {2010},
	publisher = {IOS Press},
	volume = {215},
	booktitle = {ECAI 2010 - 19th European Conference on Artificial Intelligence},
	abstract = {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.},
	doi = {10.3233/978-1-60750-606-5-131},	
	pages = {131--136}
}

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.

@conference{
	11391_1158904,
	author = {Bistarelli, Stefano and Daniele, Pirolandi and Santini, Francesco},
	title = {Solving Weighted Argumentation Farmeworks with Soft Constraints},
	year = {2010},
	publisher = {CEUR-WS.org},
	volume = {598},
	booktitle = {Proceedings of the 25th Italian Conference on Computational Logic}
}

@article{
	11391_121122,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Implementing and Testing a Formal Framework for Constraint-Based Routing over Scale-free Networks},
	year = {2009},
	journal = {INTERNATIONAL JOURNAL ON ADVANCES IN NETWORKS AND SERVICES},
	volume = {2},
	url = {http://www.iariajournals.org/networks_and_services/},
	pages = {13--24}
}

@conference{
	11391_121121,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {A Nonmonotonic Soft Concurrent Constraint Language for SLA Negotiation},
	year = {2009},
	publisher = {ELSEVIER},
	journal = {ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE},
	volume = {236},
	booktitle = {Proceedings of the 3rd International Workshop on Views On Designing Complex Architectures (VODCA 2008)},
	abstract = {We present an extension of the Soft Concurrent Constraint language that allows the nonmonotonic evolution of the constraint store. To accomplish this, we introduce some new operations: the retract(c) reduces the current store by c, the updateX(c) transactionally relaxes all the constraints of the store that deal with the variables in the set X, and then adds a constraint c; the nask(c) tests if c is not entailed by the store. We present this framework as a possible solution to the management of resources (e.g. web services and network resource allocation) that need a given Quality of Service (QoS). The QoS requirements of all the parties should converge, through a negotiation process, on a formal agreement defined as the Service Level Agreement, which specifies the contract that must be enforced. c-semirings are the algebraic structures that we use to model QoS metrics.},
	keywords = {soft constraint logic programming; nonmonotonicity; quality of service; service level agreement},
	doi = {10.1016/j.entcs.2009.03.020},	
	pages = {147--162}
}

We present an extension of the Soft Concurrent Constraint language that allows the nonmonotonic evolution of the constraint store. To accomplish this, we introduce some new operations: the retract(c) reduces the current store by c, the updateX(c) transactionally relaxes all the constraints of the store that deal with the variables in the set X, and then adds a constraint c; the nask(c) tests if c is not entailed by the store. We present this framework as a possible solution to the management of resources (e.g. web services and network resource allocation) that need a given Quality of Service (QoS). The QoS requirements of all the parties should converge, through a negotiation process, on a formal agreement defined as the Service Level Agreement, which specifies the contract that must be enforced. c-semirings are the algebraic structures that we use to model QoS metrics.

@article{
	11391_121119,
	author = {Bistarelli, Stefano and Codognet, Philippe and Hui, H. K. C. and Lee, J. H. M.},
	title = {Solving finite domain constraint hierarchies by local consistency and tree search},
	year = {2009},
	journal = {JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE},
	volume = {21},
	abstract = {We provide a reformulation of the constraint hierarchies (CHs) framework based on the notion of error indicators. Adapting the generalised view of local consistency in semiring-based constraint satisfaction problems, 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 (FD) CH solver. Experimentation confirms the efficiency and robustness of our proposed solver prototype. Unlike other FD CH solvers, our proposed method works for both local and global comparators. In addition, our solver can support arbitrary error functions.},
	keywords = {Constraint hierarchies, Soft constraints, Local consistency},
	doi = {10.1080/09528130802667690},	
	pages = {233--257}
}

We provide a reformulation of the constraint hierarchies (CHs) framework based on the notion of error indicators. Adapting the generalised view of local consistency in semiring-based constraint satisfaction problems, 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 (FD) CH solver. Experimentation confirms the efficiency and robustness of our proposed solver prototype. Unlike other FD CH solvers, our proposed method works for both local and global comparators. In addition, our solver can support arbitrary error functions.

@conference{
	11391_143646,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Soft Constraints for Dependable Service Oriented Architectures},
	year = {2009},
	publisher = {Springer},
	volume = {5835},
	booktitle = {DSN 2008: Workshop on Software Architectures for Dependable Systems (WADS)},
	abstract = {We propose the use of Soft Constraints as a natural way to model Service Oriented Architecture. In the framework, constraints are used to model components and connectors and constraint aggregation is used to represent their interactions. Moreover, a specific constraint projection operator is used to highlight the service interface. The quality of a service is measured and considered when performing queries to service providers. In particular, we are here interested to aspect of dependability, that is to the trustworthiness of a computing system on the service it delivers. In our framework, the dependability score is represented by the softness level of the constraint and the measure of complex (web) services is computed by combining the levels of the components. The framework takes also in account the interaction of software agents representing distributed services, by using a constraint based concurrent language able to also decide the collaboration taking care of the required dependability score.},
	doi = {10.1007/978-3-642-10248-6_4},	
	pages = {76--97}
}

We propose the use of Soft Constraints as a natural way to model Service Oriented Architecture. In the framework, constraints are used to model components and connectors and constraint aggregation is used to represent their interactions. Moreover, a specific constraint projection operator is used to highlight the service interface. The quality of a service is measured and considered when performing queries to service providers. In particular, we are here interested to aspect of dependability, that is to the trustworthiness of a computing system on the service it delivers. In our framework, the dependability score is represented by the softness level of the constraint and the measure of complex (web) services is computed by combining the levels of the components. The framework takes also in account the interaction of software agents representing distributed services, by using a constraint based concurrent language able to also decide the collaboration taking care of the required dependability score.

@conference{
	11391_143883,
	author = {Bistarelli, Stefano and Campli, Paola},
	title = {Fairness as a QoS Measure for Web Services},
	year = {2009},
	publisher = {--},
	journal = {ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE},
	volume = {2},
	booktitle = {Proceedings Fourth European Young Researchers Workshop on  Service Oriented Computing},
	doi = {10.4204/EPTCS.2.9},	
	pages = {115--127}
}

@misc{
	11391_146887,
	author = {Bistarelli, Stefano and Monfroy, Eric and O'Sullivan, Barry},
	title = {Proceedings of the 2009 ACM Symposium on Applied Computing - Constraint solving and programming track},
	year = {2009},
	publisher = {ACM Press},
	abstract = {atti di convegno.}
}

atti di convegno.

@conference{
	11391_143834,
	author = {Bistarelli, Stefano and Gosti, Giorgio},
	title = {Solving CSPs with Naming Games},
	year = {2009},
	publisher = {Springer},
	volume = {5655},
	booktitle = {Revised Selected Papers Recent Advances in Constraints, CSCLP. June 18-20, 2008},
	abstract = {Revised Selected Papers
Recent Advances in Constraints, CSCLP.
June 18-20, 2008.
Rome, Italy.
Springer.
AMSTERDAM.
ISBN: 9783642032509},
	doi = {10.1007/978-3-642-03251-6_2},	
	pages = {16--32}
}

Revised Selected Papers Recent Advances in Constraints, CSCLP. June 18-20, 2008. Rome, Italy. Springer. AMSTERDAM. ISBN: 9783642032509

@conference{
	11391_143884,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Soft Constraints for Quality Aspects in Service Oriented                Architectures},
	year = {2009},
	publisher = {Open Publishing Association},
	journal = {ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE},
	volume = {2},
	booktitle = {Proceedings Fourth European Young Researchers Workshop on  Service Oriented Computing},
	doi = {10.4204/EPTCS.2.5},	
	pages = {51--65}
}

@conference{
	11391_143645,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {C-semiring Frameworks for Minimum Spanning Tree Problems},
	year = {2009},
	publisher = {Springer},
	volume = {5486},
	booktitle = {Recent Trends in Algebraic Development Techniques, 19th International Workshop, WADT 2008},
	abstract = {In this paper we define general algebraic frameworks for the Minimum Spanning Tree problem based on the structure of c-semirings. We propose general algorithms that can compute such trees by following different cost criteria, which must be all specific instantiation of c-semirings. Our algorithms are extensions of well-known procedures, as Prim or Kruskal, and show the expressivity of these algebraic structures. They can deal also with partially-ordered costs on the edges.},
	doi = {10.1007/978-3-642-03429-9_5},	
	pages = {56--70}
}

In this paper we define general algebraic frameworks for the Minimum Spanning Tree problem based on the structure of c-semirings. We propose general algorithms that can compute such trees by following different cost criteria, which must be all specific instantiation of c-semirings. Our algorithms are extensions of well-known procedures, as Prim or Kruskal, and show the expressivity of these algebraic structures. They can deal also with partially-ordered costs on the edges.

@conference{
	11391_143835,
	author = {Bistarelli, Stefano and Foley, SIMON N. and O'Sullivan, Barry and Santini, Francesco},
	title = {From Marriages to Coalitions: A Soft CSP Approach},
	year = {2009},
	publisher = {Springer},
	volume = {5655},
	booktitle = {Revised Selected Papers Recent Advances in Constraints, CSCLP 2008},
	abstract = {In this work we represent the Optimal Stable Marriage problem as a Soft Constraint Satisfaction Problem. In addition, we extend this problem from couples of individuals to coalitions of generic agents, in order to define new coalition-formation principles and stability conditions. In the coalition case, we suppose the preference value as a trust score, since trust can describe the belief of a node in the capabilities of another node, in its honesty and reliability. Semiring-based soft constraints represent a general and expressive framework that is able to deal with distinct concepts of optimality by only changing the related c-semiring structure, instead of using different ad-hoc algorithms. At last, we propose an implementation of the classical OSM problem using integer linear programming tools.},
	doi = {10.1007/978-3-642-03251-6_1},	
	pages = {1--15}
}

In this work we represent the Optimal Stable Marriage problem as a Soft Constraint Satisfaction Problem. In addition, we extend this problem from couples of individuals to coalitions of generic agents, in order to define new coalition-formation principles and stability conditions. In the coalition case, we suppose the preference value as a trust score, since trust can describe the belief of a node in the capabilities of another node, in its honesty and reliability. Semiring-based soft constraints represent a general and expressive framework that is able to deal with distinct concepts of optimality by only changing the related c-semiring structure, instead of using different ad-hoc algorithms. At last, we propose an implementation of the classical OSM problem using integer linear programming tools.

@conference{
	11391_1002067,
	author = {Campli, Paola and Bistarelli, Stefano},
	title = {Capturing Fair Computations on Concurrent Constraint Language},
	year = {2009},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {5649},
	booktitle = {Logic Programming},
	doi = {10.1007/978-3-642-02846-5_63},	
	pages = {559--560}
}

@conference{
	11391_1002066,
	author = {Bottalico, Marco and Bistarelli, Stefano},
	title = {Constraint Based Languages for Biological Reactions},
	year = {2009},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {5649},
	booktitle = {Logic Programming},
	doi = {10.1007/978-3-642-02846-5_64},	
	pages = {561--562}
}

@article{
	11391_121118,
	author = {Bella, Giampaolo and Bistarelli, Stefano and Massacci, Fabio},
	title = {Retaliation Against Protocol Attacks},
	year = {2008},
	journal = {JOURNAL OF INFORMATION ASSURANCE AND SECURITY},
	volume = {3},
	abstract = {Security protocols intend to give their parties reasonable assurance that certain security properties will protect their communication session. However, the literature confirms that the protocols may suffer subtle and hidden attacks. Flawed protocols are customarily sent back to the design process, but the costs of reengineering a deployed protocol may be prohibitive. This paper outlines the concept of retaliation: who would steal a sum of money today, should this pose significant risks of having twice as much stolen back tomorrow? When ethics is left behind, attacks are always balanced decisions: if an attack can be retaliated, the economics of security may convince the attacker to refrain from attacking, and us to live with a flawed protocol. This new perspective requires a new threat model where any party may decide to subvert the protocol for his own sake, depending on the risks of retaliation. This threat model, which for example is also suitable to studying non-repudiation protocols, seems more appropriate than the Dolev-Yao model to the present technological/social setting. It is demonstrated that machine-assisted protocol verification can and must be tailored to the new threat model.},
	pages = {313--325}
}

Security protocols intend to give their parties reasonable assurance that certain security properties will protect their communication session. However, the literature confirms that the protocols may suffer subtle and hidden attacks. Flawed protocols are customarily sent back to the design process, but the costs of reengineering a deployed protocol may be prohibitive. This paper outlines the concept of retaliation: who would steal a sum of money today, should this pose significant risks of having twice as much stolen back tomorrow? When ethics is left behind, attacks are always balanced decisions: if an attack can be retaliated, the economics of security may convince the attacker to refrain from attacking, and us to live with a flawed protocol. This new perspective requires a new threat model where any party may decide to subvert the protocol for his own sake, depending on the risks of retaliation. This threat model, which for example is also suitable to studying non-repudiation protocols, seems more appropriate than the Dolev-Yao model to the present technological/social setting. It is demonstrated that machine-assisted protocol verification can and must be tailored to the new threat model.

@conference{
	11391_121117,
	author = {Bistarelli, Stefano and Peretti, Pamela and Trubitsyna, Irina},
	title = {Analyzing security scenarios using Defence Trees and Answer Set Programming},
	year = {2008},
	publisher = {ELSEVIER},
	journal = {ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE},
	volume = {197},
	booktitle = {Proceedings of the 3rd International Workshop on Security and Trust Management (STM 2007)},
	abstract = {Defence trees are used to represent attack and defence strategies in security scenarios; the aim in such scenarios is to select the best set of countermeasures that are able to stop all the vulnerabilities.

In order to represent preferences among possible countermeasures of a given attack, defence trees are enriched with conditional preferences, obtaining a new structure called CP-defence tree. In this paper we transform a CP-defence tree with preferences among attacks and countermeasures in an Answer Set Optimization (ASO) program. The ASO program, representing the overall scenario, is a special composition of the programs associated to each branch of a CP-defence tree. We describe an implementation that select the best set of countermeasure able to mitigate all the vulnerabilities by computing the optimal answer set of the corresponding ASO program.},
	keywords = {Defence tree; Answer Set Programming; CR-Prolog},
	doi = {10.1016/j.entcs.2007.12.021},	
	pages = {121--129}
}

Defence trees are used to represent attack and defence strategies in security scenarios; the aim in such scenarios is to select the best set of countermeasures that are able to stop all the vulnerabilities. In order to represent preferences among possible countermeasures of a given attack, defence trees are enriched with conditional preferences, obtaining a new structure called CP-defence tree. In this paper we transform a CP-defence tree with preferences among attacks and countermeasures in an Answer Set Optimization (ASO) program. The ASO program, representing the overall scenario, is a special composition of the programs associated to each branch of a CP-defence tree. We describe an implementation that select the best set of countermeasure able to mitigate all the vulnerabilities by computing the optimal answer set of the corresponding ASO program.

@inbook{
	11391_131196,
	author = {Bistarelli, Stefano and Rossi, Francesca},
	title = {Semiring-Based Soft Constraints},
	year = {2008},
	publisher = {Springer},
	volume = {5065},
	booktitle = {Concurrency, Graphs and Models, Essays Dedicated to Ugo Montanari on the Occasion of His 65th Birthday},
	abstract = {The semiring-based formalism to model soft constraint has been introduced in 1995 by Ugo Montanari and the authors of this paper. The idea was to make constraint programming more flexible and widely applicable. We also wanted to define the extension via a general formalism, so that all its instances could inherit its properties and be easily compared. Since then, much work has been done to study, extend, and apply this formalism. This papers gives a brief summary of some of these research activities.},
	pages = {155--173}
}

The semiring-based formalism to model soft constraint has been introduced in 1995 by Ugo Montanari and the authors of this paper. The idea was to make constraint programming more flexible and widely applicable. We also wanted to define the extension via a general formalism, so that all its instances could inherit its properties and be easily compared. Since then, much work has been done to study, extend, and apply this formalism. This papers gives a brief summary of some of these research activities.

@misc{
	11391_146837,
	author = {Bistarelli, Stefano and Monfroy, Eric and O'Sullivan, Barry},
	title = {Proceedings of the 2008 ACM Symposium on Applied Computing - Constraint solving and programming track},
	year = {2008},
	publisher = {ACM Press},
	abstract = {atti di convegno.}
}

atti di convegno.

@conference{
	11391_161113,
	author = {Bistarelli, Stefano and Gabbrielli, Maurizio and Meo, Maria Chiara and Santini, Francesco},
	title = {Timed Soft Concurrent Constraint Programs},
	year = {2008},
	publisher = {Springer},
	volume = {5052},
	booktitle = {Coordination Models and Languages, 10th International Conference, COORDINATION 2008},
	abstract = {We propose a timed and soft extension of Concurrent Constraint Programming. The time extension is based on the hypothesis of bounded asynchrony: the computation takes a bounded period of time and is measured by a discrete global clock. Action prefixing is then considered as the syntactic marker which distinguishes a time instant from the next one. Supported by soft constraints instead of crisp ones, tell and ask agents are now equipped with a preference (or consistency) threshold which is used to determine their success or suspension. In the paper we provide a language to describe the agents behavior, together with its operational and denotational semantics, for which we also prove the compositionality and correctness properties. Agents negotiating Quality of Service can benefit from this new language, by coordinating among themselves and mediating their preferences.},
	doi = {10.1007/978-3-540-68265-3_4},	
	pages = {50--66}
}

We propose a timed and soft extension of Concurrent Constraint Programming. The time extension is based on the hypothesis of bounded asynchrony: the computation takes a bounded period of time and is measured by a discrete global clock. Action prefixing is then considered as the syntactic marker which distinguishes a time instant from the next one. Supported by soft constraints instead of crisp ones, tell and ask agents are now equipped with a preference (or consistency) threshold which is used to determine their success or suspension. In the paper we provide a language to describe the agents behavior, together with its operational and denotational semantics, for which we also prove the compositionality and correctness properties. Agents negotiating Quality of Service can benefit from this new language, by coordinating among themselves and mediating their preferences.

@conference{
	11391_143640,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {SCLP for Trust Propagation in Small-World Networks},
	year = {2008},
	publisher = {Springer},
	volume = {5129},
	booktitle = {Recent Advances in Constraints, 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2007.},
	abstract = {We propose Soft Constraint Logic Programming based on semirings as a mean to easily represent and evaluate trust propagation in small-world networks. To attain this, we model the trust network adapting it to a weighted and-or graph, where the weight on a connector corresponds to the trust and confidence feedback values among the connected nodes. Semirings are the parametric and flexible structures used to appropriately represent trust metrics. Social (and not only) networks present small-world properties: most nodes can be reached from every other by a small number of hops. These features can be exploited to reduce the computational complexity of the model. In the same model we also introduce the concept of multitrust, which is aimed at computing trust by collectively involving a group of trustees at the same time.},
	doi = {10.1007/978-3-540-89812-2_3},	
	pages = {32--46}
}

We propose Soft Constraint Logic Programming based on semirings as a mean to easily represent and evaluate trust propagation in small-world networks. To attain this, we model the trust network adapting it to a weighted and-or graph, where the weight on a connector corresponds to the trust and confidence feedback values among the connected nodes. Semirings are the parametric and flexible structures used to appropriately represent trust metrics. Social (and not only) networks present small-world properties: most nodes can be reached from every other by a small number of hops. These features can be exploited to reduce the computational complexity of the model. In the same model we also introduce the concept of multitrust, which is aimed at computing trust by collectively involving a group of trustees at the same time.

@conference{
	11391_161102,
	author = {Bistarelli, Stefano and Martinelli, Fabio and Santini, Francesco},
	title = {Weighted Datalog and Levels of Trust},
	year = {2008},
	publisher = {IEEE Computer Society Press},
	booktitle = {Proceedings of the The Third International Conference on Availability, Reliability and Security, ARES 2008, March 4-7, 2008, Technical University of Catalonia, Barcelona, Spain},
	abstract = {We extend the Datalog language (we call it Datalog^W)in order to deal with weights on ground facts and to consequently compute a feedback result for the goal satisfaction. The weights are chosen from a proper c-semiring. As a second step, in order to show the usefulness of the language, we use DatalogW as the basis to give a uniform semantics to declarative RTW (Trust Management) language family, in order to represent trust levels based on c-semirings. In this way it is possible to manage a score corresponding to a preference or cost associated to the revealed credentials, instead of a plain “yes or no” authorization result. Clearly, such a solution is more informative and allows us to treat uncertainty of facts and rules application, or different preferencesfor the entity roles. Trust can be then derived by choosing the best chain. The approach is rather generic and could be applied to other trust management languages.},
	doi = {10.1109/ARES.2008.197},	
	pages = {1128--1134}
}

We extend the Datalog language (we call it Datalog^W)in order to deal with weights on ground facts and to consequently compute a feedback result for the goal satisfaction. The weights are chosen from a proper c-semiring. As a second step, in order to show the usefulness of the language, we use DatalogW as the basis to give a uniform semantics to declarative RTW (Trust Management) language family, in order to represent trust levels based on c-semirings. In this way it is possible to manage a score corresponding to a preference or cost associated to the revealed credentials, instead of a plain “yes or no” authorization result. Clearly, such a solution is more informative and allows us to treat uncertainty of facts and rules application, or different preferencesfor the entity roles. Trust can be then derived by choosing the best chain. The approach is rather generic and could be applied to other trust management languages.

@conference{
	11391_161118,
	author = {Bistarelli, Stefano and Martinelli, Fabio and Santini, Francesco},
	title = {A Semantic Foundation for Trust Management Languages with Weights: An Application to the RT Family},
	year = {2008},
	publisher = {Springer},
	volume = {5060},
	booktitle = {Autonomic and Trusted Computing, 5th International Conference, ATC 2008},
	abstract = {We show that soft constraints can be used to model logical reasoning, that is deduction and abduction (and induction). In particular, we focus on the abduction process and we show how it can be implemented with a (soft) constraint removal operator. As a running application example throughout the paper, we reason with access control policies and credentials. In this way, we can associate the level of preference defined by the “softness” of the constraint with a “level” of trust. The main benefit comes during the process of automated access authorization based on trust: soft constraint operations can be easily adopted to measure the level of trust required for each operation. Moreover, when the level is not sufficient, abduction can be used to compute the missing credentials and the levels that grant the access, making the request a (weighted) logical consequence. The proposed framework can be used to automate the deduction-abduction negotiation processes.},
	doi = {10.1007/978-3-642-16576-4},	
	pages = {481--495}
}

We show that soft constraints can be used to model logical reasoning, that is deduction and abduction (and induction). In particular, we focus on the abduction process and we show how it can be implemented with a (soft) constraint removal operator. As a running application example throughout the paper, we reason with access control policies and credentials. In this way, we can associate the level of preference defined by the “softness” of the constraint with a “level” of trust. The main benefit comes during the process of automated access authorization based on trust: soft constraint operations can be easily adopted to measure the level of trust required for each operation. Moreover, when the level is not sufficient, abduction can be used to compute the missing credentials and the levels that grant the access, making the request a (weighted) logical consequence. The proposed framework can be used to automate the deduction-abduction negotiation processes.

@conference{
	11391_158727,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {A Formal and Practical Framework for Constraint-Based Routing},
	year = {2008},
	publisher = {IEEE Computer Society Press},
	booktitle = {Seventh International Conference on Networking (ICN 2008)},
	pages = {162--167}
}

@conference{
	11391_161112,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {Propagating multitrust within trust networks},
	year = {2008},
	publisher = {ACM Press},
	booktitle = {Proceedings of the 2008 ACM Symposium on Applied Computing (SAC)},
	abstract = {We suggest the concept of multitrust, which is aimed at computing trust by collectively involving a group of trustees at the same time: the trustor needs the concurrent support of multiple individuals to accomplish its task. We propose Soft Constraint Logic Programming based on semirings as a mean to quickly represent and evaluate trust propagation for this scenario. To attain this, we model the trust network adapting it to a weighted and-or graph, where the weight on a connector corresponds to the trust feedback value among the connected nodes. Semirings are the parametric and flexible structures used to appropriately represent trust metrics.},
	doi = {10.1145/1363686.1364170},	
	pages = {1990--1994}
}

We suggest the concept of multitrust, which is aimed at computing trust by collectively involving a group of trustees at the same time: the trustor needs the concurrent support of multiple individuals to accomplish its task. We propose Soft Constraint Logic Programming based on semirings as a mean to quickly represent and evaluate trust propagation for this scenario. To attain this, we model the trust network adapting it to a weighted and-or graph, where the weight on a connector corresponds to the trust feedback value among the connected nodes. Semirings are the parametric and flexible structures used to appropriately represent trust metrics.

@conference{
	11391_143644,
	author = {Bistarelli, Stefano and Gadducci, Fabio and Larrosa, Javier and Rollon, Emma},
	title = {A soft approach to multi-objective optimization},
	year = {2008},
	publisher = {Springer},
	volume = {5366},
	booktitle = {Logic Programming, 24th International Conference, ICLP 2008},
	abstract = {Logic Programming, 24th International Conference, ICLP 2008.
December 9-13 2008.
Udine, Italy.
Springer.
Lecture Notes in Computer Science.
ISBN: 9783540899815},
	pages = {764--768}
}

Logic Programming, 24th International Conference, ICLP 2008. December 9-13 2008. Udine, Italy. Springer. Lecture Notes in Computer Science. ISBN: 9783540899815

@article{
	11391_121113,
	author = {Bistarelli, Stefano and Francesco, Bonchi},
	title = {Soft Constraint Based Pattern Mining},
	year = {2007},
	journal = {DATA & KNOWLEDGE ENGINEERING},
	volume = {62},
	abstract = {The paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more efficient computation. So far the research on this paradigm has mainly focused on the latter aspect: the development of efficient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. In this paper, we analyze such limitations and we show how they flow out from the same source: the fact that in the classical constraint-based mining, a constraint is a rigid boolean function which returns either true or false. Indeed, interestingness is not a dichotomy. Following this consideration, we introduce the new paradigm of pattern discovery based on Soft Constraints, where constraints are no longer rigid boolean functions.

Albeit based on a simple idea, our proposal has many merits: it provides a rigorous theoretical framework, which is very general (having the classical paradigm as a particular instance), and which overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery.},
	keywords = {Frequent pattern mining, Constraint-based mining, Soft constraints, Semiring-based constraints},
	doi = {10.1016/j.datak.2006.07.008},	
	pages = {118--137}
}

The paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more efficient computation. So far the research on this paradigm has mainly focused on the latter aspect: the development of efficient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. In this paper, we analyze such limitations and we show how they flow out from the same source: the fact that in the classical constraint-based mining, a constraint is a rigid boolean function which returns either true or false. Indeed, interestingness is not a dichotomy. Following this consideration, we introduce the new paradigm of pattern discovery based on Soft Constraints, where constraints are no longer rigid boolean functions. Albeit based on a simple idea, our proposal has many merits: it provides a rigorous theoretical framework, which is very general (having the classical paradigm as a particular instance), and which overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery.

@conference{
	11391_121116,
	author = {Bistarelli, Stefano and Montanari, Ugo and Rossi, Francesca and Santini, Francesco},
	title = {Modelling Multicast Qos Routing by using Best-Tree Search in AND-OR Graphs and Soft Constraint Logic Programming},
	year = {2007},
	publisher = {ELSEVIER},
	journal = {ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE},
	volume = {190},
	booktitle = {Proceedings of the Fifth Workshop on Quantitative Aspects of Programming Languages (QAPL 2007)},
	abstract = {We suggest a formal model to represent and solve the multicast routing problem in multicast networks. To attain this, we model the network adapting it to a weighted and-or graph, where the weight on a connector corresponds to the cost of sending a packet on the network link modelled by that connector. Then, we use the Soft Constraint Logic Programming (SCLP) framework as a convenient declarative programming environment in which to specify related problems. In particular, we show how the semantics of an SCLP program computes the best tree in the corresponding and-or graph: this result can be adopted to find, from a given source node, the multicast distribution tree having minimum cost and reaching all the destination nodes of the multicast communication. The costs on the connectors can be described also as vectors (multi-dimensional costs), each component representing a different Quality of Service metric value. Therefore, the construction of the best tree may involve a set of criteria, all of which are to be optimized (multi-criteria problem), e.g. maximum global bandwidth and minimum delay that can be experienced on a single link.},
	keywords = {And-or Graphs; Multicast; Quality of Service; Routing; Soft Constraint Logic Programming},
	doi = {10.1016/j.entcs.2007.07.008},	
	pages = {111--127}
}

We suggest a formal model to represent and solve the multicast routing problem in multicast networks. To attain this, we model the network adapting it to a weighted and-or graph, where the weight on a connector corresponds to the cost of sending a packet on the network link modelled by that connector. Then, we use the Soft Constraint Logic Programming (SCLP) framework as a convenient declarative programming environment in which to specify related problems. In particular, we show how the semantics of an SCLP program computes the best tree in the corresponding and-or graph: this result can be adopted to find, from a given source node, the multicast distribution tree having minimum cost and reaching all the destination nodes of the multicast communication. The costs on the connectors can be described also as vectors (multi-dimensional costs), each component representing a different Quality of Service metric value. Therefore, the construction of the best tree may involve a set of criteria, all of which are to be optimized (multi-criteria problem), e.g. maximum global bandwidth and minimum delay that can be experienced on a single link.

@conference{
	11391_121115,
	author = {Bella, Giampaolo and Bistarelli, Stefano and Peretti, Pamela and Riccobene, Salvatore},
	title = {Augmented Risk Analysis},
	year = {2007},
	publisher = {ELSEVIER},
	journal = {ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE},
	volume = {168},
	booktitle = {Proceedings of Second International Workshop on Views on Designing Complex Architectures (VODCA 2006)},
	abstract = {Risk analysis has recently emerged as a structured and precise methodology to help modern companies understand their risks and plan the relative countermeasures well in advance. It is based on a number of indicators: parameters that quantify the key concepts on which an enterprise designs its security and safety investments. A modificator is a function that further modifies an existing indicator, and is itself an indicator. It is argued here that Risk Analysis can dramatically benefit from three novel modificators. One, the Exposure Factor during Critical Time (EFCT), expresses the percentage of loss or damage that an attack can infer to a time-critical asset. Another one, the Exposure Factor under Retaliation (EFR), formalises the mitigation to the loss or damage that an attack can infer to an asset when that loss or damage can be retaliated back onto the attacker. The third one, the Mitigated Risk against Collusion (MRC), formalises how a security measure can be effective against a single attacker but not necessarily against a large team of attackers working collaboratively for the same target. Our simulated results firmly support the benefits of such augmented Risk Analysis confirming the novel insights it can provide.},
	keywords = {exposure factor; mitigated risk; time-critical; retaliation; collusion},
	doi = {10.1016/j.entcs.2006.12.006},	
	pages = {207--220}
}

Risk analysis has recently emerged as a structured and precise methodology to help modern companies understand their risks and plan the relative countermeasures well in advance. It is based on a number of indicators: parameters that quantify the key concepts on which an enterprise designs its security and safety investments. A modificator is a function that further modifies an existing indicator, and is itself an indicator. It is argued here that Risk Analysis can dramatically benefit from three novel modificators. One, the Exposure Factor during Critical Time (EFCT), expresses the percentage of loss or damage that an attack can infer to a time-critical asset. Another one, the Exposure Factor under Retaliation (EFR), formalises the mitigation to the loss or damage that an attack can infer to an asset when that loss or damage can be retaliated back onto the attacker. The third one, the Mitigated Risk against Collusion (MRC), formalises how a security measure can be effective against a single attacker but not necessarily against a large team of attackers working collaboratively for the same target. Our simulated results firmly support the benefits of such augmented Risk Analysis confirming the novel insights it can provide.

@misc{
	11391_146833,
	author = {Bistarelli, Stefano and Monfroy, Eric and O'Sullivan, Barry},
	title = {Proceedings of the 2007 ACM Symposium on Applied Computing - Constraint solving and programming track},
	year = {2007},
	publisher = {ACM Press},
	abstract = {atti di convegno}
}

atti di convegno

@conference{
	11391_143590,
	author = {Bistarelli, Stefano and Peretti, Pamela and Trubitsyna, Irina},
	title = {Answer Set Optimization for and/or Composition of CP-Nets: A Security Scenario},
	year = {2007},
	publisher = {Springer},
	volume = {4741},
	booktitle = {CP 2007, 13th International Conference, CP 2007},
	pages = {773--781}
}

@conference{
	11391_144358,
	author = {Bistarelli, Stefano and Pini, MARIA SILVIA and Rossi, Francesca and Venable, KRISTEN BRENT},
	title = {Bipolar preference problems: framework, properties and solving techniques},
	year = {2007},
	publisher = {Springer},
	volume = {4651},
	booktitle = {Recent Advances in Constraints, ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP'06, Selected Papers},
	abstract = {Recent Advances in Constraints, ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP'06, Selected Papers.
LNCS.
ISBN: 9783540738169},
	pages = {78--92}
}

Recent Advances in Constraints, ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP'06, Selected Papers. LNCS. ISBN: 9783540738169

@conference{
	11391_144362,
	author = {Servin, Christian and Ceberio, Martine and Freudenthal, Eric and Bistarelli, Stefano},
	title = {An Optimization Approach using Soft Constraints for the Cascade Vulnerability Problem},
	year = {2007},
	publisher = {IEEE},
	booktitle = {Annual Meeting of the North American Fuzzy Information Processing Society, 2007. NAFIPS '07.},
	pages = {372--377}
}

@conference{
	11391_142856,
	author = {Bistarelli, Stefano and Fioravanti, Fabio and Peretti, Pamela},
	title = {Using CP-nets as a guide for countermeasure selection},
	year = {2007},
	publisher = {ACM Press},
	booktitle = {22nd ACM Symposium on Applied Computing (SAC2007)},
	pages = {300--304}
}

@conference{
	11391_143591,
	author = {Bistarelli, Stefano and Pini, MARIA SILVIA and Rossi, Francesca and Venable, KRISTEN BRENT},
	title = {Uncertainty in Bipolar Preference Problems},
	year = {2007},
	publisher = {Springer},
	volume = {4741},
	booktitle = {Principles and Practice of Constraint Programming - CP 2007},
	abstract = {Principles and Practice of Constraint Programming - CP 2007.
Springer.
Lecture Notes in Computer Science.
ISBN: 9783540749691},
	pages = {782--789}
}

Principles and Practice of Constraint Programming - CP 2007. Springer. Lecture Notes in Computer Science. ISBN: 9783540749691

@conference{
	11391_143636,
	author = {Smith, BARBARA M. and Bistarelli, Stefano and O'Sullivan, Barry},
	title = {Constraint Symmetry for the Soft CSP},
	year = {2007},
	publisher = {Springer},
	volume = {4741},
	booktitle = {Principles and Practice of Constraint Programming - CP 2007},
	pages = {872--879}
}

@article{
	11391_120852,
	author = {Bistarelli, Stefano and Montanari, Ugo and Rossi, Francesca},
	title = {Soft Concurrent Constraint Programming},
	year = {2006},
	journal = {ACM TRANSACTIONS ON COMPUTATIONAL LOGIC},
	volume = {7},
	abstract = {Soft constraints extend classical constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many soft constraint solving formalisms, even distributed ones, as yet there seems to be no concurrent programming framework where soft constraints can be handled. In this article we show how the classical concurrent constraint (cc) programming framework can work with soft constraints, and we also propose an extension of cc languages which can use soft constraints to prune and direct the search for a solution. We believe that this new programming paradigm, called soft cc (scc), can be also very useful in many Web-related scenarios. In fact, the language level allows Web agents to express their interaction and negotiation protocols, and also to post their requests in terms of preferences, and the underlying soft constraint solver can find an agreement among the agents even if their requests are incompatible.},
	keywords = {Languages, Constraints, Soft constraints, Concurrent constraint programming},
	doi = {10.1145/1149114.1149118},	
	pages = {563--589}
}

Soft constraints extend classical constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many soft constraint solving formalisms, even distributed ones, as yet there seems to be no concurrent programming framework where soft constraints can be handled. In this article we show how the classical concurrent constraint (cc) programming framework can work with soft constraints, and we also propose an extension of cc languages which can use soft constraints to prune and direct the search for a solution. We believe that this new programming paradigm, called soft cc (scc), can be also very useful in many Web-related scenarios. In fact, the language level allows Web agents to express their interaction and negotiation protocols, and also to post their requests in terms of preferences, and the underlying soft constraint solver can find an agreement among the agents even if their requests are incompatible.

@conference{
	11391_120854,
	author = {Bella, Giampaolo and Bistarelli, Stefano and Foley, SIMON N.},
	title = {Soft Constraints for Security},
	year = {2006},
	publisher = {ELSEVIER},
	journal = {ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE},
	volume = {142},
	booktitle = {Special Issue VODCA},
	abstract = {Integrity policies and cryptographic protocols have much in common. They allow for a number of participating principals, and consist of sets of rules controlling the actions that principals should or should not perform. They are intended to uphold various security properties, the crucial ones being integrity, confidentiality and authentication.

This paper takes a unified view to the analysis of integrity policies and cryptographic protocols: they are artifacts that must be designed to be sufficiently robust to attack given an understood threat model. For example, integrity policy rules provide resilience to the threat of internal fraud, while cryptographic protocols provide resilience to the threat of replay and related attacks. The framework is modelled using (soft) constraints and analysis corresponds to the soft constraint satisfaction problem. Soft constraints facilitate a quantitative approach to analyzing integrity, confidentiality and authentication. Examples will be given: an integrity policy may achieve different levels of integrity under different circumstances; a protocol message may enjoy different levels of confidentiality for different principals; a principal can achieve different levels of authentication with different principals.},
	keywords = {Constraints; Security Protocols; Integrity Policy},
	doi = {10.1016/j.entcs.2005.07.011},	
	pages = {11--29}
}

Integrity policies and cryptographic protocols have much in common. They allow for a number of participating principals, and consist of sets of rules controlling the actions that principals should or should not perform. They are intended to uphold various security properties, the crucial ones being integrity, confidentiality and authentication. This paper takes a unified view to the analysis of integrity policies and cryptographic protocols: they are artifacts that must be designed to be sufficiently robust to attack given an understood threat model. For example, integrity policy rules provide resilience to the threat of internal fraud, while cryptographic protocols provide resilience to the threat of replay and related attacks. The framework is modelled using (soft) constraints and analysis corresponds to the soft constraint satisfaction problem. Soft constraints facilitate a quantitative approach to analyzing integrity, confidentiality and authentication. Examples will be given: an integrity policy may achieve different levels of integrity under different circumstances; a protocol message may enjoy different levels of confidentiality for different principals; a principal can achieve different levels of authentication with different principals.

@article{
	11391_121112,
	author = {Bistarelli, Stefano and Santini, Francesco and Vaccarelli, Anna},
	title = {An asymmetric fingerprint matching algorithm for Java Card (TM)},
	year = {2006},
	journal = {PATTERN ANALYSIS AND APPLICATIONS},
	volume = {9},
	abstract = {We propose a light-weight fingerprint matching algorithm that can be executed inside the devices with a limited computational power. The algorithm is based on the minutiae local structures (the “neighborhoods”), that are invariant with respect to global transformations like translation and rotation. The match algorithm has been implemented inside a smartcard over the Java CardTM platform, meeting the individual’s need for information privacy and overall authentication procedure security. The main characteristic of the algorithm is to have an asymmetric behavior, in respect to the execution time, between correct positive and negative matches. The performances in terms of authentication reliability and speed were tested on some databases from the Fingerprint Verification Competition 2002 and 2004 editions (FVC2002 and FVC2004). Moreover, our procedure showed better reliability when compared with a related algorithm on the same database. We can achieve a false acceptance rate (FAR) of 0.1%, a false rejection rate of about 6%, and from 0.3 to 8 s to match most of the finger pairs during the FAR tests.},
	keywords = {Biometrics, Fingerprint matching, Smartcard, Match on Card, Java Card},
	doi = {10.1007/s10044-006-0048-4},	
	pages = {359--376}
}

We propose a light-weight fingerprint matching algorithm that can be executed inside the devices with a limited computational power. The algorithm is based on the minutiae local structures (the “neighborhoods”), that are invariant with respect to global transformations like translation and rotation. The match algorithm has been implemented inside a smartcard over the Java CardTM platform, meeting the individual’s need for information privacy and overall authentication procedure security. The main characteristic of the algorithm is to have an asymmetric behavior, in respect to the execution time, between correct positive and negative matches. The performances in terms of authentication reliability and speed were tested on some databases from the Fingerprint Verification Competition 2002 and 2004 editions (FVC2002 and FVC2004). Moreover, our procedure showed better reliability when compared with a related algorithm on the same database. We can achieve a false acceptance rate (FAR) of 0.1%, a false rejection rate of about 6%, and from 0.3 to 8 s to match most of the finger pairs during the FAR tests.

@conference{
	11391_144359,
	author = {Foley, SIMON N. and Fitzgerald, William and Bistarelli, Stefano and O'Sullivan, Barry and O FOGHLU, Micheal},
	title = {Principles of Secure Network Configuration: Towards a Formal Basis for Self-Configuration},
	year = {2006},
	publisher = {SPRINGER-VERLAG},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {4268},
	booktitle = {AUTONOMIC PRINCIPLES OF IP OPERATIONS AND MANAGEMENT, PROCEEDINGS},
	abstract = {The challenge for autonomic network management is the provision of future network management systems that have the characteristics of self-management, self-configuration, self-protection and self-healing, in accordance with the high level objectives of the enterprise or human end-user. This paper proposes an abstract model for network configuration that is intended to help understand fundamental underlying issues in self-configuration. We describe the cascade problem in self-configuring networks: when individual network components that are securely configured are connected together (in an apparently secure manner), a configuration cascade can occur resulting in a mis-configured network. This has implications for the design of self-configuring systems and we discuss how a soft constraint-based framework can provide a solution.},
	doi = {10.1007/11908852},	
	pages = {168--180}
}

The challenge for autonomic network management is the provision of future network management systems that have the characteristics of self-management, self-configuration, self-protection and self-healing, in accordance with the high level objectives of the enterprise or human end-user. This paper proposes an abstract model for network configuration that is intended to help understand fundamental underlying issues in self-configuration. We describe the cascade problem in self-configuring networks: when individual network components that are securely configured are connected together (in an apparently secure manner), a configuration cascade can occur resulting in a mis-configured network. This has implications for the design of self-configuring systems and we discuss how a soft constraint-based framework can provide a solution.

@conference{
	11391_144312,
	author = {Bistarelli, Stefano and Fioravanti, Fabio and Peretti, Pamela},
	title = {Defense trees for economic evaluation of security investments},
	year = {2006},
	publisher = {IEEE Computer Society},
	booktitle = {Proceedings of the The First International Conference on Availability, Reliability and Security, ARES 2006, The International Dependability Conference - Bridging Theory and Practice},
	doi = {10.1109/ARES.2006.46},	
	pages = {416--423}
}

@conference{
	11391_144356,
	author = {Bistarelli, Stefano and Pini, MARIA SILVIA and Rossi, Francesca and Venable, K. BRENT},
	title = {Bipolar preference problems},
	year = {2006},
	publisher = {IOS Press},
	volume = {141},
	booktitle = {ECAI 2006, 17th European Conference on Artificial Intelligence},
	abstract = {Frontiers in Artificial Intelligence and Applications},
	pages = {705--706}
}

Frontiers in Artificial Intelligence and Applications

@conference{
	11391_144360,
	author = {Bistarelli, Stefano and Peretti, Pamela and Dall'Aglio, Marco},
	title = {Strategic games on defense trees},
	year = {2006},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {4691},
	booktitle = {Formal Aspects in Security and Trust, Fourth International Workshop, FAST 2006.},
	pages = {1--15}
}

@misc{
	11391_146840,
	author = {Bistarelli, Stefano and Monfroy, Eric and O'Sullivan, Barry},
	title = {Proceedings of the 2006 ACM Symposium on Applied Computing - Constraint solving and programming track},
	year = {2006},
	publisher = {ACM Press},
	abstract = {atti di convegno}
}

atti di convegno

@misc{
	11391_146838,
	author = {Bistarelli, Stefano and Rossi, Francesca},
	title = {Special Issue: Preferences and Soft Constraints},
	year = {2006},
	publisher = {Springer},
	address = {DORDRECHT},
	journal = {JOURNAL OF HEURISTICS},
	volume = {12},
	doi = {10.1007/s10732-006-8247-0},	
	pages = {239--240}
}

@conference{
	11391_144355,
	author = {Bella, Giampaolo and Bistarelli, Stefano and Massacci, Fabio},
	title = {Retaliation: Can We Live with Flaws?},
	year = {2006},
	publisher = {IOS Press},
	address = {AMSTERDAM},
	volume = {6},
	booktitle = {INFORMATION ASSURANCE AND COMPUTER SECURITY},
	abstract = {NATO Security through Science Series},
	pages = {3--14}
}

NATO Security through Science Series

@conference{
	11391_144357,
	author = {Bistarelli, Stefano and Gadducci, Fabio},
	title = {Enhancing constraints manipulation in semiring-based formalisms},
	year = {2006},
	publisher = {IOS Press},
	volume = {141},
	booktitle = {ECAI 2006, 17th European Conference on Artificial Intelligence},
	abstract = {Frontiers in Artificial Intelligence and Applications},
	pages = {63--67}
}

Frontiers in Artificial Intelligence and Applications

@conference{
	11391_144361,
	author = {Bistarelli, Stefano and Bonchi, Francesco},
	title = {Extending the Soft Constraint Based Mining Paradigm},
	year = {2006},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {4747},
	booktitle = {Knowledge Discovery in Inductive Databases, 5th International Workshop, KDID 2006},
	pages = {24--41}
}

@article{
	11391_120851,
	author = {Bistarelli, Stefano and Cervesato, Iliano and Lenzini, Gabriele and Martinelli, Fabio},
	title = {Relating Multiset Rewriting and Process Algebras for Security Protocol Analysis},
	year = {2005},
	journal = {JOURNAL OF COMPUTER SECURITY},
	volume = {13},
	abstract = {When formalizing security protocols, different specification languages support very different reasoning methodologies, whose results are not directly or easily comparable. Therefore, establishing clear mappings among different frameworks is highly desirable, as it permits various methodologies to cooperate by interpreting theoretical and practical results of one system into another. In this paper, we examine the relationship between two general verification frameworks: multiset rewriting (MSR) and a process algebra (PA) inspired to CCS and the π-calculus. Although defining a simple and general bijection between MSR and PA appears difficult, we show that the sublanguages needed to specify cryptographic protocols admit an effective translation that is not only trace-preserving, but also induces a correspondence relation between the two languages. In particular, the correspondence sketched in this paper permits transferring several important trace-based properties such as secrecy and many forms of authentication.},
	pages = {3--47}
}

When formalizing security protocols, different specification languages support very different reasoning methodologies, whose results are not directly or easily comparable. Therefore, establishing clear mappings among different frameworks is highly desirable, as it permits various methodologies to cooperate by interpreting theoretical and practical results of one system into another. In this paper, we examine the relationship between two general verification frameworks: multiset rewriting (MSR) and a process algebra (PA) inspired to CCS and the π-calculus. Although defining a simple and general bijection between MSR and PA appears difficult, we show that the sublanguages needed to specify cryptographic protocols admit an effective translation that is not only trace-preserving, but also induces a correspondence relation between the two languages. In particular, the correspondence sketched in this paper permits transferring several important trace-based properties such as secrecy and many forms of authentication.

@article{
	11391_120853,
	author = {Giampaolo, Bella and Bistarelli, Stefano},
	title = {Information Assurance for Security Protocols},
	year = {2005},
	journal = {COMPUTERS & SECURITY},
	volume = {24},
	abstract = {Security protocols are used pervasively to protect distributed communications in the third Millennium. This motivates the need for a definition of Information Assurance for security protocols, which, to the best of our knowledge, is still missing. Such a definition is advanced in terms of the requirements that security protocols be analysed at the same time realistically, accurately and formally, notions that the existing literature only favours in separate contexts. The precise meanings of these terms are described by means of general considerations and concrete examples. The main goal of this paper is to draw attention to and raise concern on this novel but significant niche of computer security.},
	keywords = {Formal analysis,Constraint solving, Soft constraints, Cryptographic protocol, Realism, Accuracy, Formalism, Retaliation},
	doi = {10.1016/j.cose.2004.10.004},	
	pages = {322--333}
}

Security protocols are used pervasively to protect distributed communications in the third Millennium. This motivates the need for a definition of Information Assurance for security protocols, which, to the best of our knowledge, is still missing. Such a definition is advanced in terms of the requirements that security protocols be analysed at the same time realistically, accurately and formally, notions that the existing literature only favours in separate contexts. The precise meanings of these terms are described by means of general considerations and concrete examples. The main goal of this paper is to draw attention to and raise concern on this novel but significant niche of computer security.

@article{
	11391_121114,
	author = {Bistarelli, Stefano and Foley, SIMON N. and O'Sullivan, Barry},
	title = {A soft constraint-based approach to the cascade vulnerability problem},
	year = {2005},
	journal = {JOURNAL OF COMPUTER SECURITY},
	volume = {13},
	abstract = {The security of a network configuration is based not just on the security of its individual components and their direct interconnections, but also on the potential for systems to interoperate indirectly across network routes. Such interoperation has been shown to provide the potential for cascading paths that violate security, in a circuitous manner, across a network. In this paper we show how constraint satisfaction provides a natural approach to expressing the necessary constraints to ensure multilevel security across a network configuration. In particular, soft constraints are used to detect and eliminate the cascading network paths that compromise security. Taking this approach results in practical advancements over existing solutions to this problem. In particular, constraint satisfaction highlights the set of all cascading paths, which we can eliminate in polynomial time by breaking a minimal number of system links to ensure security.},
	pages = {699--720}
}

The security of a network configuration is based not just on the security of its individual components and their direct interconnections, but also on the potential for systems to interoperate indirectly across network routes. Such interoperation has been shown to provide the potential for cascading paths that violate security, in a circuitous manner, across a network. In this paper we show how constraint satisfaction provides a natural approach to expressing the necessary constraints to ensure multilevel security across a network configuration. In particular, soft constraints are used to detect and eliminate the cascading network paths that compromise security. Taking this approach results in practical advancements over existing solutions to this problem. In particular, constraint satisfaction highlights the set of all cascading paths, which we can eliminate in polynomial time by breaking a minimal number of system links to ensure security.

@conference{
	11391_142855,
	author = {Bistarelli, Stefano and Foley, SIMON N. and Barry, Osullivan},
	title = {Reasoning about Secure Interoperation using Soft Constraints},
	year = {2005},
	publisher = {Springer},
	volume = {173},
	booktitle = {Formal Aspects in Security and Trust},
	abstract = {The security of a network configuration is based not just on the security of its individual components and their direct interconnections, but also on the potential for systems to interoperate indirectly across network routes. Such interoperation has been shown to provide the potential for circuitous paths across a network that violate security. In this paper we propose a constraint-based framework for representing access control configurations of systems. The secure reconfiguration of a system is depicted as a constraint satisfaction problem.},
	doi = {10.1007/0-387-24098-5_13},	
	pages = {173--186}
}

The security of a network configuration is based not just on the security of its individual components and their direct interconnections, but also on the potential for systems to interoperate indirectly across network routes. Such interoperation has been shown to provide the potential for circuitous paths across a network that violate security. In this paper we propose a constraint-based framework for representing access control configurations of systems. The secure reconfiguration of a system is depicted as a constraint satisfaction problem.

@conference{
	11391_143202,
	author = {Bella, Giampaolo and Bistarelli, Stefano},
	title = {A protocol's life after attacks...},
	year = {2005},
	publisher = {SPRINGER-VERLAG},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {3364},
	booktitle = {SECURITY PROTOCOLS},
	abstract = {In the analysis of security protocols, it is customary to stop as soon as we find an attack. Tons of ink can be spilled on whether an "attack" is really an attack, but it goes without saying that there is no life after that, hence no interest in continuing the analysis. If the protocol is broken, then we ought to fix it. 

Yet, fixing things is expensive and other measures may be more effective. In the physical world, most ATM safes would not resist heavy shelling with anti-tank bazookas, but banks don't worry about that. The attack will be noisy enough that cops will come within seconds from its start. To secure ourselves, we rely on a mixture of measures including the protection from attacks but also countermeasures after detection. 

In the light of these considerations, the following question becomes of interest: what can happen after an attack? Does the villain leave enough traces that we can retaliate it on-the-fly? Or, if we can't or won't, does a subsequent forensic analysis allow us to discover who did it (and send the cops behind him)? If even this is impossible, can we discover that we have been hacked by looking at the logs? 

To address these issues, we introduce the notions of retaliation, detection, and suspicion, which can be applied after an attack. These properties introduce more sophisticated formal relations between traces of actions, which go beyond the simple existentials that formal methods have made us used to. 

These concepts should allow for a more comprehensive evaluation of security protocols. A protocol may well be vulnerable to an attack, but if we can retaliate afterwards, maybe fixing it isn't that necessary: the concrete possibilities of retaliation or detection may be enough to convince potential hackers to refrain from mounting the attack.},
	keywords = {SECURITY PROPERTIES; Authentication},
	doi = {10.1007/11542322_2},	
	pages = {3--10}
}

In the analysis of security protocols, it is customary to stop as soon as we find an attack. Tons of ink can be spilled on whether an "attack" is really an attack, but it goes without saying that there is no life after that, hence no interest in continuing the analysis. If the protocol is broken, then we ought to fix it. Yet, fixing things is expensive and other measures may be more effective. In the physical world, most ATM safes would not resist heavy shelling with anti-tank bazookas, but banks don't worry about that. The attack will be noisy enough that cops will come within seconds from its start. To secure ourselves, we rely on a mixture of measures including the protection from attacks but also countermeasures after detection. In the light of these considerations, the following question becomes of interest: what can happen after an attack? Does the villain leave enough traces that we can retaliate it on-the-fly? Or, if we can't or won't, does a subsequent forensic analysis allow us to discover who did it (and send the cops behind him)? If even this is impossible, can we discover that we have been hacked by looking at the logs? To address these issues, we introduce the notions of retaliation, detection, and suspicion, which can be applied after an attack. These properties introduce more sophisticated formal relations between traces of actions, which go beyond the simple existentials that formal methods have made us used to. These concepts should allow for a more comprehensive evaluation of security protocols. A protocol may well be vulnerable to an attack, but if we can retaliate afterwards, maybe fixing it isn't that necessary: the concrete possibilities of retaliation or detection may be enough to convince potential hackers to refrain from mounting the attack.

@misc{
	11391_146890,
	author = {Bistarelli, Stefano and Monfroy, Eric and O'Sullivan, Barry},
	title = {Proceedings of the 2005 ACM Symposium on Applied Computing - Constraint solving and programming track},
	year = {2005},
	publisher = {ACM Press},
	abstract = {atti di convegno}
}

atti di convegno

@conference{
	11391_142857,
	author = {Bistarelli, Stefano and Frassi, Stefano and Vaccarelli, Anna},
	title = {MOC via TOC Using a Mobile Agent Framework},
	year = {2005},
	publisher = {SPRINGER-VERLAG},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {3546},
	booktitle = {AUDIO AND VIDEO BASED BIOMETRIC PERSON AUTHENTICATION, PROCEEDINGS},
	abstract = {A novel protocol is proposed to address the problem of user authentication to smartcards using biometric authentication instead of the usual PIN. The protocol emulates expensive Match On Card (MOC) smartcards, which can compute a biometric match onboard, by using cheap Template on Card (TOC) smartcards, which only store a biometric template. The biometric match is performed by a module running on the user's workstation, authenticated by a mobile agent coming from a reliable server. The protocol uses today's cryptographic tokens without requiring any HW/SW modifications.},
	doi = {10.1007/11527923_48},	
	pages = {464--473}
}

A novel protocol is proposed to address the problem of user authentication to smartcards using biometric authentication instead of the usual PIN. The protocol emulates expensive Match On Card (MOC) smartcards, which can compute a biometric match onboard, by using cheap Template on Card (TOC) smartcards, which only store a biometric template. The biometric match is performed by a module running on the user's workstation, authenticated by a mobile agent coming from a reliable server. The protocol uses today's cryptographic tokens without requiring any HW/SW modifications.

@conference{
	11391_143201,
	author = {Bella, Giampaolo and Bistarelli, Stefano and Martinelli, Fabio},
	title = {Biometrics to Enhance Smartcard Security},
	year = {2005},
	publisher = {SPRINGER-VERLAG},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {3364},
	booktitle = {SECURITY PROTOCOLS},
	abstract = {A novel protocol is proposed to address the problem of user authentication to smartcards by means of devices that are currently inexpensive. The protocol emulates expensive Match On Card (MOC) smartcards, which can compute a biometric match, by cheap Template on Card (TOC) smartcards, which only store a biometric template. The actual match is delegated to an extension of the cryptographic module running on the card host, which is called Cryptoki according to the PKCS#11[9] standard. Compliance to such a standard increases the portability of the protocol. Informal reasoning confirms the protocol strenghts, though its formal verification in terms of established equational techniques appears to be at hand.},
	doi = {10.1007/11542322_39},	
	pages = {324--335}
}

A novel protocol is proposed to address the problem of user authentication to smartcards by means of devices that are currently inexpensive. The protocol emulates expensive Match On Card (MOC) smartcards, which can compute a biometric match, by cheap Template on Card (TOC) smartcards, which only store a biometric template. The actual match is delegated to an extension of the cryptographic module running on the card host, which is called Cryptoki according to the PKCS#11[9] standard. Compliance to such a standard increases the portability of the protocol. Informal reasoning confirms the protocol strenghts, though its formal verification in terms of established equational techniques appears to be at hand.

@conference{
	11391_161115,
	author = {Bistarelli, Stefano and Santini, Francesco and Vaccarelli, Anna},
	title = {An Asymmetric Fingerprint Matching Algorithm for Java Card},
	year = {2005},
	publisher = {SPRINGER-VERLAG},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {3546},
	booktitle = {AUDIO AND VIDEO BASED BIOMETRIC PERSON AUTHENTICATION, PROCEEDINGS},
	abstract = {A novel fingerprint matching algorithm is proposed in this paper. The algorithm is based on the minutiae local structures, that are invariant with respect to global transformations like translation and rotation. The match algorithm has been implemented inside a smartcard over the Java Card (TM) platform, meeting the individual's need for information privacy and the overall authentication procedure security. The main characteristic of the algorithm is to have an asymmetric behaviour, in respect to the execution time, between correct positive and negative matches. The performances in terms of authentication reliability and speed have been tested on some databases from the Fingerprint Verification Competition 2002 (FVC2002). Moreover, our procedure has shown better reliability results when compared with related Java Card (TM) algorithms.},
	doi = {10.1007/11527923_29},	
	pages = {279--288}
}

A novel fingerprint matching algorithm is proposed in this paper. The algorithm is based on the minutiae local structures, that are invariant with respect to global transformations like translation and rotation. The match algorithm has been implemented inside a smartcard over the Java Card (TM) platform, meeting the individual's need for information privacy and the overall authentication procedure security. The main characteristic of the algorithm is to have an asymmetric behaviour, in respect to the execution time, between correct positive and negative matches. The performances in terms of authentication reliability and speed have been tested on some databases from the Fingerprint Verification Competition 2002 (FVC2002). Moreover, our procedure has shown better reliability results when compared with related Java Card (TM) algorithms.

@conference{
	11391_144310,
	author = {Bistarelli, Stefano and Bonchi, Francesco},
	title = {Interestingness is not a Dichotomy: Introducing Softness in Constrained Pattern Mining},
	year = {2005},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {3721},
	booktitle = {KNOWLEDGE DISCOVERY IN DATABASES: PKDD 2005},
	abstract = {The paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more efficient computation. So far the research on this paradigm has mainly focussed on the latter aspect: the development of efficient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. As a solution, in this paper we introduce the new paradigm of pattern discovery based on Soft Constraints. Albeit simple, the proposed paradigm overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery.},
	doi = {10.1007/11564126_8},	
	pages = {22--33}
}

The paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more efficient computation. So far the research on this paradigm has mainly focussed on the latter aspect: the development of efficient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. As a solution, in this paper we introduce the new paradigm of pattern discovery based on Soft Constraints. Albeit simple, the proposed paradigm overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery.

@conference{
	11391_144311,
	author = {Foley, SIMON N. and Bistarelli, Stefano and Barry, O'Sullivan and John, Herbert and Garret, Swart},
	title = {Multilevel Security and Quality of Protection},
	year = {2005},
	publisher = {Springer},
	volume = {23},
	booktitle = {Quality Of Protection, Security Measurements and Metrics},
	doi = {10.1007/978-0-387-36584-8_8},	
	pages = {93--105}
}

@article{
	11391_120850,
	author = {Bella, Giampaolo and Bistarelli, Stefano},
	title = {Soft Constraint Programming to Analysing Security Protocol},
	year = {2004},
	journal = {THEORY AND PRACTICE OF LOGIC PROGRAMMING},
	volume = {4},
	abstract = {Security protocols stipulate how the remote principals of a computer network should interact in order to obtain specific security goals. The crucial goals of confidentiality and authentication may be achieved in various forms, each of different strength. Using soft (rather than crisp) constraints, we develop a uniform formal notion for the two goals. They are no longer formalised as mere yes/no properties as in the existing literature, but gain an extra parameter, the security level. For example, different messages can enjoy different levels of confidentiality, or a principal can achieve different levels of authentication with different principals. The goals are formalised within a general framework for protocol analysis that is amenable to mechanisation by model checking. Following the application of the framework to analysing the asymmetric Needham-Schroeder protocol (Bella and Bistarelli 2001; Bella and Bistarelli 2002), we have recently discovered a new attack on that protocol as a form of retaliation by principals who have been attacked previously. Having commented on that attack, we then demonstrate the framework on a bigger, largely deployed protocol consisting of three phases, Kerberos.},
	keywords = {security, constraints, Security Protocols, soft constraints,CRYPTOGRAPHIC PROTOCOLS, INFORMATION-FLOW, SECRECY},
	doi = {10.1017/S1471068404002121},	
	pages = {545--572}
}

Security protocols stipulate how the remote principals of a computer network should interact in order to obtain specific security goals. The crucial goals of confidentiality and authentication may be achieved in various forms, each of different strength. Using soft (rather than crisp) constraints, we develop a uniform formal notion for the two goals. They are no longer formalised as mere yes/no properties as in the existing literature, but gain an extra parameter, the security level. For example, different messages can enjoy different levels of confidentiality, or a principal can achieve different levels of authentication with different principals. The goals are formalised within a general framework for protocol analysis that is amenable to mechanisation by model checking. Following the application of the framework to analysing the asymmetric Needham-Schroeder protocol (Bella and Bistarelli 2001; Bella and Bistarelli 2002), we have recently discovered a new attack on that protocol as a form of retaliation by principals who have been attacked previously. Having commented on that attack, we then demonstrate the framework on a bigger, largely deployed protocol consisting of three phases, Kerberos.

@article{
	11391_120849,
	author = {Bistarelli, Stefano and Fruewirth, Thom and Marte, Michael and Rossi, Francesca},
	title = {Soft Constraint Propagation and Solving in Constraint Handling Rules},
	year = {2004},
	journal = {COMPUTATIONAL INTELLIGENCE},
	volume = {20},
	abstract = {Soft constraints are a generalization of classical constraints, which allow for the description of preferences rather than strict requirements. In soft constraints, constraints and partial assignments are given preference or importance levels, and constraints are combined according to combinators which express the desired optimization criteria. On the other hand, constraint handling rules (CHR) constitute a high-level natural formalism to specify constraint solvers and propagation algorithms. We present a framework to design and specify soft constraint solvers by using CHR. In this way, we extend the range of applicability of CHR to soft constraints rather than just classical ones, and we provide a straightforward implementation for soft constraint solvers.},
	keywords = {Constraint solving, constraint propagation, soft constraints, constraint languages},
	doi = {10.1111/j.0824-7935.2004.00239.x},	
	pages = {287--307}
}

Soft constraints are a generalization of classical constraints, which allow for the description of preferences rather than strict requirements. In soft constraints, constraints and partial assignments are given preference or importance levels, and constraints are combined according to combinators which express the desired optimization criteria. On the other hand, constraint handling rules (CHR) constitute a high-level natural formalism to specify constraint solvers and propagation algorithms. We present a framework to design and specify soft constraint solvers by using CHR. In this way, we extend the range of applicability of CHR to soft constraints rather than just classical ones, and we provide a straightforward implementation for soft constraint solvers.

@conference{
	11391_142851,
	author = {Bistarelli, Stefano and Foley, SIMON N. and O'Sullivan, Barry},
	title = {Modelling and Detecting the Cascade Vulnerabiliy Problem using Soft Constraints},
	year = {2004},
	publisher = {ACM Press},
	booktitle = {Proceedings of the 2004 ACM Symposium on Applied Computing (SAC)},
	doi = {10.1145/967900.967984},	
	pages = {383--390}
}

@conference{
	11391_142914,
	author = {Bistarelli, Stefano and Jerome, Keleher and Barry, O'Sullivan},
	title = {Symmetry Breaking in Soft CSPs},
	year = {2004},
	publisher = {Springer-Verlag},
	volume = {20},
	booktitle = {Research and Development in Intelligent Systems XX: AI 2003},
	abstract = {Exploiting symmetry in constraint satisfaction problems has become a very popular topic of research in recent times. The existence of symmetry in a problem has the effect of artificially increasing the size of the search space that is explored by search algorithms. Another significant topic of research has been approaches to reasoning about preferences. As constraint processing applications are becoming more widespread in areas such as electronic commerce, configuration, etc., it is becoming increasingly important that we can reason about preferences as efficiently as possible. We present an approach to dealing with symmetry in the semi-ring framework for soft constraints. We demonstrate that breaking symmetries in soft constraint satisfaction problems improves the efficiency of search. The paper contributes to the state-of-the-art in symmetry breaking, as well as in reasoning about preferences.},
	pages = {199--212}
}

Exploiting symmetry in constraint satisfaction problems has become a very popular topic of research in recent times. The existence of symmetry in a problem has the effect of artificially increasing the size of the search space that is explored by search algorithms. Another significant topic of research has been approaches to reasoning about preferences. As constraint processing applications are becoming more widespread in areas such as electronic commerce, configuration, etc., it is becoming increasingly important that we can reason about preferences as efficiently as possible. We present an approach to dealing with symmetry in the semi-ring framework for soft constraints. We demonstrate that breaking symmetries in soft constraint satisfaction problems improves the efficiency of search. The paper contributes to the state-of-the-art in symmetry breaking, as well as in reasoning about preferences.

@conference{
	11391_143139,
	author = {Bistarelli, Stefano and Rossi, Francesca and Pilan, Isabella},
	title = {Abstracting Soft Constraints: Some experimental results on Fuzzy CSPs},
	year = {2004},
	publisher = {SPRINGER-VERLAG},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {3010},
	booktitle = {RECENT ADVANCES IN CONSTRAINTS},
	abstract = {Soft constraints are very flexible and expressive. However, they may also be very complex to handle. For this reason, it may be convenient in several cases to pass to an abstract version of a given soft problem, and then 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 review the main concepts and properties of our abstraction framework for soft constraints, and we show some experimental results of its application to the solution of fuzzy constraints.},
	doi = {10.1007/978-3-540-24662-6_6},	
	pages = {107--123}
}

Soft constraints are very flexible and expressive. However, they may also be very complex to handle. For this reason, it may be convenient in several cases to pass to an abstract version of a given soft problem, and then 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 review the main concepts and properties of our abstraction framework for soft constraints, and we show some experimental results of its application to the solution of fuzzy constraints.

@conference{
	11391_142686,
	author = {Bella, Giampaolo and Bistarelli, Stefano},
	title = {Confidentiality levels and deliberate/indeliberate protocol attacks},
	year = {2004},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {2845},
	booktitle = {Security Protocols, 10th International Workshop, Revised Papers},
	abstract = {A formal definition of confidentiality is developed using soft (rather than crisp) constraints. The goal is no longer considered as a mere yes/no property as in the existing literature, but gains an extra parameter, the security level. The higher the security level, the stronger the goal. For example, different messages may enjoy different levels of confidentiality, and the same message may enjoy different levels of confidentiality for different principals. On this basis, the notion of indeliberate confidentiality attack can be captured, whereby a principal learns some message not meant for him because of someone else's tampering. The analysis of Lowe's attack on the Needham-Schroeder protocol reveals a new weakness.},
	doi = {10.1007/978-3-540-39871-4_10},	
	pages = {104--119}
}

A formal definition of confidentiality is developed using soft (rather than crisp) constraints. The goal is no longer considered as a mere yes/no property as in the existing literature, but gains an extra parameter, the security level. The higher the security level, the stronger the goal. For example, different messages may enjoy different levels of confidentiality, and the same message may enjoy different levels of confidentiality for different principals. On this basis, the notion of indeliberate confidentiality attack can be captured, whereby a principal learns some message not meant for him because of someone else's tampering. The analysis of Lowe's attack on the Needham-Schroeder protocol reveals a new weakness.

@conference{
	11391_142853,
	author = {Bella, Giampaolo and Bistarelli, Stefano},
	title = {Advancing Assurance for Secure Distributed Communications},
	year = {2004},
	publisher = {IEEE Computer Society},
	booktitle = {Information Assurance Workshop, 2004. Proceedings from the Fifth Annual IEEE SMC},
	doi = {10.1109/IAW.2004.1437832},	
	pages = {306--313}
}

@conference{
	11391_143138,
	author = {Bistarelli, Stefano and Kelleher, Jerome and O'Sullivan, Barry},
	title = {Tradeoff Generation using Soft Constraints},
	year = {2004},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {3010},
	booktitle = {RECENT ADVANCES IN CONSTRAINTS},
	abstract = {Tradeoffs have been proposed in the literature as an approach to resolving over-constrainedness in interactive constraint-based tools, such as product configurators. It has been reported how tradeoffs can be modeled as additional constraints. This paper presents a formal framework for tradeoff generation based on the semiring approach to soft constraints. In particular, user preferences and tradeoffs are, respectively, represented as soft constraints and as an entailment operator. The entailment operator is used to interactively generate new constraints representing tradeoffs. The framework we present is well-motivated by real-world approaches that exploit tradeoff generation in online buying and configuration processes.},
	doi = {10.1007/978-3-540-24662-6_7},	
	pages = {124--139}
}

Tradeoffs have been proposed in the literature as an approach to resolving over-constrainedness in interactive constraint-based tools, such as product configurators. It has been reported how tradeoffs can be modeled as additional constraints. This paper presents a formal framework for tradeoff generation based on the semiring approach to soft constraints. In particular, user preferences and tradeoffs are, respectively, represented as soft constraints and as an entailment operator. The entailment operator is used to interactively generate new constraints representing tradeoffs. The framework we present is well-motivated by real-world approaches that exploit tradeoff generation in online buying and configuration processes.

@conference{
	11391_142854,
	author = {Bistarelli, Stefano and Freuder, EUGENE C. and Osullivan, Barry},
	title = {Encoding Partial Constraint Satisfaction in the Semiring-Based Framework for Soft Constraints},
	year = {2004},
	publisher = {iEEE Computer Society},
	booktitle = {Tools with Artificial Intelligence, 2004. ICTAI 2004. 16th IEEE International Conference on},
	doi = {10.1109/ICTAI.2004.58},	
	pages = {240--245}
}

@conference{
	11391_143136,
	author = {Bistarelli, Stefano and Barry, O'Sullivan},
	title = {A Theoretical Framework for Tradeoff Generation using Soft Constraints},
	year = {2004},
	publisher = {SPRINGER-VERLAG LONDON LTD, SWEETAPPLE HOUSE CATTESHALL RD FARNCOMBE, GODALMING GU7 1NH, SURREY, ENGLAND},
	volume = {XX},
	booktitle = {Research and Development in Intelligent Systems},
	abstract = {Tradeoffs have been proposed in the literature as an approach to resolving over-constrainedness in interactive constraint-based tools, such as product configurators, that reason about user preferences. It has been reported how tradeoffs can be modeled as additional constraints. This paper presents a formal framework for tradeoff generation based on the semiring approach to soft constraints. In particular, user preferences and tradeoffs are represented as soft constraints and as an entailment operator, respectively. The entailment operator is used to interactively generate new constraints representing tradeoffs. We also introduce a novel definition of substitutability for soft constraints upon which we present a relaxed definition of tradeoffs.},
	pages = {69--82}
}

Tradeoffs have been proposed in the literature as an approach to resolving over-constrainedness in interactive constraint-based tools, such as product configurators, that reason about user preferences. It has been reported how tradeoffs can be modeled as additional constraints. This paper presents a formal framework for tradeoff generation based on the semiring approach to soft constraints. In particular, user preferences and tradeoffs are represented as soft constraints and as an entailment operator, respectively. The entailment operator is used to interactively generate new constraints representing tradeoffs. We also introduce a novel definition of substitutability for soft constraints upon which we present a relaxed definition of tradeoffs.

@misc{
	11391_146889,
	author = {Hung, C. C. and Bistarelli, Stefano and Rosa, Agostinho},
	title = {Proceedings of the 2004 ACM Symposium on Applied Computing - AI and computational logic and image analysis (AI)},
	year = {2004},
	publisher = {ACM Press}
}

@book{
	11391_133486,
	author = {Bistarelli, Stefano},
	title = {Semirings for Soft Constraint Solving and Programming},
	year = {2004},
	publisher = {SPRINGER-VERLAG},
	address = {BERLIN},
	volume = {2962},
	abstract = {The Soft Constraints idea is able to capture many real-life situations that cannot be represented and solved with the classical crisp constraint framework. In this book we first describe a general framework for representing many soft constraint systems, and then we investigate the related theoretic and application- oriented issues.
Our framework is based on a semiring structure, where the carrier of the semiring specifies the values to be associated with each tuple of values of the variable domain, and the two semiring operations, + and ×, model constraint projection and combination, respectively. The semiring carrier and operations can be instantiated in order to capture all the non-crisp constraints representing fuzziness, optimization, probability, hierarchies, and others. The solution of each instance of the soft Constraint Satisfaction Problem (CSP) is computed by using the appropriate × and + semiring operation.
This uniform representation can be used to give sufficient conditions for the correctness and applicability of local consistency and dynamic programming al- gorithms. In particular:
– We show that using an idempotent × operator the classical local consis- tency (and also dynamic programming) techniques can be used to reduce the complexity of the problem without modifying its solution.
– We adapt to the soft framework partial local consistency and labeling tech- niques, which require fewer pruning steps of the domain. This means that, although they are able to remove fewer non-optimal solutions than classi- cal algorithms can, partial local consistency algorithms can be beneficial because they are faster and easier implemented.
– We extend general local consistency algorithms that use several pruning rules until the fix-point is reached.
Solving a soft CSP is generally harder than solving the corresponding crisp CSP. For this reason we introduce an abstraction/concretization mapping over soft CSPs in order to solve a problem in an easier environment and then use the abstract results to speed up the search of solutions in the concrete one. Several mappings between existing soft frameworks are given. These mappings will es- pecially be useful for applying soft local consistency techniques in a safe, easy, and faster way. Also useful, when looking for optimal solutions, are the notions of substitutability and interchangeability. In crisp CSPs they have been used as a basis for search heuristics, solution adaptation, and abstraction techniques.
The next part of the book involves some programming features: as classical constraint solving can be embedded into Constraint Logic Programming (CLP) systems, so too can our more general notion of constraint solving be handled within a logic language, thus giving rise to new instances of the CLP scheme. This not only gives new meanings to constraint solving in CLP, but it also allows one to treat in a uniform way optimization problem solving within CLP, without the need to resort to ad hoc methods. In fact, we show that it is possible to generalize the semantics of CLP programs to consider the chosen semiring and thus solve problems according to the semiring operations. This is done by associating each ground atom with an element of the semiring and by using the two semiring operations to combine goals. This allows us to perform in the same language both constraint solving and optimization. We then provide this class of languages with three equivalent semantics, model-theoretic, fix-point, and proof- theoretic, in the style of CLP programs. The language is then used to show how the soft CLP semantics can solve shortest-path problems. In a way similar to the soft CLP language we also extend the semantics of the Concurrent Constraints (cc) language. The extended cc language uses soft constraints to prune and direct the search for a solution.
The last part of the book aims to describe how soft constraints can be used to solve some security-related problems. In the framework, the crucial goals of confidentiality and authentication can be achieved with different levels of secu- rity. In fact, different messages can enjoy different levels of confidentiality, or a principal can achieve different levels of authentication with different principals.},
	keywords = {soft constraints},
	doi = {10.1007/b95712},	
	pages = {1--279}
}

The Soft Constraints idea is able to capture many real-life situations that cannot be represented and solved with the classical crisp constraint framework. In this book we first describe a general framework for representing many soft constraint systems, and then we investigate the related theoretic and application- oriented issues. Our framework is based on a semiring structure, where the carrier of the semiring specifies the values to be associated with each tuple of values of the variable domain, and the two semiring operations, + and ×, model constraint projection and combination, respectively. The semiring carrier and operations can be instantiated in order to capture all the non-crisp constraints representing fuzziness, optimization, probability, hierarchies, and others. The solution of each instance of the soft Constraint Satisfaction Problem (CSP) is computed by using the appropriate × and + semiring operation. This uniform representation can be used to give sufficient conditions for the correctness and applicability of local consistency and dynamic programming al- gorithms. In particular: – We show that using an idempotent × operator the classical local consis- tency (and also dynamic programming) techniques can be used to reduce the complexity of the problem without modifying its solution. – We adapt to the soft framework partial local consistency and labeling tech- niques, which require fewer pruning steps of the domain. This means that, although they are able to remove fewer non-optimal solutions than classi- cal algorithms can, partial local consistency algorithms can be beneficial because they are faster and easier implemented. – We extend general local consistency algorithms that use several pruning rules until the fix-point is reached. Solving a soft CSP is generally harder than solving the corresponding crisp CSP. For this reason we introduce an abstraction/concretization mapping over soft CSPs in order to solve a problem in an easier environment and then use the abstract results to speed up the search of solutions in the concrete one. Several mappings between existing soft frameworks are given. These mappings will es- pecially be useful for applying soft local consistency techniques in a safe, easy, and faster way. Also useful, when looking for optimal solutions, are the notions of substitutability and interchangeability. In crisp CSPs they have been used as a basis for search heuristics, solution adaptation, and abstraction techniques. The next part of the book involves some programming features: as classical constraint solving can be embedded into Constraint Logic Programming (CLP) systems, so too can our more general notion of constraint solving be handled within a logic language, thus giving rise to new instances of the CLP scheme. This not only gives new meanings to constraint solving in CLP, but it also allows one to treat in a uniform way optimization problem solving within CLP, without the need to resort to ad hoc methods. In fact, we show that it is possible to generalize the semantics of CLP programs to consider the chosen semiring and thus solve problems according to the semiring operations. This is done by associating each ground atom with an element of the semiring and by using the two semiring operations to combine goals. This allows us to perform in the same language both constraint solving and optimization. We then provide this class of languages with three equivalent semantics, model-theoretic, fix-point, and proof- theoretic, in the style of CLP programs. The language is then used to show how the soft CLP semantics can solve shortest-path problems. In a way similar to the soft CLP language we also extend the semantics of the Concurrent Constraints (cc) language. The extended cc language uses soft constraints to prune and direct the search for a solution. The last part of the book aims to describe how soft constraints can be used to solve some security-related problems. In the framework, the crucial goals of confidentiality and authentication can be achieved with different levels of secu- rity. In fact, different messages can enjoy different levels of confidentiality, or a principal can achieve different levels of authentication with different principals.

@conference{
	11391_142852,
	author = {Bistarelli, Stefano and Foley, SIMON N. and O'Sullivan, Barry},
	title = {Detecting and Eliminating the Cascade Vulnerability Problem from Multi-level Security Networks using Soft Constraints},
	year = {2004},
	publisher = {AAAI Pres / The MIT Press},
	booktitle = {Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence},
	pages = {808--813}
}

@conference{
	11391_143137,
	author = {Bistarelli, Stefano and Neagu, Nicoleta and Faltings, Boi},
	title = {Experimental Evaluation of Interchangeability in Soft CSPs},
	year = {2004},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {3010},
	booktitle = {Recent Advances in Constraints, Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2003},
	abstract = {In [8], Freuder defined interchangeability for classical Constraint Satisfaction Problems (CSPs). Recently [2], we extended the definition of interchangeability to Soft CSPs and we introduced two notions of relaxation based on degradation delta and on threshold alpha ((delta)neighborhood interchangeability ((NI)-N-delta)and (alpha)neighborhood interchangeability (alphaNI)). In this paper we extend the study introduced in [11] and we analyze the presence of the relaxed version of interchangeability in random soft CSPs. We give a short description of the implementation we used to compute interchangeabilities and to make the tests. The experiments show that there is high occurrence of alphaNI and (NI)-N-delta interchangeability around optimal solution in fuzzy CSPs and weighted CSPs. Thus, these algorithms can be used successfully in solution update applications. Moreover, it is also showed that NI interchangeability can well approximate full interchangeability (FI).},
	doi = {10.1007/978-3-540-24662-6_8},	
	pages = {140--153}
}

In [8], Freuder defined interchangeability for classical Constraint Satisfaction Problems (CSPs). Recently [2], we extended the definition of interchangeability to Soft CSPs and we introduced two notions of relaxation based on degradation delta and on threshold alpha ((delta)neighborhood interchangeability ((NI)-N-delta)and (alpha)neighborhood interchangeability (alphaNI)). In this paper we extend the study introduced in [11] and we analyze the presence of the relaxed version of interchangeability in random soft CSPs. We give a short description of the implementation we used to compute interchangeabilities and to make the tests. The experiments show that there is high occurrence of alphaNI and (NI)-N-delta interchangeability around optimal solution in fuzzy CSPs and weighted CSPs. Thus, these algorithms can be used successfully in solution update applications. Moreover, it is also showed that NI interchangeability can well approximate full interchangeability (FI).

@article{
	11391_120848,
	author = {Bistarelli, Stefano and Gennari, Rossella and Rossi, Francesca},
	title = {General Properties and Termination Conditions for Soft Constraint Propagation},
	year = {2003},
	journal = {CONSTRAINTS},
	volume = {8},
	abstract = {Soft constraints based on semirings are a generalization of classical constraints, where tuples of variables' values in each soft constraint are associated to elements from an algebraic structure called semiring. This framework is able to express, for example, fuzzy, classical, weighted, valued and over-constrained constraint problems. 
Classical constraint propagation has been extended and adapted to soft constraints by defining a schema for soft constraint propagation [8]. On the other hand, in [1-3] it has been proven that most of the well known constraint propagation algorithms for classical constraints can be cast within a single schema. 
In this paper we combine these two schemas and we provide a more general framework where the schema of [3] can be used for soft constraints. In doing so, we generalize the concept of soft constraint propagation, and we provide new sufficient and independent conditions for its termination.},
	keywords = {soft constraints, soft constraint propagation, termination, semiring, generic algorithm schema},
	doi = {10.1023/A:1021950728713},	
	pages = {79--97}
}

Soft constraints based on semirings are a generalization of classical constraints, where tuples of variables' values in each soft constraint are associated to elements from an algebraic structure called semiring. This framework is able to express, for example, fuzzy, classical, weighted, valued and over-constrained constraint problems. Classical constraint propagation has been extended and adapted to soft constraints by defining a schema for soft constraint propagation [8]. On the other hand, in [1-3] it has been proven that most of the well known constraint propagation algorithms for classical constraints can be cast within a single schema. In this paper we combine these two schemas and we provide a more general framework where the schema of [3] can be used for soft constraints. In doing so, we generalize the concept of soft constraint propagation, and we provide new sufficient and independent conditions for its termination.

@conference{
	11391_142688,
	author = {Bistarelli, Stefano and Faltings, Boi and Neagu, Nicoleta},
	title = {Interchangeability in Soft CSPs},
	year = {2003},
	publisher = {SPRINGER-VERLAG},
	journal = {LECTURE NOTES IN ARTIFICIAL INTELLIGENCE},
	volume = {2627},
	booktitle = {RECENT ADVANCES IN CONSTRAINTS},
	abstract = {Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). 

We introduce two notions: threshold a and degradation delta for substitutability and interchangeability, ((alpha)substitutability/interchangeability and (delta)substitutability/interchangeability respectively). We show that they satisfy analogous theorems to the ones already known for hard constraints. In interchangeability, values are interchangeable in any solution that is better than a threshold alpha, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In (delta)interchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of delta. 

We give efficient algorithms to compute (delta/alpha) interchangeable sets of values for a large class of SCSPs.},
	keywords = {CONSTRAINT SATISFACTION},
	doi = {10.1007/3-540-36607-5_3},	
	pages = {31--46}
}

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce two notions: threshold a and degradation delta for substitutability and interchangeability, ((alpha)substitutability/interchangeability and (delta)substitutability/interchangeability respectively). We show that they satisfy analogous theorems to the ones already known for hard constraints. In interchangeability, values are interchangeable in any solution that is better than a threshold alpha, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In (delta)interchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of delta. We give efficient algorithms to compute (delta/alpha) interchangeable sets of values for a large class of SCSPs.

@conference{
	11391_142910,
	author = {Fabio, Martinelli and Bistarelli, Stefano and Iliano, Cervesato and Gabriele, Lenzini and Roberto, Marangoni},
	title = {On representing biological systems through multiset rewriting},
	year = {2003},
	publisher = {Springer},
	volume = {2809},
	booktitle = {COMPUTER AIDED SYSTEMS THEORY - EUROCAST 2003},
	abstract = {We model qualitative and quantitative aspects of metabolic pathways by using a stochastic version of Multiset Rewriting (SMSR). They offer a natural way of describing both the static and the dynamic aspects of metabolic pathways. We argue that, due to its simple conceptual model, SMSR may be conveniently used as an intermediate language where many higher level specification languages may be compiled (e.g., as in the security protocol example). As a first step, we show also how SMSR may be used to simulate Stochastic Petri Nets for describing metabolic pathways.},
	doi = {10.1007/978-3-540-45210-2_38},	
	pages = {415--426}
}

We model qualitative and quantitative aspects of metabolic pathways by using a stochastic version of Multiset Rewriting (SMSR). They offer a natural way of describing both the static and the dynamic aspects of metabolic pathways. We argue that, due to its simple conceptual model, SMSR may be conveniently used as an intermediate language where many higher level specification languages may be compiled (e.g., as in the security protocol example). As a first step, we show also how SMSR may be used to simulate Stochastic Petri Nets for describing metabolic pathways.

@conference{
	11391_142909,
	author = {Bistarelli, Stefano and Philippe, Codognet and KIN CHUEN, Hui and JIMMY HO MAN, Lee},
	title = {Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search},
	year = {2003},
	publisher = {Morgan Kaufmann},
	booktitle = {IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence},
	pages = {1364--1365}
}

@conference{
	11391_142913,
	author = {Bistarelli, Stefano and Codognet, Philippe and Hui, KIN CHUEN and Lee, JIMMY HO-MAN},
	title = {Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search},
	year = {2003},
	publisher = {springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {2833},
	booktitle = {Principles and Practice of Constraint Programming - CP 2003, 9th International Conference, CP 2003},
	abstract = {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.},
	doi = {10.1007/978-3-540-45193-8_10},	
	pages = {138--152}
}

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.

@conference{
	11391_142912,
	author = {Bistarelli, Stefano and Cervesato, Iliano and Lenzini, Gabriele and Martinelli, Fabio},
	title = {Relating Process Algebras and Multiset Rewriting for Immediate Decryption Protocols},
	year = {2003},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {2776},
	booktitle = {COMPUTER NETWORK SECURITY},
	abstract = {When formalizing security protocols, different specification languages support very different reasoning methodologies, whose results are not directly or easily comparable. Therefore, establishing clear mappings among different frameworks is highly desirable, as it permits various methodologies to cooperate by interpreting theoretical and practical results of one system in another. In this paper, we examine the nontrivial relationship between two general verification frameworks: multiset rewriting (MSR) and a process algebra (PA) inspired to CCS and the pi-calculus. Although defining a simple and general bijection between MSR and PA appears difficult, we show that the sublanguages needed to specify a large class of cryptographic protocols (immediate decryption protocols) admits an effective translation that is not only bijective and trace-preserving, but also induces a weak form of bisimulation across the two languages. In particular, the correspondence sketched in this abstract permits transferring several important trace-based properties such as secrecy and many forms of authentication.},
	doi = {10.1007/978-3-540-45215-7_7},	
	pages = {88--101}
}

When formalizing security protocols, different specification languages support very different reasoning methodologies, whose results are not directly or easily comparable. Therefore, establishing clear mappings among different frameworks is highly desirable, as it permits various methodologies to cooperate by interpreting theoretical and practical results of one system in another. In this paper, we examine the nontrivial relationship between two general verification frameworks: multiset rewriting (MSR) and a process algebra (PA) inspired to CCS and the pi-calculus. Although defining a simple and general bijection between MSR and PA appears difficult, we show that the sublanguages needed to specify a large class of cryptographic protocols (immediate decryption protocols) admits an effective translation that is not only bijective and trace-preserving, but also induces a weak form of bisimulation across the two languages. In particular, the correspondence sketched in this abstract permits transferring several important trace-based properties such as secrecy and many forms of authentication.

@conference{
	11391_143200,
	author = {Bistarelli, Stefano and Foley, SIMON N.},
	title = {Analysis of Integrity Policies using Soft Constraints},
	year = {2003},
	publisher = {IEEE Computer Society},
	booktitle = {4th IEEE International Workshop on Policies for Distributed Systems and Networks (POLICY 2003)},
	doi = {10.1109/POLICY.2003.1206959},	
	pages = {77--80}
}

@conference{
	11391_142911,
	author = {Bistarelli, Stefano and Foley, SIMON N.},
	title = {A constraint framework for the qualitative analysis of dependability goals: Integrity},
	year = {2003},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {2788},
	booktitle = {Computer Safety, Reliability, and Security, 22nd International Conference, SAFECOMP 2003},
	abstract = {An integrity policy defines the situations when modification of information is authorized and is enforced by the security mechanisms of the system. However, in a complex application system it is possible that an integrity policy may have been incorrectly specified and, as a result, a user may be authorized to modify information that can lead to an unexpected system compromise. In this paper we propose a scalable and quantitative technique that uses constraint solving to model and analyze the effectiveness of application system integrity policies.},
	doi = {10.1007/978-3-540-39878-3_11},	
	pages = {130--143}
}

An integrity policy defines the situations when modification of information is authorized and is enforced by the security mechanisms of the system. However, in a complex application system it is possible that an integrity policy may have been incorrectly specified and, as a result, a user may be authorized to modify information that can lead to an unexpected system compromise. In this paper we propose a scalable and quantitative technique that uses constraint solving to model and analyze the effectiveness of application system integrity policies.

@conference{
	11391_143199,
	author = {Bistarelli, Stefano and Boffi, Giandomenico and Rossi, Fabio},
	title = {Computer Algebra for Fingerprint Matching},
	year = {2003},
	publisher = {Springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {2657},
	booktitle = {COMPUTATIONAL SCIENCE - ICCS 2003, PT I, PROCEEDINGS},
	abstract = {We show in this paper how some algebraic methods can be used for fingerprint matching. The described technique is able to compute the score of a match also when the template and test fingerprints have been not correctly acquired. In particular, the match is independent of translations, rotations and scaling transformations of the template. The technique is also able to compute a match score when part of the fingerprint image is incorrect or missed. The algorithm is being implemented in CoCoA, a computer algebra system for doing computations in Commutative Algebra.},
	doi = {10.1007/3-540-44860-8_84},	
	pages = {811--820}
}

We show in this paper how some algebraic methods can be used for fingerprint matching. The described technique is able to compute the score of a match also when the template and test fingerprints have been not correctly acquired. In particular, the match is independent of translations, rotations and scaling transformations of the template. The technique is also able to compute a match score when part of the fingerprint image is incorrect or missed. The algorithm is being implemented in CoCoA, a computer algebra system for doing computations in Commutative Algebra.

@conference{
	11391_1357744,
	author = {Neagu, Nicoleta and Bistarelli, Stefano and Faltings, Boi},
	title = {On the Computation of Local Interchangeability in Soft Constraint Satisfaction Problems},
	year = {2003},
	publisher = {AAAI Press},
	booktitle = {PROCEEDINGS OF THE SIXTEENTH INTERNATIONAL FLORIDA ARTIFICIAL INTELLIGENCE RESEARCH SOCIETY CONFERENCE},
	url = {https://www.aaai.org/Papers/FLAIRS/2003/Flairs03-037.pdf},
	pages = {187--191}
}

@misc{
	prev-187557,
	title = {Editorial message: Special track on Artificial Intelligence and Computational Logic},
	year = {2003},
	booktitle = {Proceedings of the ACM Symposium on Applied Computing},
	keywords = {Computer Science (all)}
}

@article{
	11391_120847,
	author = {Bistarelli, Stefano and Philippe, Codognet and Francesca, Rossi},
	title = {Abstracting soft constraints: Framework, properties, examples},
	year = {2002},
	journal = {ARTIFICIAL INTELLIGENCE},
	volume = {139},
	abstract = {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.},
	keywords = {Abstraction, Constraint propagation, Constraint solving, Fuzzy reasoning, Soft constraints},
	doi = {10.1016/S0004-3702(02)00208-4},	
	pages = {175--211}
}

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.

@article{
	11391_120846,
	author = {Bistarelli, Stefano and Ugo, Montanari and Francesca, Rossi},
	title = {Soft Constraint logic Programming and Generalized Shortest Path Problems},
	year = {2002},
	journal = {JOURNAL OF HEURISTICS},
	volume = {8},
	abstract = {In this paper we study the relationship between Constraint Programming (CP) and Shortest Path (SP) problems. In particular, we show that classical, multicriteria, partially ordered, and modality-based SP problems can be naturally modeled and solved within the Soft Constraint Logic Programming (SCLP) framework, where logic programming is coupled with soft constraints. In this way we provide this large class of SP problems with a high-level and declarative linguistic support whose semantics takes care of both finding the cost of the shortest path(s) and also of actually finding the path(s). On the other hand, some efficient algorithms for certain classes of SP problems can be exploited to provide some classes of SCLP programs with an efficient way to compute their semantics.},
	keywords = {shortest path problems, soft constraints, Constraint Logic Programming},
	doi = {10.1023/A:1013609600697},	
	pages = {25--41}
}

In this paper we study the relationship between Constraint Programming (CP) and Shortest Path (SP) problems. In particular, we show that classical, multicriteria, partially ordered, and modality-based SP problems can be naturally modeled and solved within the Soft Constraint Logic Programming (SCLP) framework, where logic programming is coupled with soft constraints. In this way we provide this large class of SP problems with a high-level and declarative linguistic support whose semantics takes care of both finding the cost of the shortest path(s) and also of actually finding the path(s). On the other hand, some efficient algorithms for certain classes of SP problems can be exploited to provide some classes of SCLP programs with an efficient way to compute their semantics.

@conference{
	11391_142684,
	author = {Bistarelli, Stefano and Fruewirth, Thom and Marte, Michael and Rossi, Francesca},
	title = {Soft Constraint Propagation and Solving in CHR},
	year = {2002},
	publisher = {ACM Press},
	booktitle = {Proceedings of the 2002 ACM Symposium on Applied Computing (SAC)},
	abstract = {Soft constraints are a generalization of classical constraints,
where constraints and/or partial assignments are associated
to preference or importance levels, and constraints are combined
according to combinators which express the desired
optimization criteria. Constraint Handling Rules (CHRs)
constitute a high-level natural formalism to specify constraint
solvers and propagation algorithms. In this paper
we present a framework to design and specify soft constraint
solvers by using CHRs. In this way, we extend the range of
applicability of CHRs to soft constraints rather than just
classical ones, and we provide a straightforward implementation
for soft constraint solvers.},
	pages = {1--5}
}

Soft constraints are a generalization of classical constraints, where constraints and/or partial assignments are associated to preference or importance levels, and constraints are combined according to combinators which express the desired optimization criteria. Constraint Handling Rules (CHRs) constitute a high-level natural formalism to specify constraint solvers and propagation algorithms. In this paper we present a framework to design and specify soft constraint solvers by using CHRs. In this way, we extend the range of applicability of CHRs to soft constraints rather than just classical ones, and we provide a straightforward implementation for soft constraint solvers.

@misc{
	11391_146888,
	author = {Hung, CHIH-CHENG and Rosa, Agostinho and Bistarelli, Stefano},
	title = {Proceedings of the 2012 ACM Symposium on Applied Computing - A.I. and computational logic track},
	year = {2002},
	publisher = {ACM Press}
}

@conference{
	11391_142685,
	author = {Bistarelli, Stefano and Montanari, Ugo and Rossi, Francesca},
	title = {Soft Concurrent Constraint Programming},
	year = {2002},
	publisher = {springer},
	journal = {LECTURE NOTES IN COMPUTER SCIENCE},
	volume = {2305},
	booktitle = {PROGRAMMING LANGUAGES AND SYSTEMS, PROCEEDINGS},
	abstract = {Soft constraints extend classical constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many soft constraint solving algorithms, even distributed ones, by now there seems to be no concurrent programming framework where soft constraints can be handled. In this paper we show how the classical concurrent constraint (cc) programming framework can work with soft constraints, and we also propose an extension of cc languages which can use soft constraints to prune and direct the search for a solution. We believe that this new programming paradigm, called soft cc (scc), can be very useful in many web-related scenarios. In fact, the language level allows web agents to express their interaction and negotiation protocols, and also to post their requests in terms of preferences, and the underlying soft constraint solver can find an agreement among the agents even if their requests are incompatible.},
	doi = {10.1007/3-540-45927-8_5},	
	pages = {53--67}
}

Soft constraints extend classical constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many soft constraint solving algorithms, even distributed ones, by now there seems to be no concurrent programming framework where soft constraints can be handled. In this paper we show how the classical concurrent constraint (cc) programming framework can work with soft constraints, and we also propose an extension of cc languages which can use soft constraints to prune and direct the search for a solution. We believe that this new programming paradigm, called soft cc (scc), can be very useful in many web-related scenarios. In fact, the language level allows web agents to express their interaction and negotiation protocols, and also to post their requests in terms of preferences, and the underlying soft constraint solver can find an agreement among the agents even if their requests are incompatible.

@conference{
	11391_142687,
	author = {Bistarelli, Stefano and Faltings, Boi and Neagu, Nicoleta},
	title = {Interchangeability in Soft CSPs},
	year = {2002},
	publisher = {springer},
	volume = {2470},
	booktitle = {Principles and Practice of Constraint Programming - CP 2002, 8th International Conference, CP 2002},
	abstract = {Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs).
We introduce the notions of threshold α and degradation δ for substitutability and interchangeability. In αinterchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In δinterchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ.
Theorems, algorithms to compute (δ/α)interchangeable sets of values, and a more general treatment of all the ideas presented in this paper can be found in [2].},
	doi = {10.1007/3-540-46135-3_53},	
	pages = {726--731}
}

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce the notions of threshold α and degradation δ for substitutability and interchangeability. In αinterchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In δinterchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ. Theorems, algorithms to compute (δ/α)interchangeable sets of values, and a more general treatment of all the ideas presented in this paper can be found in [2].

@book{
	11391_1316703,
	author = {Bistarelli, Stefano},
	title = {Soft Constraint Solving and Programming: a general framework.},
	year = {2001},
	volume = {TD-2/01},
	url = {http://phd.di.unipi.it/Theses/PhDthesis_Bistarelli.pdf}
}

@article{
	11391_120845,
	author = {Bistarelli, Stefano and Ugo, Montanari and Francesca, Rossi},
	title = {Semiring-Based Constraint Logic Programming: Syntax and Semantics},
	year = {2001},
	journal = {ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS},
	volume = {23},
	abstract = {We extend the Constraint Logic Programming (CLP) formalism in order to handle semiring-based constraints. This allows us to perform in the same language both constraint solving and optimization. In fact, constraints based on semirings are able to model both classical constraint solving and more sophisticated features like uncertainty, probability, fuzziness, and optimization. We then provide this class of languages with three equivalent semantics: model-theoretic, fix-point, and proof-theoretic, in the style of classical CLP programs.},
	keywords = {language, theory, soft constraints, semantics},
	doi = {10.1145/383721.383725},	
	pages = {1--29}
}

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

@conference{
	11391_142683,
	author = {Giampaolo, Bella and Bistarelli, Stefano},
	title = {Soft Constraints for Security Protocol Analysis: Confidentiality},
	year = {2001},
	publisher = {Springer},
	volume = {1990},
	booktitle = {Practical Aspects of Declarative Languages, Third International Symposium, PADL 2001},
	abstract = {We model any network configuration arising from the execution of a security protocol as a soft constraint satisfaction problem (SCSP). We formalise the protocol goal of confidentiality as a property of the solution for an SCSP, hence confidentiality always holds with a certain security level. The policySCSP models the network configuration where all admissible protocol sessions have terminated successfully, and an imputable SCSP models a given network configuration. Comparing the solutions of these two problems elicits whether the given configuration hides a confidentiality attack. We can also compare attacks and decide which is the most significant. The approach is demonstrated on the asymmetric Needham-Schroeder protocol.},
	doi = {10.1007/3-540-45241-9_8},	
	pages = {108--122}
}

We model any network configuration arising from the execution of a security protocol as a soft constraint satisfaction problem (SCSP). We formalise the protocol goal of confidentiality as a property of the solution for an SCSP, hence confidentiality always holds with a certain security level. The policySCSP models the network configuration where all admissible protocol sessions have terminated successfully, and an imputable SCSP models a given network configuration. Comparing the solutions of these two problems elicits whether the given configuration hides a confidentiality attack. We can also compare attacks and decide which is the most significant. The approach is demonstrated on the asymmetric Needham-Schroeder protocol.

@conference{
	11391_142634,
	author = {Bistarelli, Stefano and Philippe, Codognet and Yan, Georget and Francesca, Rossi},
	title = {Labeling and Partial Local Consistency for Soft Constraint Programming},
	year = {2000},
	publisher = {SPRINGER-VERLAG},
	volume = {1753},
	booktitle = {PRACTICAL ASPECTS OF DECLARATIVE LANGUAGES},
	abstract = {In this paper we generalize to soft constraints the approximation techniques usually used for local consistency in classical constraint satisfaction and programming. The theoretical results show that this is indeed possible without loosing the fundamental properties of such techniques, and the experimental results ton partial are-consistency) show that this work can help develop more efficient implementations for logic-based languages working with soft constraints.},
	doi = {10.1007/3-540-46584-7_16},	
	pages = {230--248}
}

In this paper we generalize to soft constraints the approximation techniques usually used for local consistency in classical constraint satisfaction and programming. The theoretical results show that this is indeed possible without loosing the fundamental properties of such techniques, and the experimental results ton partial are-consistency) show that this work can help develop more efficient implementations for logic-based languages working with soft constraints.

@conference{
	11391_142636,
	author = {Bistarelli, Stefano and Gennari, Rosella and Rossi, Francesca},
	title = {Constraint Propagation for Soft Constraint Satisfaction Problems: Generalization and Termination Conditions},
	year = {2000},
	publisher = {Springer},
	volume = {1894},
	booktitle = {Principles and Practice of Constraint Programming - CP 2000: 6th International Conference},
	abstract = {Soft constraints based on semirings are a generalization of classical constraints, where tuples of variables’ values in each soft constraint are uniquely associated to elements from an algebraic structure called semiring. This framework is able to express, for example, fuzzy, classical, weighted, valued and over-constrained constraint problems. Classical constraint propagation has been extended and adapted to soft constraints by defining a schema for soft local consistency [BMR97]. On the other hand, in [Apt99a,Apt99b] it has been proved that most of the well known constraint propagation algorithms for classical constraints can be cast within a single schema.
In this paper we combine these two schema and we show how the framework of [Apt99a,Apt99b] can be used for soft constraints. In doing so, we generalize the concept of soft local consistency, and we prove some convenient properties about its termination.},
	doi = {10.1007/3-540-45349-0_8},	
	pages = {83--97}
}

Soft constraints based on semirings are a generalization of classical constraints, where tuples of variables’ values in each soft constraint are uniquely associated to elements from an algebraic structure called semiring. This framework is able to express, for example, fuzzy, classical, weighted, valued and over-constrained constraint problems. Classical constraint propagation has been extended and adapted to soft constraints by defining a schema for soft local consistency [BMR97]. On the other hand, in [Apt99a,Apt99b] it has been proved that most of the well known constraint propagation algorithms for classical constraints can be cast within a single schema. In this paper we combine these two schema and we show how the framework of [Apt99a,Apt99b] can be used for soft constraints. In doing so, we generalize the concept of soft local consistency, and we prove some convenient properties about its termination.

@conference{
	11391_142635,
	author = {Bistarelli, Stefano and Codognet, Philippe and Georget, Yan and Rossi, Francesca},
	title = {Abstracting Soft Constraints},
	year = {2000},
	publisher = {Springer},
	volume = {1865},
	booktitle = {New Trends in Contraints, Joint ERCIM/Compulog Net Workshop, Selected Papers},
	abstract = {We propose an abstraction scheme for soft constraint problems and we study its main properties. Processing the abstracted version of a soft constraint problem can help us in many ways: for example, to find good approximations of the optimal solutions, or also to provide us with information that can make the subsequent search for the best solution easier. The results of this paper show that the proposed scheme is promising; thus they can be used as a stable formal base for any experimental work specific to a particular class of soft constraint problems.},
	doi = {10.1007/3-540-44654-0_6},	
	pages = {108--133}
}

We propose an abstraction scheme for soft constraint problems and we study its main properties. Processing the abstracted version of a soft constraint problem can help us in many ways: for example, to find good approximations of the optimal solutions, or also to provide us with information that can make the subsequent search for the best solution easier. The results of this paper show that the proposed scheme is promising; thus they can be used as a stable formal base for any experimental work specific to a particular class of soft constraint problems.

@conference{
	11391_142682,
	author = {Bistarelli, Stefano and Codognet, Philippe and Rossi, Francesca},
	title = {An Abstraction Framework for Soft Constraint and Its Relationship with Constraint Propagation},
	year = {2000},
	publisher = {Springer},
	volume = {1864},
	booktitle = {Abstraction, Reformulation, and Approximation, 4th International Symposium, SARA 2000},
	abstract = {Soft constraints are very flexible and expressive. However, they also are very complex to handle. For this reason, it may reasonable in several cases to pass to an abstract version of a given soft 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 review the main concepts and properties of our abstraction framework for soft constraints, and we show how it can be used 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.},
	doi = {10.1007/3-540-44914-0_5},	
	pages = {71--86}
}

Soft constraints are very flexible and expressive. However, they also are very complex to handle. For this reason, it may reasonable in several cases to pass to an abstract version of a given soft 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 review the main concepts and properties of our abstraction framework for soft constraints, and we show how it can be used 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.

@article{
	11391_120844,
	author = {Bistarelli, Stefano and Ugo, Montanari and Francesca, Rossi and Thomas, Schiex and Gerard, Verfaillie and Helene, Fargier},
	title = {Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison},
	year = {1999},
	journal = {CONSTRAINTS},
	volume = {4},
	abstract = {In this paper we describe and compare two frameworks for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. One is based on a semiring, and the other one on a totally ordered commutative monoid. While comparing the two approaches, we show how to pass from one to the other one, and we discuss when this is possible. The two frameworks have been independently introduced in [2], [3] and [35].},
	keywords = {Branch and bound, Complexity, CONSTRAINT SATISFACTION, dynamic programming, optimization, Overconstrained problems, Soft Constraint},
	doi = {10.1023/A:1026441215081},	
	pages = {199--240}
}

In this paper we describe and compare two frameworks for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. One is based on a semiring, and the other one on a totally ordered commutative monoid. While comparing the two approaches, we show how to pass from one to the other one, and we discuss when this is possible. The two frameworks have been independently introduced in [2], [3] and [35].

@article{
	11391_120843,
	author = {Bistarelli, Stefano and Ugo, Montanari and Francesca, Rossi},
	title = {Semiring-based constraint satisfaction and optimization},
	year = {1997},
	journal = {JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY},
	volume = {44},
	abstract = {We introduce a general framework for constraint satisfaction and optimization 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 with 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 certain conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving and optimization. schemes, thus allowing one to both formally justify many informally taken choices in existing schemes, and to prove that local consistency techniques can be used also in newly defined schemes.},
	keywords = {constraint solving, dynamic programming, local consistency, non-crisp constraint reasoning},
	doi = {10.1145/256303.256306},	
	pages = {201--236}
}

We introduce a general framework for constraint satisfaction and optimization 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 with 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 certain conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving and optimization. schemes, thus allowing one to both formally justify many informally taken choices in existing schemes, and to prove that local consistency techniques can be used also in newly defined schemes.

@conference{
	11391_142633,
	author = {Bistarelli, Stefano and Montanari, Ugo and Rossi, Francesca},
	title = {Semiring-based Constraint Logic Programming},
	year = {1997},
	publisher = {IJCAI},
	booktitle = {15th International Joint Conference on Artificial Intelligence (IJCAI97),},
	pages = {352--357}
}

@inbook{
	11391_130105,
	author = {Bistarelli, Stefano and Fargier, Helene and Montanari, Ugo and Rossi, Francesca and Schiex, Thomas and Verfaillie, Gerard},
	title = {Semiring-based CSPs and Valued CSPs: Basic Properties and Comparison},
	year = {1996},
	publisher = {Springer},
	volume = {1106},
	booktitle = {Over-Constrained Systems},
	abstract = {Lecture Notes in Computer Science},
	pages = {111--150}
}

Lecture Notes in Computer Science

@conference{
	11391_142632,
	author = {Bistarelli, Stefano and Montanari, Ugo and Rossi, Francesca},
	title = {Constraint Solving over Semirings},
	year = {1995},
	publisher = {IJCAI},
	volume = {1},
	booktitle = {14th International Joint Conference on Artificial Intelligence (IJCAI95),},
	pages = {624--630}
}