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 48 for “"SAT solving"”.
-
Distributed SAT solving engine
The boolean satisfiability problem (SAT) is one of the typical NP-complete problems that have found considerable industrial applications in the past decades. Significant theoretical and practical efforts has been devoted to the research in this particular problem. Recently, with the major …
-
Impact of the LZW-based common subexpression elimination algorithm on SAT-solving efficiency
The Satisfiability (SAT) problem is the problem of finding an assignment that satisfies a given propositional formula. SAT is effective in solving many important problems in areas such as automated reasoning, computer-aided design, and planning in Artificial Intelligence. The need to solve these …
-
Automated Verification of Object Petri Nets based on Transformation, Unfoldings and SAT Solving
… actions in some environment in order to satisfy their design objectives. To<br/>this end, several agents communicate and interact in order to solve a complex problem. <br/><br/>With Object Petri nets it is possible to model the mobility and dynamic interactions among agents based on their …
-
Towards Next Generation Sequential and Parallel SAT Solvers
This thesis focuses on improving the SAT solving technology. The improvements focus on two major subjects: sequential SAT solving and parallel SAT solving. To better understand sequential SAT algorithms, the abstract reduction system Generic CDCL is introduced. With Generic CDCL, the soundness of …
-
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 …
-
Structure-based satisfiability checking : analyzing and harnessing the potential
Constraint satisfaction deals with developing automated techniques for solving computationally hard problems in a declarative fashion. The main emphasis of this thesis is on constraint satisfaction techniques for the propositional satisfiability problem (SAT). As solving techniques for …
-
The Impact of Boolean Satisfiability Problem Structure on Graph Neural Network Performance
Boolean Satisfiability (SAT) is a fundamental problem in the study of computational complexity, particularly in understanding the complexity class of NP problems. Over the years, Graph Neural Networks (GNNs) have achieved significant advancements in domains such as graphics and image processing. …
-
Grid based propositional satisfiability solving
… cloud computing can be applied to efficiently solving propositional satisfiability problem (SAT) instances. Propositional logic provides a convenient language for expressing real-world originated problems such as AI planning, automated test pattern generation, bounded model checking and …
-
Applications of Games to Propositional Proof Complexity
… system forms the underpinnings of all modern SAT-solving algorithms, including clause learning. In practice, the limiting factor on these algorithms is memory space, so there is a strong motivation for better understanding it as a resource. With the second group of results in this thesis we …
-
SAT Encodings of Finite CSPs
Boolean satisfiability (SAT) is the problem of determining whether there exists an assignment of the Boolean variables to the truth values such that a given Boolean formula evaluates to true. SAT was the first example of an NP-complete problem. Only two decades ago SAT was mainly considered as of a …
-
Hardware-Accelerated SAT Solvers
We present a hardware-accelerated Boolean Satisfiability Problem (SAT) solver targeting processor/Field-Programmable Gate Array (FPGA) System on Chip (SoC)s. Our solution accelerates the most expensive subroutine of the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, Boolean Constrain Propagation …
-
SAT and CP
In this thesis, we consider the parallelisation and application of SAT and CP solvers. In the first chapter, we consider SAT, the decision problem of propositional logic. We discuss details of the implementations of SAT solvers, and show how to improve upon existing sequential solvers. Furthermore, …
-
Satisfiability and Optimization in Periodic Traffic Flow Problems
… the appropriate usage of several techniques like SAT solving and MaxSAT to calculate and optimize the corresponding instances will be presented accordingly. Computational results for real-world scenarios suggest the practical impact and give promising perspectives for further scientific research.
-
Improving formal reasoning for software systems using machine learning and symbolic approaches
… automated logical reasoning techniques such as SAT (Boolean Satisfiability) solving, model counting, and model enumeration. For front-end improvements, this dissertation introduces iAlloy, an efficient method for analyzing Alloy specifications. Recognizing that users frequently make incremental …
-
Efficient Path Delay Test Generation with Boolean Satisfiability
… 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 longest paths …
-
Verification and synthesis of linear systems by abstract acceleration
… Furthermore, by applying control theory and SAT solving techniques, we explore the synthesis of correct by construction digital controllers using abstract acceleration as a model template. Our results show that the technique scales to models with several dozen variables for which sound …
-
Hardware-Algorithm Co-Design for Energy-Efficient and Low-Latency Domain-Specific Machine Learning Systems
… co-design techniques for distributed SAT solving using stochastic recurrent neural networks (S-RNNs). Leveraging low-precision weights and tensor-parallel execution with Reduce-Scatter communication, we achieve notable speedups and reduced latency.
-
Design automation for circuit reliability and energy efficiency
… heuristics are used in our approaches such as SAT solving, data mining, logic restructuring, and applied mathematics. Furthermore, the scalability of our approaches was taken into account while we developed our solutions. Experimental results show that our approaches offer the following …
-
Prioritized Unit Propagation and Extended Resolution Techniques for SAT Solvers
NP-complete problems like the Boolean Satisfiability (SAT) Problem are ubiquitous in computer science, mathematics, and engineering. Consequently, researchers have developed algorithms such as Conflict-Driven Clause-Learning (CDCL) SAT solvers, aimed at determining the satisfiability of Boolean …
-
AUnit - a testing framework for alloy
… relational language that is supported by its SAT-based analyzer. We take inspiration from the success of the family of xUnit frameworks that are used widely in practice for test automation, albeit for imperative or object-oriented programs. The key novelty of our work is to define a basis for …
Page 1 of 3