Advanced search
Start date

PROVERBS -- PRobabilistic OVERconstrained Boolean Systems: reasoning tools and applications

Grant number: 15/21880-4
Support Opportunities:Regular Research Grants
Duration: April 01, 2016 - September 30, 2018
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Marcelo Finger
Grantee:Marcelo Finger
Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated researchers:Denis Deratani Mauá ; Fabio Gagliardi Cozman


Solving computational problems on real world objects means to bring together strict models of the universe of discourse, with less than perfect and flexible information one may gather about the world. This means that the solution method must be able to cope both with hard and well-defined statements on the world with other information whose nature is soft. The capability to deal with such a situation may enable us to deal with computer devices placed at a real world, with its often changing, imprecise and uncertain flow of information.This project studies problems that combine real-world hard constraints with soft constraints involving preferences, uncertainties and flexible requirements. In this work, the hard constraints are represented by sets of Boolean formulas. The soft constraints may take the form of weights of preference associated to some of the Boolean formulas, with the goal of maximizing the total weight of the satisfied soft constraints. This is the \emph{maximum satisfiability (MaxSAT)} approach to the problem of hard and soft constraints. Another way to model soft constraints is to associate probabilities to some of the formulas, in which case a solution is a probability distribution over the models that meet the hard constraints, that also verifies the soft probability constraints. This is the \emph{probabilistic satisfiability (PSAT)} approach to hard and soft constraints.In many situations, both modelling techniques of hard and soft Boolean constraints lead to \emph{overconstrained} formulations, that is, a set of constraints for which no consistent interpretation is possible. Important applications modelled by overconstrained hard-soft problems are found in several areas, among which the following will be explored in this project: Security, protocol verification and planning, and computational linguistics.However, the nature of these constraints place us in the middle of the \emph{intractable} computational class known as NP-hard, for which no efficient general algorithm is know, but for which many simpler instances have been discovered in the recent years. We believe that a cross fertilization between these two approaches can lead to significant progress in dealing with hard-soft constraints. By combining the expertise of top-tier researchers in both approaches, this project aims at leading the technique and applications of the area to a different level.We plan to develop several algorithms to deal with MaxSAT and PSAT problems, including the solution of PSAT using MaxSAT. We then plan to apply those techniques to the solution of overconstrained problems. Programs will be made available as free and open-source software. Applications of these techniques and algorithms will cover the areas of information security, protocol verification and computational linguistics.This project is the Brazilian side of a collaboration between research groups based at two universities in Portugal and Brazil that aim at studying these methods and exploring approaches for the problem of dealing with probabilistic over constrained problems. (AU)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications (5)
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
COZMAN, FABIO GAGLIARDI. Evenly convex credal sets. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 103, p. 124-138, . (16/18841-0, 15/21880-4)
DE FARIA, FRANCISCO H. O. VIEIRA; GUSMAO, ARTHUR COLOMBINI; DE BONA, GLAUBER; MAUA, DENIS DERATANI; COZMAN, FABIO GAGLIARDI. Speeding up parameter and rule learning for acyclic probabilistic logic programs. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 106, p. 32-50, . (17/19007-6, 16/18841-0, 16/25928-4, 16/01055-1, 15/21880-4)
COZMAN, FABIO GAGLIARDI; MAUA, DENIS DERATANI. The finite model theory of Bayesian network specifications: Descriptive complexity and zero/one laws. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 110, n. SI, p. 107-126, . (16/18841-0, 15/21880-4)
MAUA, DENIS DERATANI; COZMAN, FABIO GAGLIARDI. Complexity results for probabilistic answer set programming. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 118, p. 133-154, . (16/18841-0, 19/07665-4, 15/21880-4)

Please report errors in scientific publications list by writing to: