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 20 of 45 for “"Boolean Satisfiability (SAT)"”.
-
Several Issues on the Boolean Satisfiability (SAT) Problem
Boolean Satisfiability (SAT) is often used as the model for a significant and increasing number of applications in Electronics Design Automation (EDA) and many other fields of computer science and engineering. Although the SAT problem belongs to the class NP-complete - problems that do not have a …
-
Optimizing Vehicle Usage Using CSP, SAT and MAX-SAT
… languages from AI: Constraint Programing (CP), Boolean Satisfiability (SAT), and Maximum Satisfiability (MAX-SAT). We then use solvers to find optimal solutions to this problem. We show which of these solvers is more efficient when finding optimal solutions. For this purpose, we create a test …
-
Selected topics in Computational Relativity
… on building an empirical understanding of why Boolean Satisfiability (SAT) solvers are efficient for real-world problems, when, theoretically, the Boolean SAT problem is computationally intractable.
-
Sampling Techniques for Boolean Satisfiability
Boolean satisfiability (SAT) has played a key role in diverse areas spanning testing, formal verification, planning, optimization, inferencing and the like. Apart from the classical problem of checking boolean satisfiability, the problems of generating satisfying uniformly at random, and of …
-
Random CNF-XOR Formulas
Boolean Satisfiability (SAT) is fundamental in many diverse areas such as artificial intelligence, formal verification, and biology. Recent universal-hashing based approaches to the problems of sampling and counting crucially depend on the runtime performance of specialized SAT solvers on formulas …
-
Efficient Path Delay Test Generation with Boolean Satisfiability
… efficiency of path delay test generation using a Boolean satisfiability (SAT) solver. As part of this research, one of the most commonly used SAT solvers, MiniSat, was integrated into the path delay test generator CodGen. A mixed structural-functional approach was implemented in CodGen where …
-
FPGA Acceleration of Decision-Based Problems using Heterogeneous Computing
The Boolean satisfiability (SAT) problem is central to many applications involving the verification and optimization of digital systems. These combinatorial problems are typically solved by using a decision-based approach, however the lengthy compute time of SAT can make it prohibitively …
-
Quantum Speed-ups for Boolean Satisfiability and Derivative-Free Optimization
… we have considered two important problems, Boolean satisfiability (SAT) and derivative free optimization in the context of large scale quantum computers. In the first part, we survey well known classical techniques for solving satisfiability. We compute the approximate time it would take to …
-
Identifying sources of global contention in constraint satisfaction search
… such as clause-learning and clause-weighting in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs). Many of the top solvers in SAT use clause learning to good effect. A similar approach (nogood learning) has not …
-
Exploits in Concurrency for Boolean Satisfiability
Boolean Satisfiability (SAT) is a problem that holds great theoretical significance along with effective formulations that benefit many real-world applications. While the general problem is NP-complete, advanced solver algorithms and heuristics allow for fast solutions to many large industrial …
-
Hardware Assertions for Mitigating Single-Event Upsets in FPGAs
… clause learning (CDCL) mechanism in modern Boolean satisfiability (SAT) solvers to provide us with invariants which can be realized as hardware checkers. Furthermore, we develop the algorithms required to select a subset of these invariants to be included as part of a checker circuit. This …
-
Novel Value Ordering Heuristics Using Non-Linear Optimization In Boolean Satisfiability
Boolean Satisfiability (SAT) is a fundamental NP-complete problem of determining whether there exists an assignment of variables which makes a Boolean formula evaluate to True. SAT is a convenient representation for many naturally occurring optimization and decisions problems such as planning and …
-
Phylogenetic decisiveness and no-rainbow hypergraph coloring
… randomized algorithm for decisiveness(6) devise Boolean satisfiability (SAT) and integer linear programming formulations (ILP) of decisiveness, which allow us to analyze data sets that arise in practice. For data sets that are not decisive, we use our SAT and ILP formulations to obtain decisive …
-
Probabilistic Techniques For Constraint Satisfaction Problems
Constraint satisfaction problems (CSPs) are at the core of many tasks with direct practical relevance, such as hardware and software verification, planning, and scheduling to name a few. The two main solution paradigms for solving such problems are based on backtrack-style search and local search. …
-
Certifying Correctness for Combinatorial Algorithms : by Using Pseudo-Boolean Reasoning
… dramatic improvements in combinatorialoptimisation algorithms have significantly impacted artificialintelligence, operations research, and other areas. These advances,however, are achieved through highly sophisticated algorithms that aredifficult to verify and prone to implementation errors …
-
Machine learning for structural reasoning in Boolean Satisfiability
… of machine learning and propositional Boolean Satisfiability (SAT) offers transformative possibilities for solving some of the most challenging computational problems. This thesis investigates the use of modern machine learning (ML) and deep learning (DL) methodologies to enhance …
-
Exploiting Boolean Satisfiability Solvers for High Performance Bit-Level Model Checking
… is scalability. Recent performance advances in Boolean Satisfiability (SAT) solvers, brought about a leap in the scalability of those techniques. SAT-based model checking algorithms, however, still suffer from non-negligible applicability issues when confronted with the complexity of many …
-
Scaling quantum compilation with graph rewriting
… from this data structure, relating it to Boolean satisfiability (SAT) problems.<br><br>Together, these contributions lay the groundwork for scalable, GTS-based quantum compilers and advance the integration of quantum and classical compilation techniques. The persistent data structure for …
-
Algorithms and data structures for logic synthesis and verification using Boolean satisfiability
Boolean satisfiability (SAT) was the first problem to be proven to be NP-Complete. The proof, provided by Stephen Cook in 1971, demonstrated that inputs accepted by a non-deterministic Turing machine can be described by satisfying assignments of a Boolean formula. The reduction to SAT feels natural …
-
Formal Methods in Computer-aided Design
… been to encode them in formal languages, such as Boolean satisfiability (SAT) and quantified Boolean formulas (QBFs), and focus academic resources on improving SAT and QBF solvers. The significant progress of these solvers has validated this strategy. This dissertation contributes to the further …
Page 1 of 3