Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 18 of 18 for “"sat solvers"”.
-
A new approach to parallel SAT solvers
We present a novel approach to solving SAT problems in parallel by partitioning the entire set of problem clauses into smaller pieces that can be solved by individual threads. We examine the complications that arise with this partitioning, including the idea of global variables, broadcasting global …
-
Solving Hybrid Boolean SAT by Continuous Optimization
The Boolean SATisfiability problem (SAT) is of central importance in computer science. Despite the NP-completeness of SAT, progress on the engineering side—especially that of Conflict-Driven Clause Learning (CDCL) and Local Search SAT solvers—has been remarkable. Yet, while SAT solvers, aimed at …
-
Searching for patterns in Conway's Game of Life
… search space. More recently, people have used Sat solvers to search for patterns. These solvers are not specifically tuned to this problem and thus waste a lot of time processing Life’s rules in an engine that does not understand them. We propose a novel Sat-based approach that replaces the …
-
Exploring Constraint Satisfiability Techniques in Formal Verification
… widespread demands for efficient Propositional Satisfiability (SAT) solvers and its derivatives in Electronic Design Automation applications, methods to boost the performance of the SAT solver are highly desired. This dissertation aims to enhance the performance of SAT and related SAT solving …
-
Algebraic and Logic Solving Methods for Cryptanalysis
Algebraic solving of polynomial systems and satisfiability of propositional logic formulas are not two completely separate research areas, as it may appear at first sight. In fact, many problems coming from cryptanalysis, such as algebraic fault attacks, can be rephrased as solving a set of Boolean …
-
STRENGTH EVALUATION OF CRYPTOGRAPHIC PRIMITIVES TO LINEAR, DIFFERENTIAL AND ALGEBRAIC ATTACKS.
… main instruments used to solve the system are Sat solvers and Grobner basis of which a comparison is offered in some cases. Particular focus has been paid to SHA1 hash function and on the stream cipher E0, used in the Bluetooth protocol. Samely, differential and linear cryptanalysis are applied …
-
Core extraction and non-example generation : debugging and understanding logical models
… role is explained in terms of how the set of satisfying solutions to the model would change were that subformula removed or altered. Core extraction helps detect and localize unintentional overconstraint, in which real counterexamples are masked by bugs in the model. It leverages recent …
-
Proof theory and algorithms for answer set programming
… search for answer sets are inspired by Boolean Satisfiability (SAT) solving approaches. While the latter have firm proof-theoretic foundations, ASP lacks formal frameworks for characterizing and comparing solving methods. Furthermore, sophisticated search patterns of modern SAT solvers, …
-
An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems
… computationally expensive applications, such as SAT solvers, theorem provers, and game-playing programs. This thesis also contains theory and implementation work on other topics related to task-parallel programming and work stealing schedulers. Some parts of this thesis represent joint work with …
-
Constraint Solving for Diagnosing Concurrency Bugs
… problems. By leveraging the power of constraint satisfiability (SAT) solvers and a bounded model checker, we perform a semantic analysis of the sequential computation as well as the thread interactions. The analysis is ideally suited for handling software with small to medium code size but …
-
Generating structurally complex tests from declarative constraints
… structurally complex data, presents an automated SAT-based framework for testing such programs, and provides evidence on the feasibility of using this approach to generate high quality test suites and find bugs in non-trivial programs. The framework tests a program systematically on all …
-
Synthesis of domain specific CNF encoders for bit-vector solvers
SMT solvers are at the heart of a number of software engineering tools. These SMT solvers use a SAT solver as the back-end and convert the high-level constraints given by the user down to low-level boolean formulas that can be efficiently mapped to CNF clauses and fed into a SAT solver. Current SMT …
-
Fast Static Learning and Inductive Reasoning with Applications to ATPG Problems
… invariants have been possible due to efficient SAT solvers. Although a significant amount of research effort has been dedicated to the development of effective invariant learning techniques over the years, the computation time for deriving powerful multi-node invariants is still a bottleneck for …
-
SAT Solving Using XOR-OR-AND Normal Forms and Cryptographic Fault Attacks
The Boolean satisfiability problem (SAT) lies at the core of computational logic and has found many applications in verification, cryptography, and artificial intelligence. While conflict-driven SAT solvers (CDCL) excel on large industrial instances, they struggle with XOR-rich instances arising …
-
Synthesizing a synthesis tool
SMT/SAT solvers are used by many tools for program verification and analysis. Most of these tools have an optimization layer which applies transformations (or "rewrite rules") to simplify the internal representation of the problem. These hard coded rules can drastically affect the performance of …
-
Formal Verification Techniques for Reversible Circuits
… the use of Reversible Miter circuits followed by SAT-solvers to ascertain equivalence. The second half of this work focuses upon the application of the proposed reduction technique to Reversible Miter circuits as a pre-processing step to improve the efficiency of the subsequent SAT-based …
-
System verification tools based on Monadic Logics
In der Mitte des letzten Jahrhunderts erschienen die ersten Arbeiten über monadische Logiken zweiter Stufe. Das Interesse an diesen Logiken lag zunächst hauptsächlich an Entscheidbarkeitsfragen von arithmetischen Theorien. Die monadischen Logiken zweiter Stufe über Wörter und Bäume gehören zu den …
-
Circuit Design Methods with Emerging Nanotechnologies
… (PLE) is first proposed to explore the versatile functionalities of threshold gates (TGs) and multi-threshold threshold gates (MTTGs). This PLE structure can realize all three- or four-variable logic functions through configuring binary control bits. This is the first single threshold logic …