Rozprawy doktorskie na temat „Propositional satisfiability”
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Sprawdź 25 najlepszych rozpraw doktorskich naukowych na temat „Propositional satisfiability”.
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.
Al-Saedi, Mohammad Saleh Balasim. "Extensions of tractable classes for propositional satisfiability". Thesis, Artois, 2016. http://www.theses.fr/2016ARTO0405/document.
Pełny tekst źródłaKnowledge representation and reasoning is a key issue in computer science and more particularly in artificial intelligence. In this respect, propositional logic is a representation formalism that is a good trade-off between the opposite computational efficiency and expressiveness criteria. However, unless P = NP, deduction in propositional logic is not polynomial in the worst case. So, in this thesis we propose new extensions of tractable classes of the propositional satisfiability problem. Tractable fragments of SAT play a role in the implementation of the most efficient current SAT solvers, many of thesetractable classes use the linear time unit propagation (UP) inference rule. We attempt to extend two of currently-known polynomial fragments of SAT thanks to UP in such a way that the fragments can still be recognized and solved in polynomial time. A first result focuses on Quad fragments: we establish some properties of Quad fragments and extend these fragments and exhibit promising variants. The extension is obtained by allowing Quad fixed total orderings of clauses to be accompanied with specific additional separate orderings of maximal sub-clauses. The resulting fragments extend Quad without degrading its worst-case complexity. Also, we investigate how bounded resolution and redundancy through unit propagation can play a role in this respect. The second contribution on tractable subclasses of SAT concerns extensions of one well-known Tovey’s polynomial fragment so that they also include instances that can be simplified using UP. Then, we compare two existing polynomial fragments based on UP: namely, Quad and UP-Horn. We also answer an open question about the connections between these two classes: we show that UP-Horn and some other UP-based variants are strict subclasses of S Quad, where S Quad is the union of all Quad classes obtained by investigating all possible orderings of clauses
Hansen, Stephen Lee. "Complete Randomized Cutting Plane Algorithms for Propositional Satisfiability". NSUWorks, 2000. http://nsuworks.nova.edu/gscis_etd/565.
Pełny tekst źródłaDuong, Thach-Thao Nguyen. "Improving Diversification in Local Search for Propositional Satisfiability". Thesis, Griffith University, 2014. http://hdl.handle.net/10072/365717.
Pełny tekst źródłaThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Science, Environment, Engineering and Technology
Full Text
Ferreira, Junior Valnir, i N/A. "Improvements to Clause Weighting Local Search for Propositional Satisfiability". Griffith University. Institute for Integrated and Intelligent Systems, 2007. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070823.123257.
Pełny tekst źródłaPham, Duc Nghia, i n/a. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems". Griffith University. Institute for Integrated and Intelligent Systems, 2006. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070216.143447.
Pełny tekst źródłaPham, Duc Nghia. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems". Thesis, Griffith University, 2006. http://hdl.handle.net/10072/365503.
Pełny tekst źródłaThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Full Text
Ferreira, Junior Valnir. "Improvements to Clause Weighting Local Search for Propositional Satisfiability". Thesis, Griffith University, 2007. http://hdl.handle.net/10072/365857.
Pełny tekst źródłaThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Full Text
Slater, Andrew, i andrew slater@csl anu edu au. "Investigations into Satisfiability Search". The Australian National University. Research School of Information Sciences and Engineering, 2003. http://thesis.anu.edu.au./public/adt-ANU20040310.103258.
Pełny tekst źródłaDrake, Lyndon Paul. "Combining inference and backtracking search for the propositional satisfiability problem". Thesis, University of York, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.421496.
Pełny tekst źródłaIshtaiwi, Abdelraouf. "Towards Effective Parameter-Free Clause Weighting Local Search for SAT". Thesis, Griffith University, 2008. http://hdl.handle.net/10072/366980.
Pełny tekst źródłaThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Faculty of Engineering and Information Technology
Full Text
Polash, Md Masbaul Alam. "Exploiting Structures in Combinatorial Search". Thesis, Griffith University, 2017. http://hdl.handle.net/10072/370979.
Pełny tekst źródłaThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Inst Integrated&IntelligentSys
Science, Environment, Engineering and Technology
Full Text
Namasivayam, Gayathri. "ON SIMPLE BUT HARD RANDOM INSTANCES OF PROPOSITIONAL THEORIES AND LOGIC PROGRAMS". UKnowledge, 2011. http://uknowledge.uky.edu/gradschool_diss/132.
Pełny tekst źródłaArora, Rajat. "Enhancing SAT-based Formal Verification Methods using Global Learning". Thesis, Virginia Tech, 2004. http://hdl.handle.net/10919/32987.
Pełny tekst źródłaMaster of Science
Lonlac, Konlac Jerry Garvin. "Contributions à la résolution du problème de la Satisfiabilité Propositionnelle". Thesis, Artois, 2014. http://www.theses.fr/2014ARTO0404/document.
Pełny tekst źródłaIn this thesis, we focus on propositional satisfiability problem (SAT). This fundamental problem in complexity theory is now used in many application domains such as planning, bioinformatic, hardware and software verification. Despite enormous progress observed in recent years in practical SAT solving, there is still a strong demand of efficient algorithms that can help to solve hard problems. Our contributions fit in this context. We focus on improving two of the key components of SAT solvers: clause learning and variable ordering heuristics. First, we propose a resolution method that allows to exploit hidden Boolean functions generally introduced during the encoding phase CNF to reduce the size of clauses learned during the search. Then, we propose an resolution approach based on the intensification principle that circumscribe the variables on which the solver should branch in priority at each restart. This principle allows the solver to direct the search to the most constrained sub-formula and takes advantage of the previous search to avoid exploring the same part of the search space several times. In a third contribution, we propose a new clause learning scheme that allows to derive a particular Bi-Asserting clauses and we show that their exploitation significantly improves the performance of the state-of-the art CDCL SAT solvers. Finally, we were interested to the main learned clauses database reduction strategies used in the literature. Indeed, starting from two simple strategies : random and size-bounded reduction strategies, and motivated by the results obtained from these strategies, we proposed several new effective ones that combine maintaing short clauses (of size bounded by k), while deleting randomly clauses of size greater than k. Several other efficient variants are proposed. These new strategies allow us to identify the most important learned clauses for the search process
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łaBelov, Anton. "Syntactic characterization of propositional satisfiability". 2005. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR11752.
Pełny tekst źródłaTypescript. Includes bibliographical references (leaves 90-94). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004 & res_dat=xri:pqdiss & rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation & rft_dat=xri:pqdiss:MR11752.
Pan, Guoqiang. "Complexity and structural heuristics for propositional and quantified satisfiability". Thesis, 2007. http://hdl.handle.net/1911/20686.
Pełny tekst źródłaSlater, Andrew. "Investigations into Satisfiability Search". Phd thesis, 2004. http://hdl.handle.net/1885/48193.
Pełny tekst źródła"A solution scheme of satisfiability problem by active usage of totally unimodularity property". 2003. http://library.cuhk.edu.hk/record=b5896100.
Pełny tekst źródłaThesis (M.Phil.)--Chinese University of Hong Kong, 2003.
Includes bibliographical references (leaves 93-98).
Abstracts in English and Chinese.
Table of Contents --- p.v
Abstract --- p.viii
Acknowledgements --- p.x
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Satisfiability Problem --- p.1
Chapter 1.2 --- Motivation of the Research --- p.1
Chapter 1.3 --- Overview of the Thesis --- p.2
Chapter 2 --- Satisfiability Problem --- p.4
Chapter 2.1 --- Satisfiability Problem --- p.5
Chapter 2.1.1 --- Basic Definition --- p.5
Chapter 2.1.2 --- Phase Transitions --- p.5
Chapter 2.2 --- History --- p.6
Chapter 2.3 --- The Basic Search Algorithm --- p.8
Chapter 2.4 --- Some Improvements to the Basic Algorithm --- p.9
Chapter 2.4.1 --- Satz by Chu-Min Li --- p.9
Chapter 2.4.2 --- Heuristics and Local Search --- p.12
Chapter 2.4.3 --- Relaxation --- p.13
Chapter 2.5 --- Benchmarks --- p.14
Chapter 2.5.1 --- Specific Problems --- p.14
Chapter 2.5.2 --- Randomly Generated Problems --- p.14
Chapter 2.6 --- Software and Internet Information for SAT solving --- p.16
Chapter 2.6.1 --- Stochastic Local Search Algorithms (incomplete) --- p.16
Chapter 2.6.2 --- Systematic Search Algorithms (complete) --- p.16
Chapter 2.6.3 --- Some useful Links to SAT Related Sites --- p.17
Chapter 3 --- Integer Programming Formulation for Logic Problem --- p.18
Chapter 3.1 --- SAT Problem --- p.19
Chapter 3.2 --- MAXSAT Problem --- p.19
Chapter 3.3 --- Logical Inference Problem --- p.19
Chapter 3.4 --- Weighted Exact Satisfiability Problem --- p.20
Chapter 4 --- Integer Programming Formulation for SAT Problem --- p.22
Chapter 4.1 --- From 3-CNF SAT Clauses to Zero-One IP Constraints --- p.22
Chapter 4.2 --- Integer Programming Model for 3-SAT --- p.23
Chapter 4.3 --- The Equivalence of the SAT and the IP --- p.23
Chapter 4.4 --- Example --- p.24
Chapter 5 --- Integer Solvability of Linear Programs --- p.27
Chapter 5.1 --- Unimodularity --- p.27
Chapter 5.2 --- Totally Unimodularity --- p.28
Chapter 5.3 --- Some Results on Recognition of Linear Solvability of IP --- p.32
Chapter 6 --- TU Based Matrix Research Results --- p.33
Chapter 6.1 --- 2x2 Matrix's TU Property --- p.33
Chapter 6.2 --- Extended Integer Programming Model for SAT --- p.34
Chapter 6.3 --- 3x3 Matrix's TU Property --- p.35
Chapter 7 --- Totally Unimodularity Based Branching-and-Bound Algorithm --- p.38
Chapter 7.1 --- Introduction --- p.38
Chapter 7.1.1 --- Enumeration Trees --- p.39
Chapter 7.1.2 --- The Concept of Branch and Bound --- p.42
Chapter 7.2 --- TU Based Branching Rule --- p.43
Chapter 7.2.1 --- How to sort variables based on 2x2 submatrices --- p.43
Chapter 7.2.2 --- How to sort the rest variables --- p.45
Chapter 7.3 --- TU Based Bounding Rule --- p.46
Chapter 7.4 --- TU Based Branch-and-Bound Algorithm --- p.47
Chapter 7.5 --- Example --- p.49
Chapter 8 --- Numerical Result --- p.57
Chapter 8.1 --- Experimental Result --- p.57
Chapter 8.2 --- Statistical Results of ILOG CPLEX --- p.59
Chapter 9 --- Conclusions --- p.61
Chapter 9.1 --- Contributions --- p.61
Chapter 9.2 --- Future Work --- p.62
Chapter A --- The Coefficient Matrix A for Example in Chapter 7 --- p.64
Chapter B --- The Detailed Numerical Information of Solution Process for Exam- ple in Chapter 7 --- p.66
Chapter C --- Experimental Result --- p.67
Chapter C.1 --- "# of variables: 20, # of clauses: 91" --- p.67
Chapter C.2 --- "# of variables: 50, # of clauses: 218" --- p.70
Chapter C.3 --- # of variables: 75,# of clauses: 325 --- p.73
Chapter C.4 --- "# of variables: 100, # of clauses: 430" --- p.76
Chapter D --- Experimental Result of ILOG CPLEX --- p.80
Chapter D.1 --- # of variables: 20´ة # of clauses: 91 --- p.80
Chapter D.2 --- # of variables: 50,#of clauses: 218 --- p.83
Chapter D.3 --- # of variables: 75,# of clauses: 325 --- p.86
Chapter D.4 --- "# of variables: 100, # of clauses: 430" --- p.89
Bibliography --- p.93
Katsirelos, George. "Nogood Processing in CSPs". Thesis, 2008. http://hdl.handle.net/1807/16737.
Pełny tekst źródłaDavies, Jessica. "Solving MAXSAT by Decoupling Optimization and Satisfaction". Thesis, 2013. http://hdl.handle.net/1807/43539.
Pełny tekst źródłaSilverthorn, Bryan Connor. "A probabilistic architecture for algorithm portfolios". 2012. http://hdl.handle.net/2152/19828.
Pełny tekst źródłatext
Lierler, Yuliya. "SAT-based answer set programming". Thesis, 2010. http://hdl.handle.net/2152/ETD-UT-2010-05-888.
Pełny tekst źródłatext
Χαρατσάρης, Δημήτριος. "Υλοποίηση διαδικτυακού προσομοιωτή για αλγορίθμους επίλυσης προβλημάτων SAT". Thesis, 2012. http://hdl.handle.net/10889/5754.
Pełny tekst źródłaThis diploma dissertation deals with SAT solvers, algorithms for the Boolean satisfiability problem. It was produced in the Wire Communications Laboratory of the Electrical and Computer Engineering Department of the University of Patras. Its aim is to create a simulator for these algorithms, accessible to anyone via the Internet. An introduction to the field of Artificial Intelligence and more specifically to Propositional Calculus was given as well as the necessary groundwork to understand the problem and its solution approaches. The simulation implementation was developed in Java
Manthey, Norbert. "Towards Next Generation Sequential and Parallel SAT Solvers". Doctoral thesis, 2014. https://tud.qucosa.de/id/qucosa%3A28471.
Pełny tekst źródła