Dissertations / Theses on the topic 'SAT'
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 'SAT.'
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.
AXELSSON, LUDVIG, and TIM LINDEBERG. "SAT doku Att lösa Sudoku med moderna SAT-lösare." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-157550.
Full textSudoku is a popular puzzle game that originates from Japan. The Sudokuproblem has been shown to be NP-complete and therefore thereprobably does not exist an effecient way of solving large puzzles. In recentyears there has been a lot of research into solving the SAT problem.This report examined various SAT solvers from “The International SATCompetition” to investigate whether there exists a correlation betweenthe execution time and the difficulty level of puzzles and to determinewhich of these are most effective for solving puzzles of varying difficultyand size. To examine the above a large number of puzzles were generatedand two tests were performed. One test measured the executiontime of various SAT solvers when solving puzzles of varying difficulty.The second test measured the time that the SAT solvers took to solvepuzzles of different sizes. The tested SAT solvers are Glucose, Lingling,Minisat, Plingeling, Treengeling and Zenn.The results show a correlation between the execution time of theSAT solvers and the difficulty of the puzzles when looking at the averagetime of the solvers. A linear regression test gave a coefficent ofdetermination of approximately 0.8. Some solvers had a significant correlationand other solvers showed almost no correlation at all. Thecorrelation could also be attributed to the difference in the number ofclues between the puzzles. This however does not explain the disparitybetween puzzles of varying difficulty with the same number of clues.The average time for all solvers were approximately 20 ms for puzzlesof order three and about 50 s for puzzles of order nine. Of the testedSAT solvers, Minisat was the fastest at solving both the puzzles of orderthree and puzzles of higher order.
Szczepanski, Nicolas. "SAT en Parallèle." Thesis, Artois, 2017. http://www.theses.fr/2017ARTO0403/document.
Full textThis thesis deals with propositional satisfiability (SAT) in a massively parallel setting. The SAT problem is widely used for solving several combinatorial problems (e.g. formal verification of hardware and software, bioinformatics, cryptography, planning, scheduling, etc.). The first contribution of this thesis concerns the design of efficient algorithms based on the approaches « portfolio » and « divide and conquer ». Secondly, an adaptation of several parallel programming models including hybrid (parallel and distributed computing) to SAT is proposed. This work has led to several contributions to international conferences and highly competitive distributed SAT solvers
Lardeux, Frédéric. "Approches hybrides pour les problèmes de satisfiabilité (SAT et MAX-SAT)." Angers, 2005. http://www.theses.fr/2005ANGE0024.
Full textThis thesis deals with the resolution of the satisfiability problems SAT and MAX-SAT. Our contributions are in three types. First, we have developed the memetic algorithm GASAT for the SAT and MAX-SAT problems which hybridies a tabu algorithm and a genetic algorithm. Some specific tools for the satisfiability problems have been included in it such as intensification mechanisms, diversification mechanisms and a new crossover operator. Next, we have proposed a new resolution framework which permits the exact and the approached methods to handle the same representation of the search space. To do this, we have added a third truth value ``undetermined''. The results obtained by the tri-valued hybrid algorithms show the utility of this resolution framework. Finally, we are interested in the branching heuristics for the Branch and Bound algorithms in the MAX-SAT context. Our study shows that these heuristics react in different ways in function of the initial parameters, the structure of the studied instances and the improved mechanisms for Branch and Bound. The findings of this study may lead to the creation of new heuristics specifically dedicated to the MAX-SAT problem
André, Pascal. "Aspects probabilistes du probleme de la satisfaction d'une formule booleenne, etude des problemes sat, number-sat et max-sat." Paris 6, 1993. http://www.theses.fr/1993PA066681.
Full textDarras, Sylvain. "Traitements locaux dans les arbres de recherche pour SAT et max-SAT." Amiens, 2008. http://www.theses.fr/2008AMIE0120.
Full textThe difficulty of combinatorial problem resolution is mainly due to the exponential size of their search-space. The SAT and Max-SAT problems belong to this category. This thesis aims to increase resolution abilities of complete SAT and Max-SAT solvers, thanks to a better exploitation of information revealed all along the search-tree. About SAT, we propose a new study of the implication graph that allows to highlight possible subsumptions of existing clauses. The objective is to decrease the size of clauses belonging to the formula, in order to get them more expressive and efficient. Therefore, we develop a light computation of the implication graph, guided by the clause to subsume, finding a subsumption of this clause if there exists one. Our research on Max-SAT have focused on a better computation of the lower bound in Branch-and-Bound algorithms. Considering a solver whose lower bound estimation (or at least a part of it) relies on an inconsistent clause-set research, our approach aims to avoid repeated computation of equivalent inconsistent cores. Thanks to a storage of some of these inconsistent clause-sets from a node to its child-nodes, it is possible to reuse directly these elements without any new computation. Moreover, these cores increase the lower bound quality by keeping the efficient inconsistent sets
Bayless, Sam. "SAT modulo monotonic theories." Thesis, University of British Columbia, 2017. http://hdl.handle.net/2429/61062.
Full textScience, Faculty of
Computer Science, Department of
Graduate
Suteu, Silviu Cezar. "OPS-SAT Software Simulator." Thesis, Luleå tekniska universitet, Institutionen för system- och rymdteknik, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-59903.
Full textBierlee, Hendrik. "The MiniZinc-SAT Compiler." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-438608.
Full textONO, Takao, and Tomio HIRATA. "Approximation Algorithms for MAX SAT." Institute of Electronics, Information and Communication Engineers, 2000. http://hdl.handle.net/2237/15068.
Full textNguyen, Van-Hau. "SAT Encodings of Finite CSPs." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-162186.
Full textIzrael, Petr. "SAT Solver akcelerovaný pomocí GPU." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2013. http://www.nusl.cz/ntk/nusl-236336.
Full textGabàs, Masip Joel. "SAT-based approaches for constraint optimization." Doctoral thesis, Universitat de Lleida, 2016. http://hdl.handle.net/10803/396610.
Full textLa optimización con restricciones ha sido utilizada con éxito para resolver problemas en muchos dominios reales (industriales). Esta tesis se centra en las aproximaciones lógicas, concretamente en Máxima Satisfacibilidad (MaxSAT) que es la versión de optimización del problema de Satisfacibilidad booleana (SAT). A través de MaxSAT, se han resuelto muchos problemas de forma eficiente. Familias de instancias de la mayoría de ellos han sido sometidas a la MaxSAT Evaluation (MSE), creando así una colección pública y accesible de instancias de referencia. En las ediciones recientes de la MSE, los algoritmos SAT-based han sido las aproximaciones que han tenido un mejor comportamiento para las instancias industriales. Esta tesis está centrada en mejorar los algoritmos SAT-based. Nuestro trabajo ha contribuido a cerrar varias instancias abiertas y a reducir dramáticamente el tiempo de resolución en muchas otras. Además, hemos encontrado sorprendentemente que reformular y resolver el problema MaxSAT a través de programación lineal entera era especialmente adecuado para algunas familias. Finalmente, hemos desarrollado el primer portfolio altamente eficiente para MaxSAT que ha dominado en todas las categorías de la MSE desde 2013.
Constraint optimization has been successfully used to solve problems in many real world (industrial) domains. This PhD thesis is focused on logic-based approaches, in particular, on Maximum Satisfiability (MaxSAT) which is the optimization version of Satisfiability (SAT). There have been many problems efficiency solved through MaxSAT. Instance families on the majority of them have been submitted to the international MaxSAT Evaluation (MSE), creating a collection of publicly available benchmark instances. At recent editions of MSE, SAT-based algorithms were the best performing single algorithm approaches for industrial problems. This PhD thesis is focused on the improvement of SAT-based algorithms. All this work has contributed to close up some open instances and to reduce dramatically the solving time in many others. In addition, we have surprisingly found that reformulating and solving the MaxSAT problem through Integer Linear Programming (ILP) was extremely well suited for some families. Finally, we have developed the first highly efficient MaxSAT portfolio that dominated all categories of MSE since 2013.
Wedler, Markus. "Modellgenerierung für die SAT-basierte Eigenschaftsprüfung." [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=98098212X.
Full textGiráldez, Crú Jesús. "Beyond the Structure of SAT Formulas." Doctoral thesis, Universitat Autònoma de Barcelona, 2016. http://hdl.handle.net/10803/386422.
Full textNowadays, many real-world problems are encoded into SAT instances and efficiently solved by modern SAT solvers. These solvers, usually known as Conflict-Driven Clause Learning (CDCL) SAT solvers, include a variety of sophisticated techniques, such as clause learning, lazy data structures, conflict-based adaptive branching heuristics, or random restarts, among others. However, the reasons of their efficiency in solving real-world, or industrial, SAT instances are still unknown. The common wisdom in the SAT community is that these technique exploit some hidden structure of real-world problems. In this thesis, we characterize some important features of the underlying structure of industrial SAT instances. Namely, they are the community structure and the self-similar structure. We observe that most industrial SAT formulas, viewed as graphs, have these two properties. This means that~(i) in a graph with a clear community structure, i.e. having high modularity, we can find a partition of its nodes into communities such that most edges connect nodes of the same community; and~(ii) in a graph with a self-similar pattern, i.e. being fractal, its shape is kept after re-scalings, i.e., grouping sets of nodes into a single node. We also analyze how these structures are affected by the effects of CDCL techniques during the search. Using the previous structural studies, we propose three applications. First, we face the problem of generating pseudo-industrial random SAT instances using the notion of modularity. Our model generates instances similar to (classical) random SAT formulas when the modularity is low, but when this value is high, our model is also adequate to model realistic pseudo-industrial problems. Second, we propose a method based on the community structure of the instance to detect relevant learnt clauses. Our technique augments the original instance with this set of relevant clauses, and this results into an overall improvement of the efficiency of several state-of-the-art CDCL SAT solvers. Finally, we analyze the classification of industrial SAT instances into families using the previously analyzed structure features, and we compare them to other classifiers commonly used in portfolio SAT approaches. In summary, this \dissertation extends the understandings of the structure of SAT instances, with the aim of better explaining the success of CDCL techniques and possibly improve them, and propose a number of applications based on this analysis of the underlying structure of SAT formulas.
Asketorp, Jonatan. "Attacking RSA moduli with SAT solvers." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-157352.
Full textEmanuelsson, Kristoffer, and Ludvig Stenström. "Att lösa sudoku med SAT-lösare." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-157549.
Full textLundén, Daniel, and Erik Forsblom. "Factoring integers with parallel SAT solvers." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-166436.
Full textAtt faktorisera heltal är ett välkänt problem som för närvarande inte kan lösas i polynomisk tid. Därför är andra tillvägagångssätt för att lösa faktorisering av intresse. Ett sådant tillvägagångssätt är att reducera faktorisering till SAT och sedan lösa problemet med en dedikerad SAT-lösare. I denna studie undersöks parallella SAT-lösare i detta sammanhang och utvärderas i förhållande till uppsnabbning, effektivitet och ändamålsenlighet jämfört med sekventiella SAT-lösare. Den metod som användes var en experimentell sådan där olika parallella och sekventiella lösare jämfördes på olika reduktioner från heltalsfaktorisering till SAT. Genom testerna erhölls slutsatsen att parallella SAT-lösare inte är bättre lämpade för att lösa heltalsfaktorisering än sekventiella lösare. Prestandavinsterna som uppnåddes av den snabbaste parallella lösaren motsvarade knappt den extra mängd parallella resurser som denna hade över den snabbaste sekventiella lösaren.
Kokotov, Daniel (Daniel L. ). 1978. "PSolver : a distributed SAT solver framework." Thesis, Massachusetts Institute of Technology, 2001. http://hdl.handle.net/1721.1/86807.
Full textIncludes bibliographical references (p. 129-130).
by Daniel Kokotov.
M.Eng.and S.B.
Vimjam, Vishnu Chaithanya. "Strategies for SAT-Based Formal Verification." Diss., Virginia Tech, 2007. http://hdl.handle.net/10919/26078.
Full textPh. D.
Pilz, Enrico. "Boolsche Gleichungssysteme, SAT Solver und Stromchiffren." [S.l. : s.n.], 2008. http://nbn-resolving.de/urn:nbn:de:bsz:289-vts-65265.
Full textLe, Frioux Ludovic. "Towards more efficient parallel SAT solving." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS209.
Full textBoolean SATisfiability has been used successfully in many applicative contexts. This is due to the capability of modern SAT solvers to solve complex problems involving millions of variables. Most SAT solvers have long been sequential and based on the CDCL algorithm. The emergence of many-core machines opens new possibilities in this domain. There are numerous parallel SAT solvers that differ by their strategies, programming languages, etc. Hence, comparing the efficiency of the theoretical approaches in a fair way is a challenging task. Moreover, the introduction of a new approach needs a deep understanding of the existing solvers' implementations. We present Painless: a framework to build parallel SAT solvers for many-core environments. Thanks to its genericness and modularity, it provides the implementation of basics for parallel SAT solving. It also enables users to easily create their parallel solvers based on new strategies. Painless allowed to build and test existing strategies by using different chunk of solutions present in the literature. We were able to easily mimic the behaviour of three state-of-the-art solvers by factorising many parts of their implementations. The efficiency of Painless was highlighted as these implementations are at least efficient as the original ones. Moreover, one of our solvers won the SAT Competition'18. Going further, Painless enabled to conduct fair experiments in the context of divide-and-conquer solvers, and allowed us to highlight original compositions of strategies performing better than already known ones. Also, we were able to create and test new original strategies exploiting the modular structure of SAT instances
Cherif, Mohamed Sami. "Reasoning and inference for (maximum) satisfiability : new insights." Electronic Thesis or Diss., Aix-Marseille, 2022. http://www.theses.fr/2022AIXM0589.
Full textAt 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
Reis, Poliana Magalhães. "Análise da distribuição do número de operações de resolvedores SAT." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21012013-220441/.
Full textIn the study of computational complexity stand out two classes known as P and NP. The question P = NP is one of the greatest unsolved problems in theoretical computer science and contemporary mathematics. The SAT problem was first problem recognized as NP-complete and consists to check whether a certain formula of classical propositional logic is satisfiable or not. The implementations of algorithms to solve SAT problems are known as SAT solvers. There are several applications in computer science that can be performed with SAT solvers and other solvers NP- complete problems can be reduced to SAT problems such as graph coloring, scheduling problems and planning problems. Among the most efficient algorithms for SAT solvers are Sato, Grasp, Chaf, MiniSat and Berkmin. The Chaff algorithm is based on the DPLL algorithm which there is more than 40 years and is the most used strategy for Sat Solvers. This dissertation presents a detailed study of the behavior of zChaff (a very efficient implementation of the Chaff) to know what to expect from their performance in general.
Fang, Lei. "Exploring Constraint Satisfiability Techniques in Formal Verification." Diss., Virginia Tech, 2008. http://hdl.handle.net/10919/27573.
Full textPh. D.
Le, Piane Fabio. "Il teorema di Cook-Levin e i SAT-solver." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amslaurea.unibo.it/9026/.
Full textAbío, Roig Ignasi. "Solving hard industrial combinatorial problems with SAT." Doctoral thesis, Universitat Politècnica de Catalunya, 2013. http://hdl.handle.net/10803/117608.
Full textEriksson, Rikard, and Vlad Badea. "Indoor navigation with pseudolites (fake GPS sat.)." Thesis, Linköping University, Department of Science and Technology, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-3498.
Full textThis Master Thesis was conducted by Rikard Eriksson and Vlad Badea for their Master of Science degree in Electronics Design Engineering at the University of Linköping (Linköpings Universitet), Sweden. HTC Sweden AB initialized this Thesis and the Thesis contains a pre study of pseudolite based indoor navigation systems, a design of a simple pseudolite and finally some recommendations of applications.
The pre study starts off with an introduction of the GPS system. This since pseudolite based systems and GPS have many similarities. Different pseudolites based techniques were then investigated and the pre study is wrapped up with a very short briefing on the Hammerhead chip.
Some of the pseudolite based techniques were worth some more looking into and a pseudolite was therefore designed and simulated. There was unfortunate not enough time to actually build the pseudolite and verify it.
Some recommendations to HTC Sweden were given in the last chapter of this thesis. The authors of this thesis recommend some interesting techniques and how the future work could proceed.
Oliveira, Ricardo Tavares de. "Arco consistência generalizada em codificações SAT relativas." reponame:Repositório Institucional da UFPR, 2017. http://hdl.handle.net/1884/46292.
Full textTese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 21/02/2017
Inclui referências : f. 67-71
Área de concentração : Ciência da computação
Resumo: Várias codificações de problemas relevantes para SAT ou suas variações são conhecidas e estudadas pela comunidade. Uma possível maneira de mensurar a eficiência destas codificações consiste em avaliar a manutenção da Arco Consistência Generalizada (ACG) da fórmula resultante pelo resolvedor SAT. Ao melhor de nosso conhecimento, não há estudos sobre a manutenção de tal consistência para codificações relativas, que descrevem relações binárias sobre um dado conjunto de elementos do problema. Neste trabalho, é apresentado um estudo sobre a Arco Consistência Generalizada em codificações SAT relativas. É mostrado que, dependendo das propriedades da relação codificada, as fórmulas obtidas por estas codificações são mantidas ACG pelo procedimento da Propagação Unitária. Conjectura-se também que estas codificações não podem ser polinomialmente restritas para mantê-las ACG. Neste trabalho, é também apresentado um método para manter uma consistência parcial nas fórmulas obtidas pelas codificações relativas. O método é baseado na manutenção da árvore de dominantes do grafo induzido pela relação codificada, durante o processo de busca do resolvedor SAT. Resultados experimentais indicam que o método pode reduzir o número de decisões realizadas pelo resolvedor e, logo, o espaço de busca explorado. Outras contribuições deste trabalho incluem codificações relativas para conectividade em grafos e para o problema da Árvore de Steiner, um framework genérico para unificar as codificações relativas conhecidas, um algoritmo polinomial para SAT para fórmulas mantidas ACG, e a implementação de algoritmos que mantêm árvores de dominantes para grafos dinâmicos dentro do código-fonte de um resolvedor SAT no estado-da-arte.
Abstract: Many encodings from relevant problems to SAT or its variants are known and studied by the community. One possible way to measure the efficiency of these encodings consists on evaluating the maintenance of the Generalized Arc Consistency (GAC) of the resulting formula by the SAT solver. To the best of our knowledge, there is no study about such consistency for relative encodings, that describe binary relations over a given set of elements from the problem. In this work, it is presented a study about the Generalized Arc Consistency for relative SAT encodings. It is shown that, depending on the properties of the encoded relation, the formulae obtained by such encodings are maintened GAC by the Unit Propagation procedure. It is also conjectured that these encodings cannot be polynomially restricted in order to maintain them GAC. In this work, it is also presented a method to maintain a partial consistency on the formulae obtained by relative encoding. The method is based on the maintenance of the dominator tree of the underlying graph, during the search procedure of the SAT solver. Experimental evaluations indicate that the method may reduce the number of decisions made by the solver, and, thus, the search space it explores. Other contributions of this work include relative encodings for graph connectivity and for the Steiner Tree problem, a generic framework unifying known relative encodings, a polynomial-time algorithm for SAT for formulae maintened GAC, and the implementation of algorithms that maintain dominator trees for dynamic graphs inside the source code of a state-of-the-art SAT solver.
Neil, Tobias. "A New SAT Encoding of Earley Parsing." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-244520.
Full textNelson, Max (Max M. ). "A new approach to parallel SAT solvers." Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/85456.
Full textCataloged from PDF version of thesis.
Includes bibliographical references (pages 71-72).
We present a novel approach to solving SAT problems in parallel by partitioning the entire set of problem clauses into smaller pieces that can be solved by individual threads. We examine the complications that arise with this partitioning, including the idea of global variables, broadcasting global conflict clauses, and a protocol to ensure correctness. Along with this algorithm description, we provide the details of a C++ implementation, ParallelSAT, with a few specific optimizations. Finally, we demonstrate that this approach provides a significant speedup on a set of SAT problems related to program analysis.
by Max Nelson.
M. Eng.
Bouma, Craig Earl. "Physics First: Impact on SAT Math Scores." Digital Commons at Loyola Marymount University and Loyola Law School, 2013. https://digitalcommons.lmu.edu/etd/213.
Full textBouma, Craig E. "Physics First| Impact on SAT Math Scores." Thesis, Loyola Marymount University, 2014. http://pqdtopen.proquest.com/#viewpdf?dispub=3610316.
Full textImproving science, technology, engineering, and mathematics (STEM) education has become a national priority and the call to modernize secondary science has been heard. A Physics First (PF) program with the curriculum sequence of physics, chemistry, and biology (PCB) driven by inquiry- and project-based learning offers a viable alternative to the traditional curricular sequence (BCP) and methods of teaching, but requires more empirical evidence. This study determined impact of a PF program (PF-PCB) on math achievement (SAT math scores) after the first two cohorts of students completed the PF-PCB program at Matteo Ricci High School (MRHS) and provided more quantitative data to inform the PF debate and advance secondary science education. Statistical analysis (ANCOVA) determined the influence of covariates and revealed that PF-PCB program had a significant (p < .05) impact on SAT math scores in the second cohort at MRHS. Statistically adjusted, the SAT math means for PF students were 21.4 points higher than their non-PF counterparts when controlling for prior math achievement (HSTP math), socioeconomic status (SES), and ethnicity/race.
Kheireddine, Anissa. "Contribution to SAT-based Bounded Model Checking." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS566.
Full textComputer systems have become omnipresent in our daily lives. Ensuring the reliability and robustness of these systems is an absolute necessity. Model-Checking is one of the approaches dedicated to this purpose. Its objective is to either prove the absence of failures or identify potential ones. Model-Checking is declined into several technique. Among these, there is Bounded Model Checking (BMC), a technique that relies on Boolean satisfiability (SAT). The core idea behind BMC is to verify that a model, restricted to executions bounded by some integer k, satisfies its specification, often defined as a set of temporal logic expressions. In this approach, system behaviors are expressed as SAT problems. Unlike other formal verification methods, SAT-based BMC is generally not prone to the state space explosion problem, which can be problematic when dealing with designs involving millions of variables and constraints. However, the trade-off lies in the time complexity, as SAT problems are known to be NP-complete. Over the past few decades, significant advancements have been made in sequential SAT solving. These developments have mainly focused on utilizing dynamic information, acquired during the solving process (e.g., Learning Binary Clauses), or static information, extracted from the inherent structure of the SAT problem (e.g., community structure). However, less attention has been given to the structural information embedded within the original problem. For instance, when a BMC problem is reduced to SAT, critical information is lost in the translation. As this thesis emphasizes, reintegrating this lost information can greatly enhance the solving process. This work explores ways to improve SAT-based BMC problem-solving, both in sequential and parallel settings, by harnessing and leveraging pertinent information extracted from the problem's inherent characteristics. This may involve improving existing generic heuristics or effectively breaking down the formula into partitions
Py, Matthieu. "Inférence et certificats pour le problème de satisfiabilité maximum." Electronic Thesis or Diss., Aix-Marseille, 2021. http://www.theses.fr/2021AIXM0631.
Full textIn this thesis, we are interested in the maximum satisfiability problem (Max-SAT), which consists,given a Boolean formula in conjunctive normal form, in finding an assignment of the variables of the formula which allows to satisfy as many clauses as possible. The most widely used Max-SAT proof system is based on the Max-SAT resolution inference rule which is the adaptation for Max-SAT of the resolution rule used for the SAT problem. The resolution rule deduces a new clause from two opposing clauses, enabling to certify that a formula is unsatisfiable by gradually deducing new clauses until deducing a contradiction, represented in the form of an empty clause. The adaptation of such proofs, referred to as resolution refutations, for Max-SAT without considerably increasing its size is an open problem since the introduction of Max-SAT resolution.We propose in this thesis two methods to adapt any resolution resfutation into a valid refutation for Max-SAT, referred to as max-refutation. Another contribution is the construction of certificates to demonstrate the optimality of a solution for the Max-SAT problem. To generate such certificates, we use the max-refutations that we are now able to generate from the resolution refutations. Finally, we are interested in the problem which consists, given an initial formula and a given information (clause or formula), of inferring this information by Max-SAT-equivalence-preserving inference rules. As the max-resolution is incomplete for the inference in Max-SAT, we propose a new proof system as well as an algorithm allowing to infer, if possible, a given clause or formula
Silveira, Jaime Kirch da. "Parallel SAT solvers and their application in automatic parallelization." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2014. http://hdl.handle.net/10183/95373.
Full textSince the slowdown in improvement in the frequency of processors, a new tendency has arisen to allow software to take advantage of faster hardware: parallelization. However, different from increasing the frequency of processors, using parallelization requires a different kind of programming, parallel programming, which is usually harder than common sequential programming. In this context, automatic parallelization has arisen, allowing software to take advantage of parallelism without the need of parallel programming. We present here two proposals: SAT-PaDdlinG and RePaSAT. SAT-PaDdlinG is a parallel DPLL SAT Solver on GPU, which allows RePaSAT to use this environment. RePaSAT is our proposal of a parallel machine that uses the SAT Problem to automatically parallelize sequential code. Because GPU provides a cheap, massively parallel environment, SATPaDdlinG aims at providing this massive parallelism and low cost to RePaSAT, as well as to any other tool or problem that uses SAT Solvers.
Signati, Teresa. "Evaluating Coppersmith’s Criteria by way of SAT Solving." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/16149/.
Full textBéjar, Torres Ramón. "Systematic and local search algorithms for regular-SAT." Doctoral thesis, Universitat Autònoma de Barcelona, 2000. http://hdl.handle.net/10803/3018.
Full textMello, Arthur Renato 1985. "Plataforma para desenvolvimento e avaliação de resolvedores SAT." reponame:Repositório Institucional da UFPR, 2012. http://hdl.handle.net/1884/26705.
Full textEhlers, Thorsten [Verfasser]. "SAT and CP - Parallelisation and Applications / Thorsten Ehlers." Kiel : Universitätsbibliothek Kiel, 2017. http://d-nb.info/113755522X/34.
Full textManthey, Norbert. "Towards Next Generation Sequential and Parallel SAT Solvers." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-158672.
Full textBurchard, Jan [Verfasser], and Bernd [Akademischer Betreuer] Becker. "Applying advanced SAT-based techniques to circuit testing." Freiburg : Universität, 2018. http://d-nb.info/1165503220/34.
Full textZielke, Christian [Verfasser], and Michael [Akademischer Betreuer] Kaufmann. "Engineering SAT Applications / Christian Zielke ; Betreuer: Michael Kaufmann." Tübingen : Universitätsbibliothek Tübingen, 2015. http://d-nb.info/1163664812/34.
Full textFliti, Tamim. "Le problème SAT : traitement dynamique et données minimales." Aix-Marseille 2, 1997. http://www.theses.fr/1997AIX22015.
Full textMANDLER, JACQUES. "Sur la transition de phase de 3-sat." Paris 6, 2000. http://www.theses.fr/2000PA066530.
Full textMinařík, Vojtěch. "Využití SAT solverů v úloze optimalizace kombinačních obvodů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2019. http://www.nusl.cz/ntk/nusl-399701.
Full textBENOIST, EMMANUEL. "Generation a delai polynomial pour le probleme sat." Caen, 2000. http://www.theses.fr/2000CAEN2002.
Full textBau, Alexander. "SAT Compilation for Constraints over Structured Finite Domains." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-221884.
Full textPari, Pushkin Raj. "Several issues on the boolean satisfiability (SAT) problem." College Park, Md. : University of Maryland, 2004. http://hdl.handle.net/1903/1427.
Full textThesis 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.
Eriksson, Leif. "Solving Temporal CSPs via Enumeration and SAT Compilation." Thesis, Linköpings universitet, Institutionen för datavetenskap, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-162482.
Full textVallade, Vincent. "Contributions à la résolution parallèle du problème SAT." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS260.
Full textThis thesis presents multiple and orthogonal contributions to the improvement of the parallel resolution of the Boolean satisfiability problem (or SAT problem). An instance of the SAT problem is a propositional formula of a particular form (the conjunctive normal form is the most common) representing, in general, the variables and constraints of a real-world problem, such as multi-constraint planning, hardware and software verification or cryptography. Solving the SAT problem involves determining whether there is an assignment of variables that satisfies the formula. An algorithm capable of providing an answer to this problem is called a SAT solver. A simplified view of a SAT solver is an algorithm that will traverse the set of possible combinations of values for each variable until it finds a combination that makes the formula true (the formula is SAT). If the solver has gone through all the possible combinations without finding a solution, the formula is UNSAT. Obviously, this algorithm has an exponential complexity, indeed the SAT problem is the first problem to have been determined NP-complete. Many algorithms and heuristics have been developed to accelerate the solving capacity of this problem, mainly in a sequential context. The ubiquity of multi-core machines has encouraged considerable efforts in the parallel resolution of the SAT problem. This thesis is a continuation of these efforts. The contributions made by this thesis focus on the quality of information sharing between the different workers of a parallel SAT solver. A first contribution presents an efficient method to implement an asynchronous algorithm for reducing the size of the shared information. A second contribution combines the information extracted from the particular structure of the propositional formula with the information extracted dynamically during the resolution of the problem by the solver in order to create a filter that maximizes the quality of the shared information. Finally, a last contribution deals with the integration of a component allowing to determine in a probabilistic way the truth value of the variables allowing to make a formula satisfiable. The call of this component during the solving process allows to guide the solver more quickly towards a solution (if a solution exists)