Dissertations / Theses on the topic 'Satisfiability'
To see the other types of publications on this topic, follow the link: Satisfiability.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Satisfiability.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Gregory, Peter. "Structure in satisfiability." Thesis, University of Strathclyde, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.488552.
Full textAbstract:
This thesis examines the question of how it is possible to improve search techniques by better understanding hidden structure in Boolean Satisfiability problems. The backdoor structure, once found, makes a Satisfiability problem easy. This work provides ways of finding backdoors for analysis. It also provides a general theoretical description of what back doors represents.
2
Slater, Andrew, and andrew slater@csl anu edu au. "Investigations into Satisfiability Search." The Australian National University. Research School of Information Sciences and Engineering, 2003. http://thesis.anu.edu.au./public/adt-ANU20040310.103258.
Full textAbstract:
In this dissertation we investigate theoretical aspects of some practical approaches used
in solving and understanding search problems. We concentrate on the Satisfiability
problem, which is a strong representative from search problem domains. The work develops
general theoretical foundations to investigate some practical aspects of satisfiability
search. This results in a better understanding of the fundamental mechanics for search
algorithm construction and behaviour. A theory of choice or branching heuristics is
presented, accompanied by results showing a correspondence of both parameterisations and
performance when the method is compared to previous empirically motivated branching
techniques. The logical foundations of the backtracking mechanism are explored alongside formulations for reasoning in relevant logics which results in the development of a
malleable backtracking mechanism that subsumes other intelligent backtracking proof
construction techniques and allows the incorporation of proof rearrangement strategies.
Moreover, empirical tests show that relevant backtracking outperforms all other forms of
intelligent backtracking search tree construction methods. An investigation into
modelling and generating world problem instances justifies a modularised problem model proposal which is used experimentally to highlight the practicability of search algorithms
for the proposed model and related domains.
3
Subramanian, Rishi Bharadwaj. "FPGA Based Satisfiability Checking." University of Cincinnati / OhioLINK, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1583154848438753.
Full text
4
Zane, Francis. "Circuits, CNFs, and satisfiability /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 1998. http://wwwlib.umi.com/cr/ucsd/fullcit?p9907670.
Full text
5
Robinson, Nathan. "Advancing planning-as-satisfiability." Thesis, Griffith University, 2012. http://hdl.handle.net/10072/367119.
Full textAbstract:
Since 1992 a popular and appealing technique for solving planning problems has been to use a general purpose solution procedure for Boolean SAT(isfiability) problems. In this setting, a fixed horizon instance of the problem is encoded as a formula in propositional logic. A SAT procedure then computes a satisfying valuation for that formula, or otherwise proves it unsatisfiable. Here, the SAT encoding is constructive in the usual sense that there is a one-to-one correspondence between plans –i.e., solutions to the planning problem– and satisfying valuations of the formula.
One of the biggest drawbacks of this approach is the enormous sized formulae generated by
the proposed encodings. In this thesis we mitigate that problem by developing, implementing,
and evaluating a novel encoding that uses the techniques of splitting and factoring to develop a compact encoding that is amenable to state-of-the-art SAT procedures. Overall, our approach is the most scalable, and our representation the most compact amongst optimal planning procedures.
We then examine planning with numeric quantities, and in particular optimal planning with
action costs. SAT-based procedures have previously been proposed in this setting for the fixed horizon case, where there is a given limit on plan length, however a key challenge has been to develop a SAT-based procedure that can achieve horizon-independent optimal solutions – i.e., the least costly plan irrespective of length. Meeting that challenge, in this thesis we develop a novel horizon-independent optimal procedure that poses partially weighted MaxSAT problems to our own cost-optimising conflict-driven clause learning (CDCL) procedure. We perform a detailed empirical evaluation of our approach, detailing the types of problem structures where it dominates.
Finally, we take the insights gleaned for the classical propositional planning case, and develop
a number of encodings of problems that are described using control-knowledge. That control knowledge expresses domain-dependent constraints which: (1) constrain the space of admissible plans, and (2) allow the compact specification of constraints on plans that cannot be naturally or efficiently specified in classical propositional planning. Specifically, in this thesis we develop encodings for planning using temporal logic based constraints, procedural knowledge written in a language based on ConGolog, and Hierarchical Task Network based constraints. Our compilations use the technique of splitting to achieve relatively compact encodings compared to existing compilations. In contrast to similar work in the field of answer set planning, our compilations admit plans in the parallel format, a feature that is crucial for the performance of SAT-based planning.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Science, Environment, Engineering and Technology
Full Text
6
Oe, Duck Ki. "Formally certified satisfiability solving." Diss., University of Iowa, 2012. https://ir.uiowa.edu/etd/3362.
Full textAbstract:
Satisfiability (SAT) and satisfiability modulo theories (SMT) solvers are high-performance automated propositional and first-order theorem provers, used as underlying tools in many formal verification and artificial intelligence systems. Theoretic and engineering advancement of solver technologies improved the performance of modern solvers; however, the increased complexity of those solvers calls for formal verification of those tools themselves. This thesis discusses two methods to formally certify SAT/SMT solvers. The first method is generating proofs from solvers and certifying those proofs. Because new theories are constantly added to SMT solvers, a flexible framework to safely add new inference rules is necessary. The proposal is to use a meta-language called LFSC, which is based on Edinburgh Logical Framework. SAT/SMT logics have been encoded in LFSC, and the encoding can be easily and modularly extended for new logics. It is shown that an optimized LFSC checker can certify SMT proofs efficiently. The second method is using a verified programming language to implement a SAT solver and verify the code statically. Guru is a pure functional programming language with support for dependent types and theorem proving; Guru also allows for efficient code generation by means of resource typing. A modern SAT solver, called versat, has been implemented and verified to be correct in Guru. The performance of versat is shown to be comparable with that of the current proof checking technology.
7
Rolf, Daniel. "Algorithms for the satisfiability problem." Doctoral thesis, [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=982636849.
Full text
8
Southey, Finnegan. "Augmenting Local Search for Satisfiability." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1075.
Full textAbstract:
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 search methods. Based on this understanding, two new local search methods are proposed and tested, the first, SDF, demonstrating the value of the insights drawn from the metrics, and the second, ESG, achieving state-of-the-art performance and generalizing the approach to arbitrary 0-1 integer linear programming problems. This generality is demonstrated by applying ESG to combinatorial auction winner determination. Further augmentations to local search are proposed and examined, exploring hybrids that incorporate aspects of backtrack search methods.
9
Dahllöf, Vilhelm. "Exact Algorithms for Exact Satisfiability Problems." Doctoral thesis, Linköping University, Linköping University, TCSLAB, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-6907.
Full textAbstract:
This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. While developing exact algorithms to solve the problems, we gain new insights into their structure and mutual similarities and differences.
Given a Boolean formula in CNF, the XSAT problem asks for an assignment to the variables such that each clause contains exactly one true literal. For this problem we present an O(1.1730n) time algorithm, where n is the number of variables. XSAT is a special case of the General Exact Satisfiability problem which asks for an assignment such that in each clause exactly i literals be true. For this problem we present an algorithm which runs in O(2(1-ε) n) time, with 0 < ε < 1 for every fixed i; for i=2, 3 and 4 we have running times in O(1.4511n), O(1.6214n) and O(1.6848n) respectively.
For the counting problems we present an O(1.2190n) time algorithm which counts the number of models for an XSAT instance. We also present algorithms for #2SATw and #3SATw, two well studied Boolean problems. The algorithms have running times in O(1.2561n) and O(1.6737n) respectively.
Finally we study optimisation problems: As a variant of the Maximum Exact Satisfiability problem, consider the problem of finding an assignment exactly satisfying a maximum number of clauses while the rest are left with no true literal. This problem is reducible to #2SATw without the addition of new variables and thus is solvable in time O(1.2561n). Another interesting optimisation problem is to find two XSAT models which differ in as many variables as possible. This problem is shown to be solvable in O(1.8348n) time.
10
Dahllöf, Vilhelm. "Exact algorithms for exact satisfiability problems /." Linköping : Department of Computer and Information Science, Linköpings universitet, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-6907.
Full text
11
Russell, Richard Anthony. "Planning with preferences using maximum satisfiability." Thesis, University of Cambridge, 2012. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.610496.
Full text
12
Tamaki, Suguru. "Improved Algorithms for CNF Satisfiability Problems." 京都大学 (Kyoto University), 2006. http://hdl.handle.net/2433/68895.
Full text
13
Husain, Dhiaiddin. "Satisfiability problem and lattice basis problem." Aix-Marseille 2, 1996. http://www.theses.fr/1996AIX22037.
Full textAbstract:
Ce travail est divise en deux parties. Dans la premiere partie, nous etudions la transformation du probleme sat (satisfaisabilite), pour une entree f, en un probleme de recherche d'une base reduite d'un reseau l(f) convenablement associe a f en utilisant l'algorithme l#3fp, une variante connue de l'algorithme l#3 de lovasz. Nous avons d'abord associe a une entree f pour sat un reseau l(f) en transformant f en un systeme f d'inegalites lineaires a coefficients entiers, puis en un systeme d'equations a coefficients entiers e(f). Pour definir l(f) a partir de e(f), nous generalisons successivement deux procedes, alsco base et ajs base, qui etaient utilises pour resoudre le probleme du sac a dos. Nous utilisons alors l'algorithme l#3fp pour trouver une base reduite, au sens de lovasz, pour le reseau l(f). L'iteration de la reduction de l#3fp ne serait pas suffisante pour notre propos: il convient d'extraire (v + 1) vecteurs e#1,. . . ,e#v#+#1 de la base reduite (v est le nombre des variables de f) puis, nous proposons un algorithme que nous appelons mult (multiplicateurs) si aucun de e#i, v + 1 i 1, ne permet de remonter a une solution pour le probleme sat de f, mult essaye d'abord les (e#i e#j) puis (e#i e#j e#k) ainsi de suite jusqu'a trouver une solution. Nous appliquons aussi l'algorithme mult a des instances, de differentes dimensions, du probleme de sac a dos a deux equations, avec de densites pour lesquelles on n'obtient pas de solutions en utilisant les techniques de reductions des bases. La seconde partie consiste a factoriser un entier donne n comme produit de deux entiers pq en etudiant la satisfaisabilite d'un ensemble (n)#m#,#n de clauses exprimant la condition n = pq, les variables etant les m bits de numerations en base 2 de p,les n bits de q et les bits de n. Les ensembles deterministes de clauses (n)#m#,#n, qui representent les facteurs des entiers donnes, sont traites par un algorithme de resolution. Nous comparons, par le meme algorithme, les temps de calculs de ces donnees a ceux des donnees, generees aleatoirement, ayant les memes tailles que celles deterministes, le temps etant compte en nombre de nuds d'arbre de calcul
14
Sohanghpurwala, Ali Asgar Ali Akbar. "Exploits in Concurrency for Boolean Satisfiability." Diss., Virginia Tech, 2018. http://hdl.handle.net/10919/86417.
Full textAbstract:
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 problems. In addition to SAT, many applications rely on generalizations of Satisfiability such as MaxSAT, and Satisfiability Modulo Theories (SMT).
Much of the advancement in SAT solver performance has been in the realm of improved sequential solvers with advanced conflict resolution, learning mechanisms, and sophisticated heuristics.
There have been some successful demonstrations of massively parallel and
hardware-accelerated solvers for SAT, but these have failed to find their way
into mainstream usage. This document first presents previous work in
Hardware Acceleration of Satisfiability followed by an analysis of why these
attempts failed to gain widespread acceptance. It then demonstrates an
alternative, hardware-centric approach, based on distributed Stochastic Local
Search (SLS) that is better suited to efficient hardware implementation.
Then a parallel SLS/CDCL hybrid approach is proposed that is suitable for distributed search
with minimal communication overhead while maintaining completeness. Finally the efficacy and flexibility of
distributed local search is considered with an adaptation to Weighted Partial
MaxSAT (WPMS) and a focused case study on converted Probabilistic Inference instances.Ph. D.
15
Aytemiz, Tevfik. "A Probabilistic Study of 3-SATISFIABILITY." Diss., Virginia Tech, 2001. http://hdl.handle.net/10919/28202.
Full textAbstract:
Discrete optimization problems are defined by a finite set of solutions together with an objective function value assigned to each solution. Local search algorithms provide useful tools for addressing a wide variety of intractable discrete optimization problems. Each such algorithm offers a distinct set of rules to intelligently exploit the solution space with the hope of finding an optimal/near optimal solution using a reasonable amount of computing time.
This research studies 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 generated instance of 3-SATISFIABILITY. Then, a random vector is defined and analyzed to investigate how the solutions in the solution space are distributed over their objective function values. These results are then used to define a stopping criterion for local search algorithms applied to MAX 3-SATISFIABILITY.
This research also analyses and compares the effectiveness of two local search algorithms, tabu search and random restart local search, on MAX 3-SATISFIABILITY. Computational results with tabu search and random restart local search on randomly generated instances of 3-SATISFIABILITY are reported. These results suggest that, given a limited computing budget, tabu search offers an effective alternative to random restart local search. On the other hand, these two algorithms yield similar results in terms of the best solution found. The computational results also suggest that for randomly generated instances of 3-SATISFIABILITY (of the same size), the globally optimal solution objective function values are typically concentrated over a narrow range.Ph. D.
16
Weaver, Sean A. "Satisfiability Advancements Enabled by State Machines." University of Cincinnati / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1353343116.
Full text
17
Andersen, Carl Floyd. "Using join networks to compute satisfiability." College Park, Md. : University of Maryland, 2008. http://hdl.handle.net/1903/8146.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2008.Thesis research directed by: Dept. of Computer Science. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
18
Turner, Charles Hudson. "Causal action theories and satisfiability planning /." Digital version accessible at:, 1998. http://wwwlib.umi.com/cr/utexas/main.
Full text
19
Calabro, Chris. "The exponential complexity of satisfiability problems." Diss., [La Jolla] : University of California, San Diego, 2009. http://wwwlib.umi.com/cr/ucsd/fullcit?p3369625.
Full textAbstract:
Thesis (Ph. D.)--University of California, San Diego, 2009.Title from first page of PDF file (viewed September 15, 2009). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 129-133).
20
Bailey, Delbert D. "Phase transitions of boolean satisfiability variants /." Diss., Digital Dissertations Database. Restricted to UC campuses, 2004. http://uclibs.org/PID/11984.
Full text
21
Cai, Shaowei. "Novel Local Search Methods for Satisfiability." Thesis, Griffith University, 2015. http://hdl.handle.net/10072/366424.
Full textAbstract:
The Boolean Satisfiability Problem (SAT) is a prototypical NP-complete problem, and is central in computer science and artificial intelligence. Given a formula over a set of Boolean variables, the SAT problem tests whether an interpretation that satisfies the formula exists.
Stochastic Local Search (SLS) is a simple but effective approach to SAT. In this thesis, we proposed new SLS techniques for SAT solving and developed new SLS algorithms. Using empirical evaluations, we showed that at the time they were designed our algorithms performed better than the existing state-of-the-art solvers. Moreover, our algorithms have been established as the latest state-of-the-art algorithms for several types of instances.
The first idea is configuration checking (CC) for SAT. A typical CC technique is to forbid flipping a variable if since the last time it was flipped, none of its neighbouring variables has been flipped. Based on this strategy, we developed several solvers, including Swcca and CCAnr. In particular, CCAnr performed very well on crafted instances, and a hybrid solver CCAnr+glucose won the silver prize of Hard-combinatorial track in SAT Competition 2014.
The second idea is the notion of multilevel properties which consider the satisfaction degree of clauses. Using the CC strategy and the second level score, we developed the CCASat solver, which won the 2012 SAT Challenge random track. We also proposed several new scoring functions, which were used to design CScoreSAT and HScoreSAT. These two solvers are particularly efficient in solving random SAT instances with long clauses, and show one to two orders of magnitude improvement than previous solvers. Thirdly, we proposed a linear make function for tie-breaking in the famous algorithm WalkSAT, leading to the WalkSATlm algorithm. Our experiments demonstrate that WalkSATlm improves WalkSAT by orders of magnitudes on random k-SAT instances with k > 3.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Science, Environment, Engineering and Technology
Full Text
22
Meng, Baoluo. "Satisfiability modulo relations: theory and applications." Diss., University of Iowa, 2018. https://ir.uiowa.edu/etd/6614.
Full textAbstract:
Many computational problems require reasoning about relational structures. Examples include high-level system design, architectural configuration of network systems, reasoning about ontologies, and verification of programs with linked data structures. Traditionally, relational models are translated to propositional formulas and then solved by leveraging SAT solvers. However, SAT solvers can only reason about problems within a finite scope, i.e, concrete cardinality bounds on the relations involved. SMT solvers, on the other hand, are efficient tools that can check automatically the satisfiability of complex constraints over several domains without scope restrictions. They are used as the back-end solvers in many verification tools.
To break the limitation of bounded analysis, this thesis presents a many-sorted relational logic in SMT where relations of arity n are defined as sets of n-tuples with parametrized sorts for tuple elements. We define a version of this logic as a first-order theory of finite relations where relation terms are built from relation constants and variables, set operators, and relational operators such as join, transpose, product, and transitive closure. We also present a deductive calculus for that theory and provide proofs of refutation soundness and model soundness of our calculus. In addition, we implement the calculus as a relational solver in the SMT solver CVC4, expanding its already large set of built-in theories, and evaluate the relational solver in two applications: Alloy and Ontology, showing promising results.
Moreover, with the goal of improving the performance of SMT solvers in general, we present a symmetry detection algorithm to detect symmetries in SMT formulas and present a symmetry breaking algorithm to generate blocking constraints that eliminate those symmetries. We then discuss an experimental evaluation of our implementation of these algorithms in CVC4 against SMT-LIB benchmarks.
23
Al-Saedi, Mohammad Saleh Balasim. "Extensions of tractable classes for propositional satisfiability." Thesis, Artois, 2016. http://www.theses.fr/2016ARTO0405/document.
Full textAbstract:
La représentation des connaissances et les problèmes d’inférence associés restent à l’heure actuelle une problématique riche et centrale en informatique et plus précisément en intelligence artificielle. Dans ce cadre, la logique propositionnelle permet d’allier puissance d’expression et efficacité. Il reste que, tant que P est différent de NP, la déduction en logique propositionnelle ne peut admettre de solutions à la fois générales et efficaces. Dans cette thèse, nous adressons le problème de satisfiabilité et proposons de nouvelles classes d’instances pouvant être résolues de manière polynomiale.La découverte de nouvelles classes polynomiales pour SAT est à la fois importante d’un point de vue théorique et pratique. En effet, on peut espérer les exploiter efficacement au sein de solveurs SAT. Dans cette thèse, nous proposons d’étendre deux fragments polynomiaux de SAT à l’aide de la propagation unitaire tout en s’assurant que ces fragments demeurent reconnus et résolus de manière polynomiale. Le premier résultat de cette thèse concerne la classe Quad. Nous avons établi certaines propriétés de cette classe d’instances et avons étendu cette dernière de manière à s’abstraire de l’ordre imposé sur les littéraux. Le fragment obtenu en remplaçant cet ordre par différents ordres sur les clauses, conserve lamême complexité dans le pire cas. Nous avons également étudié l’impact de la résolution bornée et de la redondance par propagation unitaire sur cette classe. La seconde contribution concerne la classe polynomiale proposée par Tovey. La propagation unitaire est une nouvelle fois utilisée pour étendre cette classe. Nous comparons le nouveau fragment polynomial obtenu à deux autres classes basées également sur la propagation unitaire : Quad et UP-Horn. Nousapportons également une réponse à une question ouverte au sujet des connexions de ces classes. Nous montrons que UP-Horn et d’autres classes basées sur la propagation unitaire sont strictement incluses dans S Quad qui représente l’union de toutes les classes Quad obtenues par l’exploitation de tous les ordres sur les clauses possiblesKnowledge representation and reasoning is a key issue in computer science and more particularly in artificial intelligence. In this respect, propositional logic is a representation formalism that is a good trade-off between the opposite computational efficiency and expressiveness criteria. However, unless P = NP, deduction in propositional logic is not polynomial in the worst case. So, in this thesis we propose new extensions of tractable classes of the propositional satisfiability problem. Tractable fragments of SAT play a role in the implementation of the most efficient current SAT solvers, many of thesetractable classes use the linear time unit propagation (UP) inference rule. We attempt to extend two of currently-known polynomial fragments of SAT thanks to UP in such a way that the fragments can still be recognized and solved in polynomial time. A first result focuses on Quad fragments: we establish some properties of Quad fragments and extend these fragments and exhibit promising variants. The extension is obtained by allowing Quad fixed total orderings of clauses to be accompanied with specific additional separate orderings of maximal sub-clauses. The resulting fragments extend Quad without degrading its worst-case complexity. Also, we investigate how bounded resolution and redundancy through unit propagation can play a role in this respect. The second contribution on tractable subclasses of SAT concerns extensions of one well-known Tovey’s polynomial fragment so that they also include instances that can be simplified using UP. Then, we compare two existing polynomial fragments based on UP: namely, Quad and UP-Horn. We also answer an open question about the connections between these two classes: we show that UP-Horn and some other UP-based variants are strict subclasses of S Quad, where S Quad is the union of all Quad classes obtained by investigating all possible orderings of clauses
24
Schwerdtfeger, Konrad W. [Verfasser]. "Connectivity of Boolean satisfiability / Konrad W. Schwerdtfeger." Hannover : Technische Informationsbibliothek (TIB), 2016. http://d-nb.info/1116960338/34.
Full text
25
Schewe, Lars [Verfasser]. "Satisfiability Problems in Discrete Geometry / Lars Schewe." Aachen : Shaker, 2007. http://d-nb.info/1166509400/34.
Full text
26
Council, Steven Michael. "A 'satisfiability' based approach to integer programming." Thesis, University of Southampton, 1999. https://eprints.soton.ac.uk/50600/.
Full textAbstract:
The purpose of this work is the development of a collection of satisfiability based algorithms that can be used to solve particular instances of integer programming problems. Satisfiability based algorithms have recently obtained a strong standing within the industrial community and, although for all but a few special cases the problem is NP-complete, research has shown that other problems in this class can often be transformed into a corresponding satisfiability problem and solved more effectively using the best SAT-solvers. One of the most important uses of satisfiability based algorithms is within chip design testing, such as the floating point failure of Pentium processors which require the need of efficient satisfiability based tools to aid in the verification process. We start with the case of Pure 0-1 Integer Programming problems and show how they can be transformed into a general satisfiability problem and solved using an algorithm developed by Davis, Putnam and Loveland. The thesis then concerns itself with making the process as efficient as possible by adopting a number of approaches that include the implementation of polynomial time algorithms including 'Incremental Satisfiability', allowing flexibility to add new branching strategies and the conversion of constraints to logical clauses. The programs are compiled to interact with each other fully and are tested on the 'truss design problem' found in structural engineering.
27
Fang, Lei. "Exploring Constraint Satisfiability Techniques in Formal Verification." Diss., Virginia Tech, 2008. http://hdl.handle.net/10919/27573.
Full textAbstract:
Due to the 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 problems. A hybrid solution to boost SAT solver performance is proposed as an initial attack in this dissertation, via an integration of local and DPLL-based search approaches.
Next, a different hybrid strategy is attempted that takes advantage of the conflicts in the SAT search, which plays a critical role in modern SAT solvers. Usually a learned conflict-induced clause is added back to the clause database. Although conflict-induced clauses help to block a portion of the search space, they can also become a burden due to the added cost in memory consumption and Boolean Constraint Propagation (BCP). We thus propose a novel double-layer conflict-driven learning to store only those "primary" conflict clauses back into the clause database while keeping the other clauses as pseudo Boolean constraints. With this approach our experiments demonstrate that the approach can improve both in performance and memory consumption. This work opens the door on how to assess the usefulness of conflict induced clauses.
Besides the aforementioned works about enhancing SAT solver performance and reducing memory cost, this dissertation also proposed a contributing work on the extended SAT problem solving. The current SAT solvers can provide an assignment for a satisfiable propositional formula. However, the capability for a SAT solver to return an "optimal" solution for a given objective function is severely lacking. MIN-ONE SAT is an optimization problem which requires the satisfying assignment with the minimal number of Ones, and it can be easily extended to minimize an arbitrary linear objective function. While some research has been conducted on MIN-ONE SAT, the existing algorithms do not scale very well on large formulas. This dissertation presents a novel approximation algorithm (RelaxSAT) for MIN-ONE SAT. RelaxSAT generates a set of constraints from the objective function to guide the search. The constraints are gradually relaxed to eliminate the conflicts with the original Boolean SAT formula until a solution is found. The experiments demonstrate that RelaxSAT is able to handle very large instances which cannot be solved by existing MIN-ONE algorithms; furthermore, RelaxSAT is able to obtain a very tight bound on the solution with one to two orders of magnitude speedup.
Based on the proposed powerful MIN-ONE SAT algorithm, we built a MAX-SAT solver which achieved more than one order of magnitude speed up compared with the-state-of-art MAX-SAT solver. We also discuss a promising application of this MAX-SAT solver in formal verification.Ph. D.
28
Reynolds, Andrew Joseph. "Finite model finding in satisfiability modulo theories." Diss., University of Iowa, 2013. https://ir.uiowa.edu/etd/5047.
Full textAbstract:
In recent years, Satisfiability Modulo Theories (SMT) solvers have emerged as powerful tools in many formal methods applications, including verification, automated theorem proving, planning and software synthesis. The expressive power of SMT allows problems from many disciplines to be handled in a single unified approach. While SMT solvers are highly effective at handling certain classes of problems due to highly tuned implementations of efficient ground decision procedures, their ability is often limited when reasoning about universally quantified first-order formulas. Since generally this class of problems is undecidable, most SMT solvers use heuristic techniques for answering unsatisfiable when quantified formulas are present. On the other hand, when the problem is satisfiable, solvers using these techniques will either run indefinitely, or give up after some predetermined amount of effort. In a majority of formal methods applications, it is critical that the SMT solver be able to determine when such a formula is satisfiable, especially when it can return some representation of a model for the formula. This dissertation introduces new techniques for finding models for SMT formulas containing quantified first-order formulas. We will focus our attention on finding finite models, that is, models whose domain elements can be represented as a finite set. We give a procedure that is both finite model complete and refutationally complete for a fragment of first-order logic that occurs commonly in practice.
29
Suy, Franch Josep. "A satisfiability modulo theories approach to constraint programming." Doctoral thesis, Universitat de Girona, 2012. http://hdl.handle.net/10803/98302.
Full textAbstract:
In this thesis we focus on solving CSPs using SMT. Essentially, what we do is reformulating CSPs into SMT. The obtained results allow us to conclude that state-of-the-art SMT solvers are a robust tool to solve CSPs. We tackle not only decisional CSPs, but also Constraint Optimization Problems and Weighted Constraint Satisfaction Problems. For solving these problems we have used SMT in conjunction with appropriated algorithms: search algorithms and UNSAT core-based algorithms. We have provided support for meta-constraints that is, constraints on constraints. Meta-constraints can be very helpful in the modelling process. Once verified that SMT is a good generic approximation for CP, we tested how algorithms built on top of an SMT solver can have equal or better performance than ad-hoc programs designed specifically for a given problem. The problem that we have selected to make this test is the RCPSP, obtaining highly competitive results.Aquesta tesi es centra en la resolució de CSPs utilitzant SMT. En essència, es reformulen els CSPs a fórmules SMT. Els resultats obtinguts permeten concloure que els millors solucionadors actuals d'SMT són una eina sòlida per a resoldre CSPs. No només s'aborden els CSP decisionals, sinó també problemes d'optimització de restriccions i problemes de satisfactibilitat de restriccions amb pesos. Per a resoldre aquests problemes s'ha utilitzat SMT juntament amb els algorismes apropiats: algorismes de cerca i algorismes basats en nuclis d'insatisfactibilitat. També es dóna suport a meta-restriccions, és a dir, restriccions sobre restriccions. Un cop vist que SMT és una molt bona aproximació genèrica per a CP, s'ha comprovat com algorismes basats en SMT poden tenir un rendiment igual o millor que els programes dissenyats específicament per a un determinat problema. El problema seleccionat per a dur a terme aquesta comprovació ha estat el RCPSP, obtenint uns resultats altament competitius.
30
Soler, Cabrejas Juan Ramón. "New Solving Techniques for Maximum and Minimum Satisfiability." Doctoral thesis, Universitat Autònoma de Barcelona, 2021. http://hdl.handle.net/10803/671710.
Full textAbstract:
El problema de la Satisfactibilitat (SAT) consisteix a decidir si existeix una assignació de valors de veritat que satisfaci una fórmula proposicional donada. SAT va ser el primer problema per al qual es va demostrar la seva NP-completitud, sent un dels problemes més estudiats en Ciències de la Computació. D'altra banda, MaxSAT i MinSAT són versions d'optimització de SAT en les quals l'objectiu és trobar una assignació que maximitzi o minimitzi el nombre de clàusules satisfetes, respectivament. Aquests problemes són importants perquè molts problemes pràctics poden codificar-se com a problemes SAT, MaxSAT o MinSAT, i resoldre's utilitzant un resolvedor SAT, MaxSAT o MinSAT. Mentre que SAT s'utilitza per resoldre problemes de decisió, MaxSAT i MinSAT s'utilitzen per resoldre problemes d'optimització.
L'objectiu general d'aquesta tesi doctoral és avançar en l'estat de l'art en la resolució de problemes d'optimització computacionalment difícils via la seva reducció a MaxSAT i MinSAT. Per aconseguir aquest objectiu, hem investigat nous sistemes d'inferència per MaxSAT i MinSAT basats en tableaux semàntics, i definit codificacions adequades per a noves aplicacions MaxSAT.
Quant als sistemes d'inferència, la tesi defineix un càlcul de tableaux complet per MaxSAT clausal, un càlcul de tableaux complet per MinSAT clausal i un càlcul de tableaux complet que permet resoldre tant MaxSAT com MinSAT. A més, la tesi proposa dos enfocaments diferents per a resoldre MaxSAT no clausal i MinSAT no clausal: en el primer enfocament, la tesi defineix transformacions de MaxSAT no clausal a MaxSAT clausal que preserven el cost. Aquestes transformacions s'estenen després per a definir transformacions de MinSAT no clausal a MinSAT clausal. En el segon enfocament, la tesi defineix un càlcul de tableaux per MaxSAT no clausal i demostra la seva consistència i completitud. També descriu com el càlcul de tableaux per MaxSAT no clausal es pot utilitzar per resoldre MinSAT no clausal.
Pel que fa a les noves aplicacions de MaxSAT, la tesi defineix codificacions MaxSAT pel problema de composició d'equips en una aula, les avalua empíricament i demostra que aquest problema és NP-dur. Els coneixements adquirits són útils per resoldre altres problemes d'optimització mitjançant la seva reducció a MaxSAT. En particular, la tesi mostra com resoldre problemes de formació d'equips més complexos, utilitzant el model de composició d'equips sinèrgics com a cas d'estudi.El problema de la Satisfacibilidad (SAT) consiste en decidir si existe una asignación de valores de verdad que satisfaga una fórmula proposicional dada. SAT fue el primer problema para el cual se demostró su NP-completitud, siendo uno de los problemas más estudiados en Ciencias de la Computación. Por otro lado, MaxSAT y MinSAT son versiones de optimización de SAT en las cuales el objetivo es encontrar una asignación que maximice o minimice el número de cláusulas satisfechas, respectivamente. Estos problemas son importantes porque muchos problemas prácticos pueden codificarse como problemas SAT, MaxSAT o MinSAT, y resolverse utilizando un resolvedor para SAT, MaxSAT o MinSAT. Mientras SAT se utiliza para resolver problemas de decisión, MaxSAT y MinSAT se utilizan para resolver problemas de optimización. El objetivo general de esta tesis doctoral es avanzar en el estado del arte en la resolución de problemas de optimización computacionalmente difíciles via su reducción a MaxSAT y MinSAT. Para lograr este objetivo, hemos estudiado nuevos sistemas de inferencia para MaxSAT y MinSAT basados en tableaux semánticos, y hemos definido codificaciones adecuadas para problemas que todavía no habían sido resueltos mediante su reducción a MaxSAT y MinSAT. En cuanto a los sistemas de inferencia, la tesis define un cálculo de tableaux completo para MaxSAT clausal, un cálculo de tableaux completo para MinSAT clausal y un cálculo de tableaux completo que permite resolver tanto MaxSAT como MinSAT. Además, la tesis propone dos enfoques diferentes para resolver MaxSAT no clausal y MinSAT no clausal: en el primer enfoque, la tesis define transformaciones de MaxSAT no clausal a MaxSAT clausal que preservan el coste. Además, define la extensión de estas transformaciones de MinSAT no clausal a MinSAT clausal. En el segundo enfoque, la tesis define un cálculo de tableaux para MaxSAT no clausal y demuestra su consistencia y completud. También describe cómo el cálculo de tableaux para MaxSAT no clausal puede utilizarse para resolver MinSAT no clausal. En cuanto a las nuevas aplicaciones de MaxSAT, la tesis define codificaciones MaxSAT para el problema de composición de equipos en un aula, las evalúa empíricamente y demuestra que este problema es NP-duro. Los conocimientos adquiridos son útiles para resolver otros problemas de optimización con tecnología MaxSAT. En particular, la tesis muestra cómo resolver problemas de formación de equipos más complejos, utilizando el modelo de composición de equipos sinérgicos como caso de estudio.
The Satisfiability problem, or SAT, is the problem of deciding if there exists an assignment that satisfies a given propositional formula. SAT was the first problem proven to be NP-complete and is one of the most studied problems in Computer Science. On the other hand, MaxSAT and MinSAT are optimization versions of SAT where the goal is to find an assignment that maximizes or minimizes the number of satisfied clauses, respectively. All these problems are significant because many practical problems can be encoded as SAT, MaxSAT or MinSAT problems, and solved using a SAT, MaxSAT or MinSAT solver. While SAT is used to solve decision problems, MaxSAT and MinSAT are used to solve optimization problems. The general objective of this PhD thesis is to advance the state of the art in solving computationally difficult optimization problems by reducing them to MaxSAT and MinSAT. To achieve this objective, we have investigated new inference systems for MaxSAT and MinSAT based on semantic tableaux, and suitable encodings for new MaxSAT applications. Regarding inference systems, the thesis defines a complete tableau calculus for solving clausal MaxSAT, a complete tableau calculus for solving clausal MinSAT and a complete tableau calculus for solving both clausal MaxSAT and clausal MinSAT. Moreover, the thesis proposes two different approaches to solving non-clausal MaxSAT and non-clausal MinSAT: in the first approach, the thesis defines novel cost-preserving transformations from non-clausal MaxSAT to clausal MaxSAT. Such transformations are then extended to define cost-preserving transformations from non-clausal MinSAT to clausal MinSAT. In the second approach, the thesis defines a genuine tableau calculus for non-clausal MaxSAT and proves its soundness and completeness. It also describes how the tableau calculus for non-clausal MaxSAT can be used to solve non-clausal MinSAT. Regarding new MaxSAT applications, the thesis defines and empirically evaluates MaxSAT encodings for the team composition problem in a classroom and proves that this problem is NP-hard. The insights gained are useful for solving other challenging optimization problems via their reduction to MaxSAT. In particular, the thesis shows how to solve more complex team formation problems, using the synergistic team composition model as a case study.
31
Zeranski, Robert [Verfasser]. "Satisfiability Characterizations of Upward Planarity Problems / Robert Zeranski." München : Verlag Dr. Hut, 2014. http://d-nb.info/105155053X/34.
Full text
32
Achlioptas, Demetrios. "Threshold phenomena in random graph colouring and satisfiability." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0002/NQ41090.pdf.
Full text
33
Gaur, Daya Ram. "Satisfiability and self-duality of monotone boolean functions." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0026/NQ51863.pdf.
Full text
34
Li, Bing. "Satisfiability-based abstraction refinement in symbolic model checking." Diss., Connect to online resource, 2006. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3207696.
Full text
35
Uhler, Richard Stephen. "Smten and the art of satisfiability-based search." Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/92967.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 177-182).
Satisfiability (SAT) and Satisfiability Modulo Theories (SMT) have been leveraged in solving a wide variety of important and challenging combinatorial search problems, including automatic test generation, logic synthesis, model checking, program synthesis, and software verification. Though in principle SAT and SMT solvers simplify the task of developing practical solutions to these hard combinatorial search problems, in practice developing an application that effectively uses a SAT or SMT solver can be a daunting task. SAT and SMT solvers have limited support, if any, for queries described using the wide array of features developers rely on for describing their programs: procedure calls, loops, recursion, user-defined data types, recursively defined data types, and other mechanisms for abstraction, encapsulation, and modularity. As a consequence, developers cannot rely solely on the sophistication of SAT and SMT solvers to efficiently solve their queries; they must also optimize their own orchestration and construction of queries. This thesis presents Smten, a search primitive based on SAT and SMT that supports all the features of a modern, general purpose functional programming language. Smten exposes a simple yet powerful search interface for the Haskell programming language that accepts user-level constraints directly. We address the challenges of supporting general purpose, Turing-complete computation in search descriptions, and provide an approach for eciently evaluating Smten search using SAT and SMT solvers. We show that applications developed using Smten require significantly fewer lines of code and less developer effort for results comparable to standard SMT-based tools.
by Richard S. Uhler.
Ph. D.
36
Ragno, Robert J. (Robert John) 1977. "Solving optimal satisfiability problems through clause-directed A*." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/29242.
Full textAbstract:
Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.Includes bibliographical references (p. 37-38).
Real-world applications, such as diagnosis and embedded control, are increasingly being framed as OpSAT problems - problems of finding the best solution that satisfies a formula in propositional state logic. Previous methods, such as Conflict-directed A*, solve OpSAT problems through a weak coupling of A* search, used to generate optimal candidates, and a DPLL-based SAT solver, used to test feasibility. This paper achieves a substantial performance improvement by introducing a tightly coupled approach, Clause-directed A * (CIA *). ClA* simultaneously directs the search towards assignments that are feasible and optimal. First, satisfiability is generalized to state logic by unifying the DPLL satisfiability procedure with forward checking. Second, optimal assignments are found by using A* to guide variable splitting within DPLL. Third, search is directed towards feasible regions of the state space by treating all clauses as conflicts, and by selecting only assignments that entail more clauses. Finally, ClA* climbs towards the optimum by using a variable ordering heuristic that emulates gradient search. Empirical experiments on real-world and randomly-generated instances demonstrate an order of magnitude increase in performance over Conflict-directed A*.
by Robert J. Ragno.
M.Eng.
37
Purcell, Christopher. "Cliques, colouring and satisfiability : from structure to algorithms." Thesis, University of Warwick, 2013. http://wrap.warwick.ac.uk/60496/.
Full textAbstract:
We examine the implications of various structural restrictions on the computational complexity of three central problems of theoretical computer science (colourability, independent set and satisfiability), and their relatives. All problems we study are generally NP-hard and they remain NP-hard under various restrictions. Finding the greatest possible restrictions under which a problem is computationally difficult is important for a number of reasons. Firstly, this can make it easier to establish the NP-hardness of new problems by allowing easier transformations. Secondly, this can help clarify the boundary between tractable and intractable instances of the problem. Typically an NP-hard graph problem admits an infinite sequence of narrowing families of graphs for which the problem remains NP-hard. We obtain a number of such results; each of these implies necessary conditions for polynomial-time solvability of the respective problem in restricted graph classes. We also identify a number of classes for which these conditions are sufficient and describe explicit algorithms that solve the problem in polynomial time in those classes. For the satisfiability problem we use the language of graph theory to discover the very first boundary property, i.e. a property that separates tractable and intractable instances of the problem. Whether this property is unique remains a big open problem.
38
Hansen, Stephen Lee. "Complete Randomized Cutting Plane Algorithms for Propositional Satisfiability." NSUWorks, 2000. http://nsuworks.nova.edu/gscis_etd/565.
Full textAbstract:
The propositional satisfiability problem (SAT) is a fundamental problem in computer science and combinatorial optimization. A considerable number of prior researchers have investigated SAT, and much is already known concerning limitations of known algorithms for SAT. In particular, some necessary conditions are known, such that any algorithm not meeting those conditions cannot be efficient. This paper reports a research to develop and test a new algorithm that meets the currently known necessary conditions.
In chapter three, we give a new characterization of the convex integer hull of SAT, and two new algorithms for finding strong cutting planes. We also show the importance of choosing which vertex to cut, and present heuristics to find a vertex that allows a strong cutting plane. In chapter four, we describe an experiment to implement a SAT solving algorithm using the new algorithms and heuristics, and to examine their effectiveness on a set of problems. In chapter five, we describe the implementation of the algorithms, and present computational results. For an input SAT problem, the output of the implemented program provides either a witness to the satisfiability or a complete cutting plane proof of satisfiability. The description, implementation, and testing of these algorithms yields both empirical data to characterize the performance of the new algorithms, and additional insight to further advance the theory. We conclude from the computational study that cutting plane algorithms are efficient for the solution of a large class of SAT problems.
39
Großmann, Peter. "Satisfiability and Optimization in Periodic Traffic Flow Problems." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2016. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-213122.
Full textAbstract:
Automatically calculating periodic timetables in public railway transport systems is an NP-complete problem – namely the Periodic Event Scheduling Problem (PESP). The original model is restricted to basic periodic timetabling. Extending the model by decisional transport networks with flows induces new possibilities in the timetabling and planning process. Subsequently, the given flexibility results in a generic model extension of PESP that can be applied in subsets of the timetabling process. The successful utilization of this approach is presented for distinct chain paths, duplicated chain paths and non-connected flow graphs that represent integration of routing and timetabling, planning of periodic rail freight train paths and track allocation, respectively. Furthermore, the encoding of this generic model into a binary propositional formula is introduced and 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.
40
Pon, Farreny Josep. "Contributions to automatic configuration and selection for satisfiability." Doctoral thesis, Universitat de Lleida, 2021. http://hdl.handle.net/10803/673622.
Full textAbstract:
En l’àrea de les ciències de la computació, és sabut que els algoritmes poden exhibir comportaments completament diferents depenent de com estiguin configurats els seus paràmetres, fet que s’aguditza quan els problemes que s’aborden són NPComplets. Per exemple, s’ha demostrat experimentalment que configurar solvers pels problemes de la SATisfactibilitat (SAT), la Màxima SATisfactibilitat (MaxSAT) o la programació lineal d’enters mixta (MIP), pot resultar en millores d’ordres de
magnitud.
En aquesta tesi, mostrem com algoritmes metaheurístics configurats de manera automàtica poden resoldre de forma eficient diverses families d’instancies industrials i artificails del problema MaxSAT. A continuació, ens centrem a millorar el configurador automàtic d’algoritmes GGA proporcionant un nou configurador distribuït que el supera en diverses famílies d’instancis industrials i artificials dels problemes SAT i MIP.
Finalment, per fer aquesta tecnologia més accessible a totes les comunitats científiques i la indústria, presentem l’eina PyDGGA que implementa el nostre nou configurador. A més, presentem el paquet OptiLog, el qual permet la creació ràpida de sistemes basats en SAT que addicionalment incorpora un mòdul de configuració automàtica per facilitar l’ús de diverses eines de configuració.En el área de las ciencas de la computación, es sabido que los algoritmos pueden exhibir comportamientos completamente diferentes dependiendo de como estén configurados sus parámetros, agudizándose este fenómeno cuando los problemas que se abordan son NP-Completos. Por ejemplo, se ha demostrado experimentalmente que configurar solvers para los problemas de la SATisfactibilidad (SAT), la Maxima SATisfactibilidad (MaxSAT) o la programación lineal de enteros mixta (MIP), puede resultar en mejoras de órdenes de magnitud. En esta tesis, mostramos cómo algoritmos metaheurísticos configurados de manera automática pueden resolver de forma eficiente diversas familias de instancias industriales y artificiales del problema MaxSAT. A continuación, nos centramos en mejorar el configurador automático de algoritmos GGA proporcionando un nuevo configurador distribuido que lo supera en varias familias de instancias industriales y artificiales de los problemas SAT y MIP. Finalmente, para hacer que esta tecnología sea más accesible para todas las comunidades científicas y la industria, presentamos la herramienta PyDGGA que implementa nuestro nuevo configurador. Además, presentamos el paquete OptiLog el cual permite la creación rápida de sistemas basados en SAT que adicionalmente incorpora un módulo de configuración automática para facilitar el uso de varias herramientas de configuración.
Within the computer science community, it is well known that algorithms may exhibit completely different behaviours depending on how their parameters are configured. This is even more obvious when the problems being tackled are NP-Complete. For example it has been proved experimentally that configuring solvers for the SATisfiabilty (SAT) problem, the Maximum SATisfiability (MaxSAT) problem or for Mixed Integer Programming (MIP), can result in improvements of orders of magnitude. In this thesis, we show how automatically configured metahueristic algorithms can efficiently solve families of industrial and crafted instances of the MaxSAT problem. Then, we focus on improving the automatic algorithm configurator GGA providing a new distributed configurator which outperforms GGA on families of industrial and crafted SAT and MIP instances. Finally, in our aim of making this technology more accessible for all research communities and industry we present the tool PyDGGA that implements our new configurator. We additionally introduce the OptiLog framework for rapid prototyping of SAT-based systems that also incorporates a module for automatic configuration for the easy application of several configuration tools.
41
SIVA, SUBRAMANYAN D. "APPLICATIONS OF SATISFIABILITY IN SYNTHESIS OF RECONFIGURABLE COMPUTERS." University of Cincinnati / OhioLINK, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1022761893.
Full text
42
Pari, Pushkin Raj. "Several issues on the boolean satisfiability (SAT) problem." College Park, Md. : University of Maryland, 2004. http://hdl.handle.net/1903/1427.
Full textAbstract:
Thesis (M.S.) -- University of Maryland, College Park, 2004.Thesis research directed by: Dept. of Electrical Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
43
Roy, Amitabha. "Symmetry breaking and fault tolerance in boolean satisfiability /." view abstract or download file of text, 2001. http://wwwlib.umi.com/cr/uoregon/fullcit?p3024528.
Full textAbstract:
Thesis (Ph. D.)--University of Oregon, 2001.Typescript. Includes vita and abstract. Includes bibliographical references (leaves 124-127). Also available for download via the World Wide Web; free to University of Oregon users.
44
Duong, Thach-Thao Nguyen. "Improving Diversification in Local Search for Propositional Satisfiability." Thesis, Griffith University, 2014. http://hdl.handle.net/10072/365717.
Full textAbstract:
In recent years, the Propositional Satisfiability (SAT) has become standard for encoding real world complex constrained problems. SAT has significant impacts on various research fields in Artificial Intelligence (AI) and Constraint Programming (CP). SAT algorithms have also been successfully used in solving many practical and industrial applications that include electronic design automation, default reasoning, diagnosis, planning, scheduling, image interpretation, circuit design, and hardware and software verification. The most common representation of a SAT formula is the Conjunctive Normal Form (CNF). A CNF formula is a conjunction of clauses where each clause is a disjunction of Boolean literals. A SAT formula is satisfiable if there is a truth assignment for each variable such that all clauses in the formula are satisfied. Solving a SAT problem is to determine a truth assignment that satisfies a CNF formula. SAT is the first problem proved to be NP-complete [20]. There are many algorithmic methodologies to solve SAT. The most obvious one is systematic search; however another popular and successful approach is stochastic local search (SLS). Systematic search is usually referred to as complete search or backtrack-style search. In contrast, SLS is a method to explore the search space by randomisation and perturbation operations. Although SLS is an incomplete search method, it is able to find the solutions effectively by using limited time and resources. Moreover, some SLS solvers can solve hard SAT problems in a few minutes while these problems could be beyond the capacity of systematic search solvers.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Science, Environment, Engineering and Technology
Full Text
45
Mover, Sergio. "Verification of Hybrid Systems using Satisfiability Modulo Theories." Doctoral thesis, Università degli studi di Trento, 2014. https://hdl.handle.net/11572/368887.
Full textAbstract:
Embedded systems are formed by hardware and software
components that interact with the physical environment and thus may be modeled as Hybrid Systems. Due to the complexity the system,there is an increasing need of automatic techniques to support the design phase, ensuring that a system behaves as expected in all the possible operating conditions.In this thesis, we propose novel techniques for the verification and the validation of hybrid systems using Satisfiability Modulo Theories (SMT).
SMT is an established technique that has been used successfully in many verification approaches, targeted for both hardware and software systems.
The use of SMT to verify hybrid systems has been limited,
due to the restricted support of complex continuous dynamics and the lack
of scalability.
The contribution of the thesis is twofold.
First, we propose novel encoding techniques, which widen the
applicability and improve the effectiveness of the SMT-based
approaches.
Second, we propose novel SMT-based algorithms that improve the
performance of the existing state of the art approaches.
In particular we show algorithms to solve problems such as
invariant verification, scenario verification and parameter synthesis.
The algorithms fully exploit the underlying structure of a
network of hybrid systems and the functionalities of modern
SMT-solvers.
We show and discuss the effectiveness of the the proposed techniques
when applied to benchmarks from the hybrid systems domain.
46
Mover, Sergio. "Verification of Hybrid Systems using Satisfiability Modulo Theories." Doctoral thesis, University of Trento, 2014. http://eprints-phd.biblio.unitn.it/1177/1/main.pdf.
Full textAbstract:
Embedded systems are formed by hardware and software
components that interact with the physical environment and thus may be modeled as Hybrid Systems. Due to the complexity the system,there is an increasing need of automatic techniques to support the design phase, ensuring that a system behaves as expected in all the possible operating conditions.In this thesis, we propose novel techniques for the verification and the validation of hybrid systems using Satisfiability Modulo Theories (SMT).
SMT is an established technique that has been used successfully in many verification approaches, targeted for both hardware and software systems.
The use of SMT to verify hybrid systems has been limited,
due to the restricted support of complex continuous dynamics and the lack
of scalability.
The contribution of the thesis is twofold.
First, we propose novel encoding techniques, which widen the
applicability and improve the effectiveness of the SMT-based
approaches.
Second, we propose novel SMT-based algorithms that improve the
performance of the existing state of the art approaches.
In particular we show algorithms to solve problems such as
invariant verification, scenario verification and parameter synthesis.
The algorithms fully exploit the underlying structure of a
network of hybrid systems and the functionalities of modern
SMT-solvers.
We show and discuss the effectiveness of the the proposed techniques
when applied to benchmarks from the hybrid systems domain.
47
Cherif, Mohamed Sami. "Reasoning and inference for (maximum) satisfiability : new insights." Electronic Thesis or Diss., Aix-Marseille, 2022. http://www.theses.fr/2022AIXM0589.
Full textAbstract:
Au cœur de l'informatique et de l'intelligence artificielle, la logique est souvent utilisée comme un langage pour modéliser et résoudre des problèmes complexes issus du milieu académique ou d'applications industrielles. Un formalisme bien connu dans ce contexte est le problème de satisfiabilité (SAT) qui vérifie simplement si une formule propositionnelle donnée sous la forme d'un ensemble de contraintes, appelées clauses, peut être satisfaite. Une extension naturelle de SAT en problème d'optimisation est la satisfiabilité maximum (Max-SAT), qui consiste à déterminer le nombre maximal de contraintes clausales pouvant être satisfaites dans la formule. Dans nos travaux, on s'intéresse à l'étude du pouvoir et des limites de l'inférence et du raisonnement dans le contexte de ces deux paradigmes. Nos premières contributions tournent autour de l'étude de l'inférence dans le cadre des algorithmes de résolution pour SAT et Max-SAT. Tout d'abord, nous étudions l'inférence statistique dans le cadre des solveurs modernes pour SAT qui sont basés sur l'apprentissage de clauses. On introduit un formalisme bandit manchot pour la sélection adaptative d'heuristiques de branchement et on montre qu'un tel mécanisme permet d'améliorer l'efficacité des solveurs modernes. De plus, nous investiguons minutieusement la puissance de l'inférence dans le cadre des algorithmes de type séparation et évaluation pour Max-SAT grâce à la propriété de l'UP-résilience. Nos contributions s'étendent également à la théorie des preuves pour SAT et Max-SAT, l'un de nos objectifs majeurs étant de combler le fossé théorique entre l'inférence SAT et Max-SATAt the heart of computer science and artificial intelligence, logic is often used as a powerful language to model and solve complex problems that arise in academia and in real-world applications. A well-known formalism in this context is the Satisfiability (SAT) problem which simply checks whether a given propositional formula in the form of a set of constraints, called clauses, can be satisfied. A natural optimization extension of this problem is maximum satisfiability (Max-SAT) which consists in determining the maximum number of clausal constraints that can be satisfied within the formula. In our work, we are interested in studying the power and limits of inference and resoning in the context of (Maximum) Satisfiability. Our first contributions revolve around investigating inference in SAT and Max-SAT solving. First, we study statistical inference within a Multi-Armed Bandit (MAB) framework for online selection of branching heuristics in SAT and we show that it can further enhance the efficiency of modern clause-learning solvers. Moreover, we provide further insights on the power of inference in Branch and Bound algorithms for Max-SAT solving through the property of UP-resilience. Our contributions also extend to SAT and Max-SAT proof theory. We particularly attempt to theoretically bridge the gap between SAT and Max-SAT inference
48
Ferreira, Junior Valnir, and N/A. "Improvements to Clause Weighting Local Search for Propositional Satisfiability." Griffith University. Institute for Integrated and Intelligent Systems, 2007. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070823.123257.
Full textAbstract:
The propositional satisfiability (SAT) problem is of considerable theoretical and practical relevance to the artificial intelligence (AI) community and has been used to model many pervasive AI tasks such as default reasoning, diagnosis, planning, image interpretation, and constraint satisfaction. Computational methods for SAT have historically fallen into two broad categories: complete search and local search. Within the local search category, clause weighting methods are amongst the best alternatives for SAT, becoming particularly attractive on problems where a complete search is impractical or where there is a need to find good candidate solutions within a short time. The thesis is concerned with the study of improvements to clause weighting local search methods for SAT. The main contributions are: A component-based framework for the functional analysis of local search methods. A clause weighting local search heuristic that exploits longer-term memory arising from clause weight manipulations. The approach first learns which clauses are globally hardest to satisfy and then uses this information to treat these clauses differentially during weight manipulation [Ferreira Jr and Thornton, 2004]. A study of heuristic tie breaking in the domain of additive clause weighting local search methods, and the introduction of a competitive method that uses heuristic tie breaking instead of the random tie breaking approach used in most existing methods [Ferreira Jr and Thornton, 2005]. An evaluation of backbone guidance for clause weighting local search, and the introduction of backbone guidance to three state-of-the-art clause weighting local search methods [Ferreira Jr, 2006]. A new clause weighting local search method for SAT that successfully exploits synergies between the longer-term memory and tie breaking heuristics developed in the thesis to significantly improve on the performance of current state-of-the-art local search methods for SAT-encoded instances containing identifiable CSP structure. Portions of this thesis have appeared in the following refereed publications: Longer-term memory in clause weighting local search for SAT. In Proceedings of the 17th Australian Joint Conference on Artificial Intelligence, volume 3339 of Lecture Notes in Artificial Intelligence, pages 730-741, Cairns, Australia, 2004. Tie breaking in clause weighting local search for SAT. In Proceedings of the 18th Australian Joint Conference on Artificial Intelligence, volume 3809 of Lecture Notes in Artificial Intelligence, pages 7081, Sydney, Australia, 2005. Backbone guided dynamic local search for propositional satisfiability. In
Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics, AI&M, Fort Lauderdale, Florida, 2006.
49
Pham, Duc Nghia, and n/a. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems." Griffith University. Institute for Integrated and Intelligent Systems, 2006. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070216.143447.
Full textAbstract:
Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].
50
Heller, Kelly K. "Satisfiability checking for quality assurance in relational data processing." Thesis, California State University, Long Beach, 2013. http://pqdtopen.proquest.com/#viewpdf?dispub=1524200.
Full textAbstract:
Developers using the SQL language lack relational SQL debugging tools. SQL also suffers from a lack of sufficient automated frameworks for unit testing and regression testing of queries. This thesis begins with an SQL bug taxonomy. The focus is on Core SQL as defined in the SQL:1999 standard. Features in Core SQL remain virtually unchanged through the latest standard, SQL:2011. Our bug taxonomy illustrates common coding defects related to NULL, LEFT JOIN, selectivity assumptions, and ordering assumptions. We highlight ways that silent failures can impact a databasedependent application. Our proposal for addressing SQL development errors is a verification tool (named POQ) that leverages annotated postconditions attached to each query statement. The formalism of domain relational calculus is the basis for axiomatizing queries. Subsequently, a theorem prover searches for counterexamples that demonstrate when the postcondition fails. Alternative projects using SMT solvers and static analysis methods are also discussed.