Rozprawy doktorskie na temat „SAT”
Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: SAT.
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Sprawdź 50 najlepszych rozpraw doktorskich naukowych na temat „SAT”.
Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.
Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.
Przeglądaj rozprawy doktorskie z różnych dziedzin i twórz odpowiednie bibliografie.
1
AXELSSON, LUDVIG, i 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.
Pełny tekst źródłaStreszczenie:
Sudoku är ett mycket populärt pusselspel som härstammar från Japan. Sudokuproblemet har visats vara NP-fullständigt och det finns därför troligen inget effektivt sätt att lösa stora pussel. På senare år har det skett mycket forskning kring SAT-lösare. I denna rapport prövades olika SAT-lösare från ”International SAT-Competition” för att undersöka om det existerar en korrelation mellan exekveringstid och svårighetsgradering samt för att avgöra vilken av dessa som är effektivast för att lösa pussel av olika svårighetsgrad och storlek. För att undersöka detta genereradesett stort antal pussel och två tester utfördes. Ett test mätteexekveringstiden för olika SAT-lösare på pussel av olika svårighetsgrad.Det andra testet mätte tiden för SAT-lösarna på pussel av olika storlek.De prövade SAT-lösarna är Glucose, Lingeling, Minisat, Plingeling,Treengeling och Zenn.Resultaten visar på en korrelation mellan exekveringstid och svårighetsgradför de prövade SAT-lösarna när ett genomsnitt för lösarnabehandlades. Vid ett linjärt regressionstest erhölls en bestämningskoefficentpå ca 0.8. Vissa lösare hade en stor korrelation och andra lösarevisade inte någon korrelation alls. Korrelationen skulle också kunna beropå skillnaden i antalet ledtrådar mellan de olika pusslena. Det förklarardock inte den skillnad som finns mellan pussel av olika svårighetsgradmed samma antal ledtrådar.Genomsnittstiden för samtliga lösare var ca 20 ms för pussel avordning tre och ca 50 s för pussel av ordning nio. Av de prövade SATlösarnavar Minisat snabbast, både för pusslena av ordning tre och avhögre ordningar.Sudoku 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.
2
Szczepanski, Nicolas. "SAT en Parallèle". Thesis, Artois, 2017. http://www.theses.fr/2017ARTO0403/document.
Pełny tekst źródłaStreszczenie:
La thèse porte sur la résolution des problèmes de satisfaisabilité booléenne (SAT) dans un cadre massivement parallèle. Le problème SAT est largement utilisé pour résoudre des problèmes combinatoires de première importance comme la vérification formelle de matériels et de logiciels, la bio-informatique, la cryptographie, la planification et l’ordonnancement de tâches. Plusieurs contributions sont apportées dans cette thèse. Elles vont de la conception d’algorithmes basés sur les approches « portfolio » et « diviser pour mieux régner », à l’adaptation de modèles de programmation parallèle, notamment hybride (destinés à des architectures à mémoire partagée et distribuée), à SAT, en passant par l’amélioration des stratégies de résolution. Ce travail de thèse a donné lieu à plusieurs contributions dans des conférences internationales du domaine ainsi qu’à plusieurs outils (open sources) de résolution des problèmes SAT, compétitifs au niveau internationalThis 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
3
Lardeux, Frédéric. "Approches hybrides pour les problèmes de satisfiabilité (SAT et MAX-SAT)". Angers, 2005. http://www.theses.fr/2005ANGE0024.
Pełny tekst źródłaStreszczenie:
Cette thèse est centrée sur la résolution des problèmes de satisfiabilité SAT et MAX-SAT. Les contributions apportées sont de trois types. Tout d'abord nous avons développé l'algorithme mémétique GASAT pour les problèmes SAT et MAX-SAT hybridant un algorithme tabou et un algorithme génétique. Des outils spécifiques aux problèmes de satisfiabilité y ont été intégrés tels que des mécanismes d'intensification, de diversification et un nouvel opérateur de croisement. Ensuite, nous avons proposé un nouveau cadre de résolution permettant aux méthodes exactes et aux méthodes approchées de manipuler la même représentation de l'espace de recherche. Pour cela, nous avons ajouté une troisième valeur de vérité "indéterminé". Les résultats obtenus par les algorithmes hybrides trivalués montrent l'intérêt de ce cadre de résolution. Enfin, nous nous sommes penchés sur les heuristiques de branchement des algorithmes de Branch and Bound pour le problème MAX-SAT. L'étude que nous présentons montre que ces heuristiques réagissent très différemment en fonction des paramètres initiaux, de la structure de l'instance étudiée et des mécanismes d'amélioration du Branch and Bound. Elle permet d'envisager la création de nouvelles heuristiques spécifiquement dédiées au problème MAX-SATThis 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
4
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.
Pełny tekst źródłaStreszczenie:
Le probleme sat (existence d'une solution d'un systeme sat) est un probleme np-complet. Le probleme max-sat (nombre maximum de clauses satisfaites d'un systeme sat), bien qu'a priori plus difficile, est egalement un probleme np-complet. Le probleme number-sat (nombre de solutions d'un systeme sat) est plus complexe et appartient a la classe des problemes number-p-complet. Il n'existe donc pas, aujourd'hui, d'algorithme deterministe polynomial capable de resoudre l'un ou l'autre de ces trois problemes. Pourtant, a propos du probleme number-sat, on montre que l'on peut definir des classes de systemes sat pour lesquelles il est possible de calculer, polynomialement par rapport a la taille de ces systemes, l'esperance, ou n'importe quel autre moment, du nombre de solutions. On montre egalement, a propos du probleme max-sat, que l'on peut calculer, pour n'importe quel systeme sat, toujours polynomialement par rapport a la taille du systeme, l'esperance, ou n'importe quel autre moment, du nombre de clauses satisfaites. En revanche, en ce qui concerne le probleme sat, la complexite du calcul de la probabilite d'existence d'une solution d'une classe de systemes sat est toujours un probleme ouvert
5
Darras, Sylvain. "Traitements locaux dans les arbres de recherche pour SAT et max-SAT". Amiens, 2008. http://www.theses.fr/2008AMIE0120.
Pełny tekst źródłaStreszczenie:
La difficulté de résolution des problèmes combinatoires réside dans la taille exponentielle de leur espace de recherche. Parmi ces problèmes figurent les problèmes de satisfaction de contraintes, tels que SAT et Max-SAT. Ce mémoire s'inscrit dans une politique d'augmentation des capacités de résolution des solveurs complets SAT et Max-SAT, grâce à une meilleure exploitation des informations révélées par le parcours de l'arbre de recherche. Concernant le problème SAT, nous proposons une nouvelle étude du graphe d'implication qui nous permet de mettre en relief de possibles subsomptions appliquées aux clauses existantes. L'objectif de cette technique est de provoquer une diminution de la taille des clauses de la formule, afin de rendre celles-ci plus expressives et efficaces. Pour cela, nous développons un parcours peu coûteux du graphe d'implication, dirigé par la clause à subsumer, déterminant (s'il en existe) une subsomption de cette clause. Les travaux appliqués au domaine Max-SAT ont porté sur une amélioration du calcul de la borne inférieure des algorithmes "Branch-and-Bound". Considérant un solveur dont l'estimation de la borne inférieure repose, au moins en partie, sur la recherche d'ensembles conflictuels, notre approche vise à éviter le calcul répété de noyaux inconsistants équivalents. Grâce à l'enregistrement de certains de ces ensembles conflictuels d'un noeud vers ses noeuds-fils, il est possible de réutiliser directement ces éléments sans nécessiter de calcul. De plus, ces noyaux permettent une amélioration de la qualité de la borne inférieure en favorisant la conservation les ensembles conflictuels efficacesThe 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
6
Bayless, Sam. "SAT modulo monotonic theories". Thesis, University of British Columbia, 2017. http://hdl.handle.net/2429/61062.
Pełny tekst źródłaStreszczenie:
Satisfiability Modulo Theories (SMT) solvers are a class of efficient constraint solvers which
form integral parts of many algorithms. Over the years, dozens of different Satisfiability Modulo Theories solvers have been developed, supporting dozens of different logics. However, there are still many important applications for which specialized SMT solvers have not yet been developed.
We develop a framework for easily building efficient SMT solvers for previously unsupported logics.
Our techniques apply to a wide class of logics which we call monotonic theories, which include many important elements of graph theory and automata theory.
Using this SAT Modulo Monotonic Theories framework, we created a new SMT solver, MonoSAT. We demonstrate that MonoSAT improves the state of the art across a wide body of applications, ranging from circuit layout and data center management to protocol synthesis - and even to video game design.Science, Faculty of
Computer Science, Department of
Graduate
7
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.
Pełny tekst źródłaStreszczenie:
OPS-SAT is an in-orbit laboratory mission designed to allow experimenters todeploy new on-board software and perform in-orbit demonstrations of new tech-nology and concepts related to mission operations. The NanoSat MO Frame-work facilitates the process of developing experimental on-board software for OPS-SAT by abstracting the complexities related to communication across the space toground link as well as the details of low-level device access. The objective of thisproject is to implement functional simulation models of OPS-SAT peripherals andorbit/attitude behavior, which integrated together with the NanoSat MO Frame-work provide a sufficiently realistic runtime environment for OPS-SAT on-boardsoftware experiment development. Essentially, the simulator exposes communi-cation interfaces for executing commands which affect the payload instrumentsand/or retrieve science data and telemetry. The commands can be run either fromthe MO Framework or manually, from an intuitive GUI which performs syntaxcheck. In this case, the output will be displayed for advanced debugging. The endresult of the thesis work is a virtual machine which has all the tools installed todevelop cutting edge technology space applications.
8
Bierlee, 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.
Pełny tekst źródłaStreszczenie:
Combinatorial (optimization) problems occur in nature and society. Constraint modeling languages such as MiniZinc allow the user to declaratively specify such problems in terms of its decision variables and constraints. Subsequently, the MiniZinc model can be compiled into an equivalent (Boolean) SAT formula to be solved by a SAT solver. This thesis reports on the design, implementation and experimental evaluation of the new MiniZinc-SAT compiler, which supports single or even mixed usage of three distinct integer variable encoding methods.
9
ONO, Takao, i Tomio HIRATA. "Approximation Algorithms for MAX SAT". Institute of Electronics, Information and Communication Engineers, 2000. http://hdl.handle.net/2237/15068.
Pełny tekst źródła
10
Nguyen, 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.
Pełny tekst źródłaStreszczenie:
Boolean satisfiability (SAT) is the problem of determining whether there exists an assignment of the Boolean variables to the truth values such that a given Boolean formula evaluates to true. SAT was the first example of an NP-complete problem. Only two decades ago SAT was mainly considered as of a theoretical interest.
Nowadays, the picture is very different. SAT solving becomes mature and is a successful approach for tackling a large number of applications, ranging from artificial intelligence to industrial hardware design and verification. SAT solving consists of encodings and solvers. In order to benefit from the tremendous advances in the development of solvers, one must first encode the original problems into SAT instances.
These encodings should not only be easily generated, but should also be efficiently processed by SAT solvers. Furthermore, an increasing number of practical applications in computer science can be expressed as constraint satisfaction problems (CSPs). However, encoding a CSP to SAT is currently regarded as more of an art than a science, and choosing an appropriate encoding is considered as important as choosing an algorithm. Moreover, it is much easier and more efficient to benefit from highly optimized state-of-the-art SAT solvers than to develop specialized tools from scratch. Hence, finding appropriate SAT encodings of CSPs is one of the most fascinating challenges for solving problems by SAT.
This thesis studies SAT encodings of CSPs and aims at:
1) conducting a comprehensively profound study of SAT encodings of CSPs by separately investigating encodings of CSP domains and constraints;
2) proposing new SAT encodings of CSP domains;
3) proposing new SAT encoding of the at-most-one constraint, which is essential for encoding CSP variables; 4) introducing the redundant encoding and the hybrid encoding that aim to benefit from both two efficient and common SAT encodings (i.e., the sparse and order encodings) by using the channeling constraint (a term used in Constraint Programming) for SAT; and
5) revealing interesting guidelines on how to choose an appropriate SAT encoding in the way that one can exploit the availability of many efficient SAT solvers to solve CSPs efficiently and effectively.
Experiments show that the proposed encodings and guidelines improve the state-of-the-art SAT encodings of CSPs.
11
Izrael, 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.
Pełny tekst źródłaStreszczenie:
This thesis is concerned with design and implementation of a complete SAT solver accelerated on GPU. The achitecture of modern graphics cards is described as well as the CUDA platform and a list of common algorithms used for solving the boolean satisfiability problem (the SAT problem). The presented solution is based on the 3-SAT DC alogirthm, which belongs to the family of well-known DPLL based algorithms. This work describes problems encountered during the design and implementation. The resulting application was then analyzed and optimized. The presented solver cannot compete with state of the art solvers, but proves that it can be up to 21x faster than an equivalent sequential version. Unfortunately, the current implementation can only handle formulas of a limited size. Suggestions on further improvements are given in final sections.
12
Gabàs, Masip Joel. "SAT-based approaches for constraint optimization". Doctoral thesis, Universitat de Lleida, 2016. http://hdl.handle.net/10803/396610.
Pełny tekst źródłaStreszczenie:
La optimització amb restriccions ha estat utilitzada amb èxit par a resoldre problemes en molts dominis reals (industrials). Aquesta tesi es centra en les aproximacions lògiques, concretament en Màxima Satisfactibilitat (MaxSAT) que és la versió d’optimització del problema de Satisfactibilitat booleana (SAT). A través de MaxSAT, s’han resolt molts problemes de forma eficient. Famílies d’instàncies de la majoria d’aquests problemes han estat sotmeses a la MaxSAT Evaluation (MSE), creant així una col•lecció pública i accessible d’instàncies de referència. En les edicions recents de la MSE, els algorismes SAT-based han estat les aproximacions que han tingut un millor comportament per a les instàncies industrials. Aquesta tesi està centrada en millorar els algorismes SAT-based . El nostre treball ha contribuït a tancar varies instàncies obertes i a reduir dramàticament el temps de resolució en moltes altres. A més, hem trobat sorprenentment que reformular y resoldre el problema MaxSAT a través de programació lineal sencera era especialment adequat per algunes famílies. Finalment, hem desenvolupat el primer portfoli altament eficient par a MaxSAT que ha dominat en totes las categories de la MSE des de 2013.La 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.
13
Wedler, Markus. "Modellgenerierung für die SAT-basierte Eigenschaftsprüfung". [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=98098212X.
Pełny tekst źródła
14
Giráldez, Crú Jesús. "Beyond the Structure of SAT Formulas". Doctoral thesis, Universitat Autònoma de Barcelona, 2016. http://hdl.handle.net/10803/386422.
Pełny tekst źródłaStreszczenie:
Hoy en día, muchos problemas del mundo real son codificados en instancias SAT y resueltos eficientemente por modernos SAT solvers. Estos solvers, usualmente conocidos como Conflict-Driven Clause Learning (CDCL: Aprendizaje de cláusulas guiado por conflictos) SAT solvers, incluyen una variedad de sofisticadas técnicas, como el aprendizaje de cláusulas, estructuras de datos perezosas, heurísticas de ramificación adaptativas basadas en los conflictos, o reinicios aleatorios, entre otros. Sin embargo, las razones de su eficiencia resolviendo problemas SAT del mundo real, o industriales, son todavía desconocidas. La creencia común en la comunidad SAT es que estas técnicas explotan alguna estructura oculta de los problemas del mundo real.
En esta tesis, primeramente se caracteriza algunas importantes características de la estructura subyacente de las instancias SAT industriales. Específicamente, estas son la estructura de comunidades y la estructura auto-similar. Se observa que la mayoría de las fórmulas SAT industriales, vistas como grafos, tienen estas dos propiedades. Esto significa que (i) en un grafo con una estructura de comunidades clara; es decir, alta modularidad, se puede encontrar una partición de sus nodos en comunidades de tal forma que la mayoría de las aristas conectan nodos de la misma comunidad; y (ii) en un grafo con el patrón de auto-similitud; es decir, siendo fractal, su forma se mantiene después de re-escalados (agrupando conjuntos de nodos en uno). Se analiza también cómo estas estructuras están afectadas por los efectos de las técnicas CDCL durante la búsqueda.
Usando los estudios estructurales previos, se proponen tres aplicaciones. Primero, se aborda el problema de la generación aleatoria de instancias SAT pseudo-industriales usando la noción de modularidad. Nuestro modelo genera instancias similares a las (clásicas) fórmulas SAT aleatorias cuando la modularidad es baja, pero cuando este valor es alto, nuestro modelo también es adecuado para modelar problemas pseudo-industriales realísticamente. Segundo, se propone un método basado en la estructura en comunidades de la instancia para detectar cláusulas aprendidas relevantes. Nuestra técnica aumenta la instancia original con un conjunto de cláusulas relevantes, y esto resulta en una mejora general de la eficiencia de varios CDCL SAT solvers. Finalmente, se analiza la clasificación de instancias SAT industrial en familias usando las características estructurales previamente analizadas, y se comparan con otros clasificadores comúnmente usados en aproximaciones SAT portfolio.
En resumen, esta disertación extiende nuestro conocimiento sobre la estructura de las instancias SAT, con el objetivo de explicar mejor el éxito de las técnicas CDCL, con la posibilidad de mejorarlas; y propone una serie de aplicaciones basadas en este análisis de la estructura subyacente de las fórmulas SAT.Nowadays, 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.
15
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.
Pełny tekst źródłaStreszczenie:
This thesis aimed to explore how sequential boolean satisability solvers can be used on the integer factorisation problem. The integer factorisation problem is believed to be hard and modern public key cryptography relies on that,note worthily SSL/TSL and SSH support the use of RSA. However, it is not proven that integer factorisation is hard and therefore it is of great importanceto explore dierent attack avenues. The modulus in RSA is a semiprime, e.g.an integer that is the product of two primes. Hence, in this thesis an empiricalstudy of the factorisation of semiprimes with a bit-length of up to 32 bits iscarried out. Randomly selected semiprimes are factorized through six dierent reductions using three dierent solvers (Glucose, Lingeling and PicoSAT) and the result are compared to that of MSieve, an open-source integer factorisationprogram. As seen in the comparison boolean satisability solvers cannot be used as a replacement of an integer factorisation solver. Additionally comparisons between the dierent reductions and boolean satisability solvers show that the combination of solver and reduction greatly aects performance. The implication is that further explorations of the integer factorisation problem with boolean satisability solvers can greatly benet from either avoiding a inadequate solver and reduction pair or from attempting to identify the outliers that signify a inadequate coupling.
16
Emanuelsson, Kristoffer, i 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.
Pełny tekst źródła
17
Lundén, Daniel, i 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.
Pełny tekst źródłaStreszczenie:
Factoring integers is a well known problem that at present cannot be solved in polynomial time. Therefore, other approaches for solving factorization problems are of interest. One such approach is to reduce factorization to SAT and solve it with a dedicated SAT solver. In this study, parallel SAT solvers are examined in this context and evaluated in terms of speedup, efficiency and effectiveness versus sequential SAT solvers. The methodology used was an experimental approach where different parallel and sequential solvers were benchmarked on different reductions from integer factorization to SAT. The benchmarks concluded that parallel SAT solvers are not better suited for solving factorization problems than sequential solvers. The performance boosts achieved by the fastest parallel solver barely corresponded to the extra amount of available parallel resources over the fastest sequential solver.Att 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.
18
Kokotov, Daniel (Daniel L. ). 1978. "PSolver : a distributed SAT solver framework". Thesis, Massachusetts Institute of Technology, 2001. http://hdl.handle.net/1721.1/86807.
Pełny tekst źródłaStreszczenie:
Thesis (M.Eng. and S.B.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001.Includes bibliographical references (p. 129-130).
by Daniel Kokotov.
M.Eng.and S.B.
19
Vimjam, Vishnu Chaithanya. "Strategies for SAT-Based Formal Verification". Diss., Virginia Tech, 2007. http://hdl.handle.net/10919/26078.
Pełny tekst źródłaStreszczenie:
Verification of digital hardware designs is becoming an increasingly complex task as the designs are incorporating more functionality, becoming complex and growing larger in size. Today, verification remains a bottleneck in meeting time-to-market requirements and consumes more than 70% of the overall design-costs. Traditionally, verification has been done using simulation-based approaches, where a set of appropriate test-stimuli is used by the designer. As the designs become more complex, however, simulation-based techniques often fail to capture corner-case errors. Furthermore, unless exhaustively tested, these approaches do not guarantee the correctness of a system with respect to its specifications. As a consequence, formal methods for design verification have been sought after. In formal verification, the conformance of a design to a given set of specifications is proven mathematically, thereby leaving no room for unexplored search spaces. Despite the exponential time/memory complexities often involved within the formal approaches, they have shown promise in capturing subtle bugs, which were missed otherwise.
In this dissertation, we focus on Boolean Satisfiability (SAT) based formal verification, which has gained tremendous importance in the recent past. Importantly, SAT-based approaches often alleviate the memory explosion problem, which had been a bottleneck of the traditional symbolic (Binary Decision Diagram based) approaches. In SAT-based techniques, the set of verification tasks are converted into a set of Boolean formulae, which are checked for satisfiability using a SAT solver. These problems are often NP-complete and are prone to an explosion in the required run-time. To overcome this, we propose novel strategies which utilize both structural and logical information of a sequential circuit. In particular, we devise techniques to extract non-trivial invariants of a design, strengthen properties such that they can be proven faster and interleave bounded reachability analysis with bounded model checking. We provide the necessary algorithms and implementation details in order to automate the proposed techniques. Experiments conducted on a variety of benchmark circuits show that orders of magnitude improvement in overall run-times can be achieved via our techniques compared to the existing state-of-the-art SAT-based approaches.Ph. D.
20
Pilz, Enrico. "Boolsche Gleichungssysteme, SAT Solver und Stromchiffren". [S.l. : s.n.], 2008. http://nbn-resolving.de/urn:nbn:de:bsz:289-vts-65265.
Pełny tekst źródła
21
Le, Frioux Ludovic. "Towards more efficient parallel SAT solving". Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS209.
Pełny tekst źródłaStreszczenie:
Les solveurs résolvants le problème de SATisfiabilité booléenne sont utilisés avec succès dans de nombreux contextes. Ceci est dû à leur capacité à résoudre d'énormes problèmes. La plupart des solveurs SAT ont longtemps été séquentiels. L'émergence de machines multi-coeurs ouvre de nouvelles perspectives. Il existe de nombreux solveurs SAT parallèles différant par leurs stratégies, langages, etc. Il est donc difficile de comparer l'efficacité de différentes stratégies de manière équitable. De plus, l'introduction de nouvelles approches nécessite une compréhension approfondie de l'implémentation des solveurs existants. Nous présentons Painless : une platefrome pour implémenter des solveurs SAT parallèles pour les multi-coeurs. Grâce à sa modularité, elle offre une implémentation des composants de base et permet également aux utilisateurs de créer facilement leurs solveurs parallèles basés sur de nouvelles stratégies. Painless a permis de construire et tester de nombreux solveurs. Nous avons pu imiter le comportement de trois solveurs de l'état de l'art tout en factorisant de nombreuses parties. L'efficacité de Painless a été soulignée par le fait que ces implémentations sont au moins aussi efficaces que les originales. De plus, l'un des nos solveurs a gagné la compétition SAT 2018. Painless nous a permis de mener des expériences équitables avec des solveurs diviser pour régner et de mettre en lumière des compositions originales d'heuristiques plus performantes que celles déjà connues. De plus, nous avons été en mesure de créer et tester de nouvelles stratégies exploitant la structure modulaire des formules SATBoolean 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
22
Cherif, Mohamed Sami. "Reasoning and inference for (maximum) satisfiability : new insights". Electronic Thesis or Diss., Aix-Marseille, 2022. http://www.theses.fr/2022AIXM0589.
Pełny tekst źródłaStreszczenie:
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
23
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/.
Pełny tekst źródłaStreszczenie:
No estudo da complexidade de problemas computacionais destacam-se duas classes conhecidas como P e NP. A questao P=NP e um dos maiores problemas nao resolvidos em Ciencia da Compu- tacao teorica e Matematica contemporanea. O problema SAT foi o primeiro problema reconhecido como NP-completo e consiste em verificar se uma determinada formula da logica proposicional clas- sica e ou nao satisfazivel. As implementacoes de algoritmos para resolver problemas SAT sao conhe- cidas como resolvedores SAT (SAT Solvers). Existem diversas aplicacoes em Ciencia da Computacao que podem ser realizadas com SAT Solvers e com outros resolvedores de problemas NP-completos que podem ser reduzidos ao SAT como por exemplo problemas de coloracao de grafos, problemas de agendamento e problemas de planejamento. Dentre os mais eficientes algoritmos para resolvedores de SAT estao Sato, Grasp, Chaff, MiniSat e Berkmin. O Algoritmo Chaff e baseado no Algoritmo DPLL o qual existe a mais de 40 anos e e a estrategia mais utilizada para os Sat Solvers. Essa dissertacao apresenta um estudo aprofundado do comportamento do zChaff (uma implementacao muito eficiente do Chaff) para saber o que esperar de suas execucoes em geral .In 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.
24
Fang, Lei. "Exploring Constraint Satisfiability Techniques in Formal Verification". Diss., Virginia Tech, 2008. http://hdl.handle.net/10919/27573.
Pełny tekst źródłaStreszczenie:
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.
25
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/.
Pełny tekst źródłaStreszczenie:
In questa tesi è trattato il tema della soddisfacibilità booleana o proposizionale, detta anche SAT, ovvero il problema di determinare se una formula booleana è soddisfacibile o meno. Soddisfacibile significa che è possibile assegnare le variabili in modo che la formula assuma il valore di verità vero; viceversa si dice insoddisfacibile se tale assegnamento non esiste e se quindi la formula esprime una funzione identicamente falsa. A tal fine si introducono degli strumenti preliminari che permetteranno di affrontare più approfonditamente la questione, partendo dalla definizione basilare di macchina di Turing, affrontando poi le classi di complessità e la riduzione, la nozione di NP-completezza e si dimostra poi che SAT è un problema NP-completo. Infine è fornita una definizione generale di SAT-solver e si discutono due dei principali algoritmi utilizzati a tale scopo.
26
Abío, Roig Ignasi. "Solving hard industrial combinatorial problems with SAT". Doctoral thesis, Universitat Politècnica de Catalunya, 2013. http://hdl.handle.net/10803/117608.
Pełny tekst źródłaStreszczenie:
The topic of this thesis is the development of SAT-based techniques and tools for solving industrial combinatorial problems. First, it describes the architecture of state-of-the-art SAT and SMT Solvers based on the classical DPLL procedure. These systems can be used as black boxes for solving combinatorial problems. However, sometimes we can increase their efficiency with slight modifications of the basic algorithm. Therefore, the study and development of techniques for adjusting SAT Solvers to specific combinatorial problems is the first goal of this thesis.
Namely, SAT Solvers can only deal with propositional logic. For solving general combinatorial problems, two different approaches are possible:
- Reducing the complex constraints into propositional clauses.
- Enriching the SAT Solver language.
The first approach corresponds to encoding the constraint into SAT. The second one corresponds to using propagators, the basis for SMT Solvers. Regarding the first approach, in this document we improve the encoding of two of the most important combinatorial constraints: cardinality constraints and pseudo-Boolean constraints. After that, we present a new mixed approach, called lazy decomposition, which combines the advantages of encodings and propagators.
The other part of the thesis uses these theoretical improvements in industrial combinatorial problems. We give a method for efficiently scheduling some professional sport leagues with SAT. The results are promising and show that a SAT approach is valid for these problems.
However, the chaotical behavior of CDCL-based SAT Solvers due to VSIDS heuristics makes it difficult to obtain a similar solution for two similar problems. This may be inconvenient in real-world problems, since a user expects similar solutions when it makes slight modifications to the problem specification. In order to overcome this limitation, we have studied and solved the close solution problem, i.e., the problem of quickly finding a close solution when a similar problem is considered.
27
Eriksson, Rikard, i 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.
Pełny tekst źródłaStreszczenie:
This 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.
28
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.
Pełny tekst źródłaStreszczenie:
Orientador : Prof. Dr. Fabiano SilvaTese (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.
29
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.
Pełny tekst źródłaStreszczenie:
While the Boolean satisfiability problem (SAT) lies in NP, prodigious work in SAT solvers has allowed for its use in modeling a multitude of practical problems. Stating a problem in SAT can be cumbersome though and so the demand for SAT encodings arises, providing a means to formulate problems or parts of problems in a more intuitive environment. Several algorithms have been proposed in the past to encode context-free grammars as SAT formulae, allowing for the comprehensive construction of many interesting constraints such as at-most k constraints or such ones pertaining to language syntax. In 2011 a new algorithm was proposed, differing from previous ones in it being based on Earley parsing instead of CYK parsing. Although it performed well for interesting groups of grammars it was later found to behave incorrectly for certain inputs. This thesis discusses the flaws in said algorithm, presents a revision of it and argues for the altered algorithm's correctness. The alterations come with a price, however, and both the running time and output size complexities suffer more-than-quadratic blowup. Since no empirical tests have been performed as of yet, it is still unclear what impact this blowup will have on practical instances.
30
Nelson, Max (Max M. ). "A new approach to parallel SAT solvers". Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/85456.
Pełny tekst źródłaStreszczenie:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013.Cataloged 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.
31
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.
Pełny tekst źródłaStreszczenie:
Improving 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.
32
Bouma, Craig E. "Physics First| Impact on SAT Math Scores". Thesis, Loyola Marymount University, 2014. http://pqdtopen.proquest.com/#viewpdf?dispub=3610316.
Pełny tekst źródłaStreszczenie:
Improving 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.
33
Kheireddine, Anissa. "Contribution to SAT-based Bounded Model Checking". Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS566.
Pełny tekst źródłaStreszczenie:
Les systèmes informatiques sont devenus omniprésents dans notre vie quotidienne. Garantir la fiabilité et la robustesse de ces systèmes est une nécessité absolue. La Vérification de Modèles (Model-Checking) est l'une des approches dédiées à cette fin. Son objectif est de prouver l'absence de défaillances ou d'identifier d'éventuelles erreurs. La Vérification de Modèles se décline en plusieurs techniques. Parmi celles-ci, on trouve la Vérification de Modèles Bornée (Bounded Model Checking - BMC), une technique qui repose sur la satisfaisabilité booléenne (SAT). L'idée centrale derrière le BMC est de vérifier qu'un modèle, limité à des exécutions bornées par un entier k, satisfait sa spécification, souvent définie comme un ensemble d'expressions logiques temporelles. Dans cette approche, les comportements du système sont exprimés sous forme de problèmes SAT. Contrairement à d'autres méthodes de vérification formelle, le BMC basé sur SAT n'est généralement pas sensible au problème de l'explosion de l'espace d'états, ce qui peut poser problème lors de la conception de systèmes impliquant des millions de variables et de contraintes. Cependant, le compromis réside dans la complexité temporelle, car les problèmes SAT sont connus pour être NP-complets. Au cours des dernières décennies, d'importantes avancées ont été réalisées dans la résolution séquentielle de problèmes SAT. Ces développements se sont principalement concentrés sur l'utilisation d'informations dynamiques, acquises lors du processus de résolution (par exemple, l'apprentissage de clauses binaires) ou d'informations statiques, extraites de la structure inhérente du problème SAT (par exemple, la structure communautaire). Cependant, moins d'attention a été accordée aux informations structurelles intégrées dans le problème initial. Par exemple, lorsque qu'un problème BMC est réduit à SAT, des informations cruciales sont perdues dans la traduction. Comme le souligne cette thèse, la réintégration de ces informations perdues peut considérablement améliorer le processus de résolution. Ce travail explore des moyens d'améliorer la résolution de problèmes BMC basés sur SAT, tant dans des contextes séquentiels que parallèles, en exploitant et en valorisant les informations pertinentes extraites des caractéristiques inhérentes du problème. Cela peut impliquer l'amélioration d'heuristiques génériques existantes ou la décomposition efficace de la formule en partitionsComputer 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
34
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.
Pełny tekst źródłaStreszczenie:
Dans cette thèse, on s'intéresse au problème de satisfiabilité maximum (Max-SAT), qui consiste, étant donnée une formule propositionnelle sous forme normale conjonctive, à trouver une interprétation des variables de la formule permettant de satisfaire le plus de clauses possible. Le système de preuve le plus utilisé dans Max-SAT est basé sur la règle d'inférence par max-résolution qui est l'adaptation pour Max-SAT de la règle de résolution utilisée pour le problème SAT. La règle de résolution déduit une nouvelle clause à partir de deux clauses, ce qui permet de certifier qu'une formule est insatisfiable en déduisant de nouvelles clauses jusqu'à en déduire une contradiction, représentée par la clause vide (on parle de réfutation par résolution). L'adaptation des réfutations par résolution en réfutations valides pour Max-SAT (appelées max-réfutations) sans en augmenter considérablement la taille est un problème ouvert depuis l'introduction de la max-résolution. On propose ici deux méthodes pour adapter n'importe quelle réfutation par résolution en max-réfutation. Une autre contribution est la construction de certificats qui permettent de démontrer l'optimalité d'une solution pour le problème Max-SAT, générés en utilisant les max-réfutations calculées à partir des réfutations par résolution. Enfin, on s'intéresse à comment inférer, à partir d'une formule initiale, une information donnée (clause ou formule) par des règles d'inférence qui préservent l'équivalence Max-SAT. On propose alors un nouveau système de preuve ainsi qu'un algorithme permettant de construire n'importe quelle inférence de clauses ou de formules, ou de certifier qu'une telle inférence ne peut existerIn 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
35
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.
Pełny tekst źródłaStreszczenie:
Desde a diminuição da tendência de aumento na frequência de processadores, uma nova tendência surgiu para permitir que softwares tirem proveito de harwares mais rápidos: a paralelização. Contudo, diferente de aumentar a frequência de processadores, utilizar parallelização requer um tipo diferente de programação, a programação paralela, que é geralmente mais difícil que a programação sequencial comum. Neste contexto, a paralelização automática apareceu, permitindo que o software tire proveito do paralelismo sem a necessidade de programação paralela. Nós apresentamos aqui duas propostas: SAT-PaDdlinG e RePaSAT. SAT-PaDdlinG é um SAT Solver DPLL paralelo que roda em GPU, o que permite que RePaSAT utilize esse ambiente. RePaSAT é a nossa proposta de uma máquina paralela que utiliza o Problema SAT para paralelizar automaticamente código sequencial. Como uma GPU provê um ambiente barato e massivamente paralelo, SAT-PaDdlinG tem como objetivo prover esse paralelismo massivo a baixo custo para RePaSAT, como para qualquer outra ferramenta ou problema que utilize SAT Solvers.Since 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.
36
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/.
Pełny tekst źródłaStreszczenie:
S-boxes are the non-linear part of DES cryptosystem. Along the years it has became clear that any kind of edit to the structure of DES S-boxes increases the probability of success of breaking the algorithm, which was very carefully designed. The reason why the S-boxes were built in this way was clarified by Coppersmith, years after the publication of the encryption algorithm. The aim of this thesis is to investigate on Coppersmith’s DES S-boxes design criteria and to evaluate them by way of SAT Solving, in order to analyze the performance of SAT-Solvers for different versions of DES algorithm, in which S-boxes respect only a sample of Coppersmith’s design criteria. This aim is achieved thanks to the implementation of a Python tool: DESBoxGen. The main challenge in the design of DESBoxGen is the one of finding a way to efficiently generating S-boxes satisfying certain criteria.
37
Bé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.
Pełny tekst źródła
38
Mello, 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.
Pełny tekst źródłaStreszczenie:
Resumo: Este estudo apresenta a criação de uma plataforma para o desenvolvimento e a avaliação de algoritmos que visam resolver o problema de definir a satisfatibilidade de uma fórmula em lógica proposicional. Muitos estudos já foram realizados sobre o problema da satisfatibilidade, principalmente sobre fórmulas na Forma Normal Conjuntiva. Com isso, muitas técnicas foram desenvolvidas baseadas nas características exclusivas desse formato. O algoritmo conhecido como DPLL é utilizado como base técnica para os principais resolvedores atuais. Heurísticas de aprendizado sobre erros e melhores estruturas de representação são os pontos fortes dos algoritmos mais modernos. Porém, a utilização de um formato de representação menos restritivo, não clausal, permite aos resolvedores atuarem sobre um número maior de domínios. Testes automatizados de circuitos são um bom exemplo de aplicação para um resolvedor não clausal. Dada a diversidade de aplicações, o processo de desenvolvimento de tais algoritmos exige a decisão de qual conjunto de técnicas e heurísticas deve ser utilizado para um melhor desempenho. Nesse cenário, uma plataforma de desenvolvimento robusta, que permita a implementação de estruturas e heurísticas específicas, facilita esse processo de decisão, possibilitando, assim, análises comparativas mais precisas entre diversas soluções.
39
Ehlers, Thorsten [Verfasser]. "SAT and CP - Parallelisation and Applications / Thorsten Ehlers". Kiel : Universitätsbibliothek Kiel, 2017. http://d-nb.info/113755522X/34.
Pełny tekst źródła
40
Manthey, 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.
Pełny tekst źródłaStreszczenie:
This thesis focuses on improving the SAT solving technology. The improvements focus on two major subjects: sequential SAT solving and parallel SAT solving.
To better understand sequential SAT algorithms, the abstract reduction system Generic CDCL is introduced. With Generic CDCL, the soundness of solving techniques can be modeled. Next, the conflict driven clause learning algorithm is extended with the three techniques local look-ahead, local probing and all UIP learning that allow more global reasoning during search. These techniques improve the performance of the sequential SAT solver Riss. Then, the formula simplification techniques bounded variable addition, covered literal elimination and an advanced cardinality constraint extraction are introduced. By using these techniques, the reasoning of the overall SAT solving tool chain becomes stronger than plain resolution. When using these three techniques in the formula simplification tool Coprocessor before using Riss to solve a formula, the performance can be improved further.
Due to the increasing number of cores in CPUs, the scalable parallel SAT solving approach iterative partitioning has been implemented in Pcasso for the multi-core architecture. Related work on parallel SAT solving has been studied to extract main ideas that can improve Pcasso. Besides parallel formula simplification with bounded variable elimination, the major extension is the extended clause sharing level based clause tagging, which builds the basis for conflict driven node killing. The latter allows to better identify unsatisfiable search space partitions. Another improvement is to combine scattering and look-ahead as a superior search space partitioning function. In combination with Coprocessor, the introduced extensions increase the performance of the parallel solver Pcasso. The implemented system turns out to be scalable for the multi-core architecture. Hence iterative partitioning is interesting for future parallel SAT solvers.
The implemented solvers participated in international SAT competitions. In 2013 and 2014 Pcasso showed a good performance. Riss in combination with Copro- cessor won several first, second and third prices, including two Kurt-Gödel-Medals. Hence, the introduced algorithms improved modern SAT solving technology.
41
Burchard, Jan [Verfasser], i Bernd [Akademischer Betreuer] Becker. "Applying advanced SAT-based techniques to circuit testing". Freiburg : Universität, 2018. http://d-nb.info/1165503220/34.
Pełny tekst źródła
42
Zielke, Christian [Verfasser], i 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.
Pełny tekst źródła
43
Fliti, Tamim. "Le problème SAT : traitement dynamique et données minimales". Aix-Marseille 2, 1997. http://www.theses.fr/1997AIX22015.
Pełny tekst źródłaStreszczenie:
Le present memoire se compose de deux parties consacrees, l'une aux traitements dynamique de donnees aleatoires du probleme de satisfaisabilite sat, l'autre a l'etude sur les systemes minimaux (et inconsistants) smi en forme normale conjonctive. Dans la premiere partie nous incluons, d'une part, une methode de recherche dynamique sur plusieurs niveaux a la procedure de davis et putnam visant a valuer les meilleures variables qui produisent un plus petit arbre de calcul apres k-niveaux de recherche. Les experimentations des variantes ainsi obtenues, pour k = 2 sur des donnees 3-sat aleatoires, donnent un meilleur nombre de nuds de l'arbre de calcul, ce nombre compense le temps necessaire a la recherche des variables fournissant un plus petit arbre apres deux niveaux de recherche. D'autre part, nous essayons d'isoler l'intervalle (c/v)#i#n#f,(c/v)#s#u#p hors duquel la correspondance experimentale c/v probabilite de satisfaisabilite des donnees est constante par morceaux ; en faisant une etude sur les donnees k-sat de format (c,v), dans la zone d'entropie maximale plus particulierement. Dans la seconde partie, nous etudions divers algorithmes pour engendrer des smi de facon aleatoire, en vue notamment d'estimer les nombres n(v) de smi a v variables apparentes. Nous donnons le nombre minimum des clauses d'une donnee smi et nous construisons de smi 3-sat ayant un nombre de clauses polynomial en le nombre v des variables apparentes, plus particulierement un exemple de smi 3-sat qui n'a pas moins de v#3/(48(log v)#3) clauses
44
MANDLER, JACQUES. "Sur la transition de phase de 3-sat". Paris 6, 2000. http://www.theses.fr/2000PA066530.
Pełny tekst źródłaStreszczenie:
Dans la premiere partie, nous explorons une nouvelle methode pour trouver les valeurs asymptotiques de sommes de nombres complexes du type s n = n k = 0f n (k). Posant f n(x) = f n (nx), nous avons constate empiriquement que souvent, dans des situations ou la methode du col s'applique a i (f n) = 1 0 f n (x) dx, la quantite ni (f n) constitue un equivalent asymptotique, voire exact de s n. Des exemples typiques sont des sommes alternees de nombres reels, et, contrairement a celles jusqu'ici connues, cette procedure semble d'application assez large. Des resultats partiels sont presentes en vue d'une justification theorique, dont l'un au moins semble prometteur. Parmi nos exemples, signalons un calcul par inclusion-exclusion redonnant la borne superieure de 4. 64 pour le seuil de 3-sat obtenue en 1995 par o dubois et y. Boufkhad. La seconde partie introduit un nouvelle idee dans l'etude du probleme k-sat aleatoire, celle de formule booleenne aleatoire typique ; cette notion est ensuite appliquee a la preuve d'une borne superieur de 4. 506 pour le seuil de 3-sat, la meilleure actuellement etablie de facon rigoureuse. Bien qu'on ne puisse donner un definition canonique, une formule aleatoire typique est essentiellement une formule susceptible de sortir effectivement d'un generateur logiciel. Les techniques mises en uvre dans notre preuve proviennent principalement de l'analyse reelle et des probabilites (grandes deviations). Bien qu'il s'agisse de techniques assez repandues, la preuve elle-meme est longue et complexe.
45
Minaří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.
Pełny tekst źródłaStreszczenie:
This thesis is focused on the task of application of SAT problem and it's modifications in area of evolution logic circuit development. This task is supposed to increase speed of evaluating candidate circuits by fitness function in cases where simulation usage fails. Usage of SAT and #SAT problems make evolution of complex circuits with high input number significantly faster. Implemented solution is based on #SAT problem. Two applications were implemented. They differ by the approach to checking outputs of circuit for wrong values. Time complexity of implemented algorithm depends on logical complexity of circuit, because it uses logical formulas and it's satisfiability to evaluate logic circuits.
46
BENOIST, EMMANUEL. "Generation a delai polynomial pour le probleme sat". Caen, 2000. http://www.theses.fr/2000CAEN2002.
Pełny tekst źródłaStreszczenie:
Nous nous sommes interesses a l'etude des classes de formules cnf propositionnelles pour lesquelles il est possible de generer tous les modeles de facon efficace (i. E. Avec un delai polynomial entre chaque modele genere). Nous proposons un algorithme generique permettant de generer tous les modeles d'une formule quelconque. Nous prouvons que pour les principales classes de formules pour lesquelles on sait resoudre le probleme sat efficacement, notre algorithme genere les solutions avec un delai polynomial. Cette etude nous pousse a etudier ensuite plus en detail les classes de formules pour lesquelles la resolution unitaire est le seul outil utilise pour la generation. C'est pourquoi nous nous interessons aux formules horn etendues introduites par chandru et hooker. Malheureusement, il n'existe pas encore d'algorithme polynomial permettant de tester si une formule appartient a cette classe. Nous etudions donc la classe des formules horn etendues simples qui est une restriction de la classe pecedente pour laquelle swaminathan et wagner ont propose un algorithme de reconnaissance quadratique. Une etude de la structure de ces formules nous permet de proposer un algorithme de reconnaissance lineaire. Le resultat de plus original de ce travail est la presentation de la classe des formules ordonnees. Cette classe etend de facon naturelle celle des formules de horn, en preservant les proprietes relatives a la resolution unitaire (sat, generation de modeles). De plus, nous proposons un algorithme quadratique permettant de determiner si une formule est ordonnee-renommable. En outre nous presentons la classe des formules presque ordonnees qui englobe les formules ordonnees-renommables. Ces formules peuvent etre reconnues en temps polynomial et on peut aussi generer leurs modeles en n'utilisant que la resolution unitaire, a condition de disposer d'un ordre convenable sur les variables.
47
Bau, 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.
Pełny tekst źródłaStreszczenie:
A constraint is a formula in first-order logic expressing a relation between values of various domains. In order to solve a constraint, constructing a propositional encoding is a successfully applied technique that benefits from substantial progress made in the development of modern SAT solvers. However, propositional encodings are generally created by developing a problem-specific generator program or by crafting them manually, which often is a time-consuming and error-prone process especially for constraints over complex domains. Therefore, the present thesis introduces the constraint solver CO4 that automatically generates propositional encodings for constraints over structured finite domains written in a syntactical subset of the functional programming language Haskell. This subset of Haskell enables the specification of expressive and concise constraints by supporting user-defined algebraic data types, pattern matching, and polymorphic types, as well as higher-order and recursive functions. The constraint solver CO4 transforms a constraint written in this high-level language into a propositional formula. After an external SAT solver determined a satisfying assignment for the variables in the generated formula, a solution in the domain of discourse is derived. This approach is even applicable for finite restrictions of recursively defined algebraic data types. The present thesis describes all aspects of CO4 in detail: the language used for specifying constraints, the solving process and its correctness, as well as exemplary applications of CO4.
48
Pari, Pushkin Raj. "Several issues on the boolean satisfiability (SAT) problem". College Park, Md. : University of Maryland, 2004. http://hdl.handle.net/1903/1427.
Pełny tekst źródłaStreszczenie:
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.
49
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.
Pełny tekst źródłaStreszczenie:
The constraint satisfaction problem (CSP) is a powerful framework used in theoretical computer science for formulating a multitude of problems. The CSP over a constraint language Γ (CSP(Γ)) is the decision problem of verifying whether a set of constraints based on the relations in Γ admits a satisfying assignment or not. Temporal CSPs are a special subclass of CSPs frequently encountered in AI. Here, the relations are first-order definable in the structure (Q;<), i.e the rationals with the usual order. These problems have previously often been solved by either enumeration or SAT compilation. We study a restriction of temporal CSPs where the constraint language is limited to logical disjunctions of <-, =-, ≠- and ≤-relations, and were each constraint contains at most k such basic relations (CSP({<,=,≠,≤}∨k)). Every temporal CSP with a finite constraint language Γ is polynomial-time reducible to CSP({<,=,≠,≤}∨k) where k is only dependent on Γ. As this reduction does not increase the number of variables, the time complexity of CSP(Γ) is never worse than that of CSP({<,=,≠,≤}∨k). This makes the complexity of CSP({<,=,≠,≤}∨k) interesting to study. We develop algorithms combining enumeration and SAT compilation to solve CSP({<,=,≠,≤}∨k), and study the asymptotic behaviour of these algorithms for different classes. Our results show that all finite constraint languages Γ first order definable over (Q;<) are solvable in O*(((1/(eln(2))-ϵk)n)^n) time for some ϵk>0 dependent on Γ. This is strictly better than O*((n/(eln(2)))^n), i.e. O*((0.5307n)^n), achieved by enumeration algorithms. Some examples of upper bounds on time complexity achieved in the thesis are CSP({<}∨2) in O*((0.1839n)^n) time, CSP({<,=,≤}∨2) in O*((0.2654n)^n) time, CSP({<,=,≠}∨3) in O*((0.4725n)^n) time and CSP({<,=,≠,≤}∨3) in O*((0.5067n)^n) time. For CSP({<}∨2) this should be compared to the bound O*((0.3679n)^n), from previously known enumeration algorithms.
50
Vallade, Vincent. "Contributions à la résolution parallèle du problème SAT". Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS260.
Pełny tekst źródłaStreszczenie:
Cette thèse présente des contributions multiples et orthogonales à l'amélioration de la résolution parallèle du problème de satisfiabilité booléenne (ou problème SAT). Une instance du problème SAT est une formule propositionnelle de forme particulière (la forme normale conjonctive est la plus courante) représentant, en général, les variables et les contraintes d'un problème du monde réel, tel que la planification multi-contraintes, la vérification matérielle et logicielle ou la cryptographie. La résolution du problème SAT consiste à déterminer s'il existe une affectation des variables qui permet de satisfaire la formule. Un algorithme capable de fournir une réponse à ce problème est appelé un solveur SAT. Une vision simplifiée d'un solveur SAT est un algorithme qui va parcourir l'ensemble des combinaisons de valeurs possibles pour chaque variables jusqu'à trouver une combinaison rendant la formule vrai (la formule est SAT). Si le solveur a parcouru l'ensemble des combinaisons possibles sans trouver de solution la formule est donc UNSAT. Évidemment, cet algorithme a une complexité exponentielle, en effet le problème SAT est le premier problème à avoir été déterminé NP-complet. De nombreux algorithmes et heuristiques ont été développés pour accélérer la capacité de résolution de ce problème, principalement dans un contexte séquentiel. L’omniprésence de machines multi-cœurs a encouragé des efforts considérables dans la résolution parallèle du problème SAT. Cette thèse s’inscrit dans le prolongement de ces efforts. Les contributions apportées par cette thèse se concentrent sur la qualité du partage de l'information entre les différents travailleurs d'un solveur SAT parallèle. Une première contribution présente une méthode efficace pour mettre en œuvre un algorithme asynchrone de réduction de la taille de l'information partagées. Une deuxième contribution combine les informations extraites de la structure particulière de la formule propositionnelle avec les informations extraites dynamiquement pendant la résolution du problème par le solveur afin de créer un filtre qui maximise la qualité de l'information partagée. Enfin, une dernière contribution porte sur l'intégration d'un composant permettant de déterminer de manière probabiliste la valeur de vérité des variables permettant de rendre une formule satisfaisable. L'appel de ce composant lors du processus de résolution permet de guider plus rapidement le solveur vers une solution (si une solution existe)This 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)