Advanced search
Start date
Betweenand

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

Abstract

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
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications (18)
(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)
FINGER, MARCELO; PRETO, SANDRO. Probably Partially True: Satisfiability for Lukasiewicz Infinitely-Valued Probabilistic Logic and Related Topics. JOURNAL OF AUTOMATED REASONING, v. 64, n. 7, p. 18-pg., . (14/12236-1, 15/21880-4)
FINGER, MARCELO; DE BONA, GLAUBER; AAAI. Algorithms for Deciding Counting Quantifiers over Unary Predicates. PROCEEDINGS OF THE TWENTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, v. N/A, p. 7-pg., . (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)
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, p. 20-pg., . (15/21880-4, 16/18841-0)
COZMAN, FABIO GAGLIARDI; MAUA, DENIS DERATANI; LANG, J. The Finite Model Theory of Bayesian Networks: Descriptive Complexity. PROCEEDINGS OF THE TWENTY-SEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, v. N/A, p. 5-pg., . (15/21880-4, 16/18841-0, 16/01055-1)
COZMAN, FABIO G.; MAUA, DENIS D.; ANTONUCCI, A; CHOLVY, L; PAPINI, O. The Descriptive Complexity of Bayesian Network Specifications. SYMBOLIC AND QUANTITATIVE APPROACHES TO REASONING WITH UNCERTAINTY, ECSQARU 2017, v. 10369, p. 11-pg., . (15/21880-4)
DE BONA, GLAUBER; FINGER, MARCELO; RIBEIRO, MARCIO M.; SANTOS, YURI D.; WASSERMANN, RENATA; AAAI. Consolidating Probabilistic Knowledge Bases via Belief Contraction. 2022 25TH INTERNATIONAL CONFERENCE ON INFORMATION FUSION (FUSION 2022), v. N/A, p. 10-pg., . (15/21880-4)
PRETO, SANDRO; FINGER, MARCELO. Efficient representation of piecewise linear functions into Lukasiewicz logic modulo satisfiability. MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, v. N/A, p. 26-pg., . (21/03117-2, 14/12236-1, 19/07665-4, 15/21880-4)
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)
PRETO, SANDRO; FINGER, MARCELO. Proving properties of binary classification neural networks via Lukasiewicz logic. LOGIC JOURNAL OF THE IGPL, v. N/A, p. 17-pg., . (14/12236-1, 19/07665-4, 15/21880-4, 21/03117-2)
OTTE VIEIRA DE FARIA, FRANCISCO HENRIQUE; COZMAN, FABIO GAGLIARDI; MAUA, DENIS DERATANI; MORAL, S; PIVERT, O; SANCHEZ, D; MARIN, N. Closed-Form Solutions in Learning Probabilistic Logic Programs by Exact Score Maximization. SCALABLE UNCERTAINTY MANAGEMENT (SUM 2017), v. 10564, p. 15-pg., . (15/21880-4, 16/01055-1, 16/18841-0)
MAUA, DENIS DERATANI; COZMAN, FABIO GAGLIARDI. Thirty years of credal networks: Specification, algorithms and complexity. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 126, p. 25-pg., . (19/07665-4, 16/18841-0, 15/21880-4)
COZMAN, FABIO G.; MAUA, DENIS D.; ANTONUCCI, A; CHOLVY, L; PAPINI, O. The Complexity of Inferences and Explanations in Probabilistic Logic Programming. SYMBOLIC AND QUANTITATIVE APPROACHES TO REASONING WITH UNCERTAINTY, ECSQARU 2017, v. 10369, p. 10-pg., . (16/01055-1, 15/21880-4)
SALVATORE, FELIPE DE SOUZA; FINGER, MARCELO; HIRATA JR, ROBERTO; PATRIOTA, ALEXANDRE G.. A resampling-based method to evaluate NLI models. NATURAL LANGUAGE ENGINEERING, v. N/A, p. 28-pg., . (15/24485-9, 14/12236-1, 19/07665-4, 15/21880-4, 18/21934-5, 15/22308-2)
FINGER, MARCELO; PRETO, SANDRO; GALMICHE, D; SCHULZ, S; SEBASTIANI, R. Probably Half True: Probabilistic Satisfiability over Lukasiewicz Infinitely-Valued Logic. AUTOMATED REASONING, IJCAR 2018, v. 10900, p. 17-pg., . (14/12236-1, 15/21880-4)

Please report errors in scientific publications list using this form.