Probabilistic satisfiability: algorithms with the presence and absence of a phase transition

DOI10.1007/S10472-015-9466-6zbMATH Open1347.68331OpenAlexW2212155158WikidataQ117021971 ScholiaQ117021971MaRDI QIDQ905995

Glauber De Bona, Marcelo Finger

Publication date: 28 January 2016

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-015-9466-6

zbMATH Keywords

phase transitionprobabilistic satisfiabilityPSAT

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Reasoning under uncertainty in the context of artificial intelligence (68T37) Logic in artificial intelligence (68T27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory and Applications of Satisfiability Testing
• Stochastic independence in a coherent setting
• Probabilistic logic
• A linear programming approach to reasoning about probabilities
• Merging the local and global approaches to probabilistic satisfiability
• Column Generation Methods for Probabilistic Logic
• A Hybrid Method for Probabilistic Satisfiability
• The complexity of theorem-proving procedures
• A linear-time transformation of linear inequalities into conjunctive normal form
• Classical recursion theory. The theory of functions and sets of natural numbers
• Probabilistic satisfiability with imprecise probabilities
• The many facets of linear programming
• Direct algorithms for checking consistency and making inferences from conditional probability assessments
• Exploiting Cycle Structures in Max-SAT
• Probability logic
• Algorithms for the maximum satisfiability problem
• The Consistency of the CADIAG-2 Knowledge Base: A Probabilistic Approach
• Boole's logic and probability. A critical exposition from the standpoint of contemporary algebra, logic and probability theory. 2nd ed., rev. and enlarged
• Simplification rules for the coherent probability assessment problem
• Probabilistic satisfiability
• Probability logic and optimization SAT: The PSAT and CPA models
• Easy cases of probabilistic satisfiability
• Probabilistic satisfiability
• Solutions for Hard and Soft Constraints Using Optimized Probabilistic Satisfiability
• Probabilistic satisfiability and coherence checking through integer programming
• Probabilistic logic revisited
• Understanding a Probabilistic Description Logic via Connections to First-Order Logic of Probability
• Probabilistic satisfiability: algorithms with the presence and absence of a phase transition

Cited In (8)

• Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics
• Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
• Probabilistic satisfiability: algorithms with the presence and absence of a phase transition
• Probabilistic sentence satisfiability: an approach to PSAT
• Phase transitions of PP-complete satisfiability problems
• Quantitative Logic Reasoning
• Generalized probabilistic satisfiability
• Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities

Uses Software

• MiniSat
• z3
• Chaff
• MSUnCore
• Pronto

This page was built for publication: Probabilistic satisfiability: algorithms with the presence and absence of a phase transition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q905995)