Practical Applications of Boolean Satisfiability [PDF]
2008 9th International Workshop on Discrete Event Systems, 2008 Boolean satisfiability (SAT) solvers have been the subject of remarkable improvements since the mid 90s. One of the main reasons for these improvements has been the wide range of practical applications of SAT. Indeed, examples of modern applications of SAT range from termination analysis in term-rewrite systems to circuit-level prediction of crosstalk ...
João Marques Silva
exaly +3 more sources
Symmetry in Boolean Satisfiability [PDF]
Symmetry, 2010 This paper reviews recent approaches on how to accelerate Boolean Satisfiability (SAT) search by exploiting symmetries in the problem space. SAT search algorithms traverse an exponentially large search space looking for an assignment that satisfies a set of constraints.
exaly +3 more sources
Backjumping for Quantified Boolean Logic Satisfiability
Artificial Intelligence, 2003 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Enrico Giunchiglia +2 more
exaly +5 more sources
APPLICATION OF INCREMENTAL SATISFIABILITY PROBLEM SOLVERS FOR NON-DETERMINISTIC POLYNOMIAL-TIME HARD PROBLEMS AS ILLUSTRATED BY MINIMAL BOOLEAN FORMULA SYNTHESIS PROBLEM [PDF]
Научно-технический вестник информационных технологий, механики и оптики, 2020 Subject of Research. The paper considers a method for solution of the nondeterministic polynomial hard problem (NP-hard problem) of a minimal Boolean formula synthesis from a given truth table.
Konstantin I. Chukharev
doaj +1 more source
Solving Graph Coloring Problem Based on Grover Algorithm [PDF]
Jisuanji kexue, 2023 Grover quantum search algorithm is a famous quantum algorithm designed for unstructured search problems.It can be used to solve problems such as graph coloring and shortest path sorting,and can also effectively decipher cryptosystems.Graph coloring ...
LIU Xiaonan, LIU Zhengyu, XIE Haoshan, ZHAO Chenyan
doaj +1 more source
Quantum Algorithm for Variant Maximum Satisfiability
Entropy, 2022 In this paper, we proposed a novel quantum algorithm for the maximum satisfiability problem. Satisfiability (SAT) is to find the set of assignment values of input variables for the given Boolean function that evaluates this function as TRUE or prove that
Abdirahman Alasow +2 more
doaj +1 more source
Satisfiability modulo theories and chiral heterotic string vacua with positive cosmological constant
Physics Letters B, 2021 We apply Boolean Satisfiability (SAT) and Satisfiability Modulo Theories (SMT) solvers in the context of finding chiral heterotic string models with positive cosmological constant from Z2×Z2 orbifolds.
Alon E. Faraggi +3 more
doaj +1 more source
Solving Restricted Preemptive Scheduling on Parallel Machines with SAT and PMS [PDF]
Journal of Universal Computer Science, 2023 Restricted preemption plays a crucial role in reducing total completion time while controlling preemption overhead. A typical version of restricted preemptive models is k-restricted preemptive scheduling, where preemption is only allowed after a task has
Xiaojuan Liao +4 more
doaj +3 more sources
Boolean satisfiability with transitivity constraints [PDF]
ACM Transactions on Computational Logic, 2000 We consider a variant of the Boolean satisfiability problem where a subset ε of the propositional variables appearing in formula F sat encode a symmetric, transitive, binary relation over N elements. Each of these relational variables, e
Randal E. Bryant, Miroslav N. Velev
openaire +5 more sources
Deterministic Algorithms for Solving Boolean Polynomial Equations Based on Channel Coding Theory
IEEE Access, 2020 Solving the satisfiability problems of Boolean polynomial equations is still an open challenge in the fields of mathematics and computer science.
Guangfu Wu +5 more
doaj +1 more source