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 436 for “"satisfiability"”.
-
Generalized Satisfiability Problems
… example of an NP-complete problem is the satisfiability problem of propositional formulas (SAT). Here we get a propositional formula as an input and it must be decided whether an assignment for the propositional variables exists, such that this assignment satisfies the given formula. The …
-
Efficient satisfiability solver
… saw great improvements in the performance of satisfiability (SAT) solvers. In this thesis, we discuss the state-of-the-art techniques used in building an efficient SAT solver. Modern SAT solvers are mainly constituted by the following components: decision heuristics, Boolean constraint …
-
Backdoors in Satisfiability Problems
Although satisfiability problems (SAT) are NP-complete, state-of-the-art SAT solvers are able to solve large practical instances. The notion of backdoors has been introduced to capture structural properties of instances. Backdoors are a set of variables for which there exists some value assignment …
-
Augmenting Local Search for Satisfiability
This dissertation explores approaches to the satisfiability problem, focusing on local search methods. The research endeavours to better understand how and why some local search methods are effective. At the root of this understanding are a set of metrics that characterize the behaviour of local …
-
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 …
-
Grid based propositional satisfiability solving
… 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 cryptanalysis. The interest …
-
Application of satisfiability to examination timetabling
This thesis describes approaches for solving non-boolean problems, especially examination timetabling problems, develops and implements three non-boolean procedures--the NB-GSAT procedure, the NB-WalkSAT procedure and the WSAT(OIP) procedure, and uses them on six groups of examination problems and …
-
Using Join Networks to Compute Satisfiability
Satisfiability (SAT) of propositional logic formulas is a canonical NP-complete problem; algorithms for its solution have been studied for over forty years. The representational power of propositional logic allows a host of research and real-world problems to be solved using SAT solvers: some …
-
Incremental Satisfiability Solving and its Applications
The propositional logic satisfiability problem (SAT) is a computationally hard decision problem. Despite its theoretical hardness, decision procedures for solving instances of this problem have become surprisingly efficient in recent years. These procedures, known as SAT solvers, are able to solve …
-
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 …
-
A Probabilistic Study of 3-SATISFIABILITY
… and analyses randomly generated instances of 3-SATISFIABILITY to gain insights into the structure of the underlying solution space. Two random variables are defined and analyzed to assess the probability that a fixed solution will be assigned a particular objective function value in a randomly …
-
Efficient, mechanically-verified validation of satisfiability solvers
Satisfiability (SAT) solvers are commonly used for a variety of applications, including hardware verification, software verification, theorem proving, debugging, and hard combinatorial problems. These applications rely on the efficiency and correctness of SAT solvers. When a problem is determined …
-
Inductive logic programming as satisfiability modulo theories
… is that <em>LFF frames the ILP problem as one of Satisfiability Modulo Theories (SMT)</em>. With the search for viable hypotheses handed-off to a SAT-solver, the test stage can be regarded as a theory solver collaborating with the SAT-solver, effectively making ILP’s notion of background knowledge …
-
Satisfiability-based Program Reasoning and Program Synthesis
… the underlying inference tasks as solutions to satisfiability instances. A core ingredient in the reduction of these problems to finite satisfiability instances is the assumption of templates. Templates are user-provided hints about the structural form of the desired artifact, e.g., invariant, …
-
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 …
Page 1 of 22