Dissertation > Excellent graduate degree dissertation topics show

The Enhancement Techniques to SMT Solvers

Author: HuoXiang
Tutor: WuWeiMin
School: Beijing Jiaotong University
Course: Computer science and technology
Keywords: Satisfiability(SAT) Satisfiability Modulo Theories(SMT) Optimization Conflict analysis Preprocessing
CLC: TP391.7
Type: Master's thesis
Year: 2011
Downloads: 20
Quote: 0
Read: Download Dissertation

Abstract


In the age of remarkable development of IC technology, the complexity of both hardware and software designs are increasing rapidly. In addition, there are some new challenges for designing and developing new products, especially for guaranteeing security, reliability and soundness for specific requirements. To solve the new problems, computer aided verification and testing tools are exploited. Both Satisfiability(SAT) and Satisfiability Modulo Theories(SMT) have become hotspots in the last decade. With the improvements to relevant techniques, SAT/SMT tools have found many applications in various regions. In this thesis, a SMT solver is improved and applied in optimization problems, which is a region a SMT may play important roles.Concretely, we have made the following efforts to enhance both the performance and the functionality of a SMT solver:1. Based on the study of current conflict analysis techniques, a new method is proposed. The goal of our approach is to decrease the number of conflicts during the search process and fully utilize these conflict nodes to generate more effective and more concise conflict clauses. Although our approach may increase the number of additional clauses to the clause library, with these more informational clauses, the solver can avoid more conflict in the future and thus runs faster.2. We have studied and improved CNF preprocessing techniques. The preprocessing will simplify CNF formula before starting the solving process. One feature of a modern SAT solver is their performance depends on the way the relations between variables are expressed. For example, a CNF formula with more asserting clauses, a clause with less literals, will be more helpful for solving the problem sooner. This is the main source of ideas we propose to handle the problem.3. We extend a SMT solver for optimization applications. We propose a novel method to tune a SMT solver for solving optimization problems. Our inspiration comes from the necessary conditions for extrema of multivariable functions. In our work, such necessary conditions are added to the clause library of the Boolean abstraction of the SMT problem. All extrema are enumerated through the DPLL procedure among which the optimal one can be acquired. The feasibility of the method is demonstrated by experiments. Based on SATEEn, a SMT solver developed by VLSI/CAD Research Group in University of Colorado at Boulder, we implement our method with C and lex&yacc, and conduct some experiments to prove soundness and feasibility of our approach.

Related Dissertations

  1. Development of the Platform for Compressor Optimization Design and Aerodynamic Optimization Design in the Transonic Compressor,TH45
  2. Investigation of Turbine S2 Stream Surface Direct Problem Aerodynamic Optimization Design,V235.11
  3. Reseach on Optimal Control of Elevator Group Based upon Ant Colony Algorithm,TU857
  4. Research on High Efficiency Interior Permanent Magnet Synchronous Motor,TM341
  5. Application of Interior-Point Theory for Reactive Power Optimization in Large Power Systems,TM714.3
  6. The Basic Research of Axial Flux Inductor Type High Temperature Superconducting Motor,TM37
  7. The Optimization of AVS Video Decoder on the PC Platform and Improvement of Field Decoding,TN919.81
  8. Research on Stability of Hierarchical Sattellite Network,TN927.23
  9. Query Processing and Optimization in Massive Multi-Database Integration,TP311.13
  10. Research on Feature Extraction and Classification of Tongue Shape and Tooth-Marked Tongue in TCM Tongue Diagnosis,TP391.41
  11. Studies on Fermentation Optimization, Purification and Enzyme Characteristics of Lipase from Aspergillus Oryzae FS-1,TQ925.6
  12. Large the Hongshan iron ore mine personnel tracking positioning system optimization study,TN929.5
  13. Computing Minimum Distance between Curves/Surfaces Based on PSO Algorithm,O182
  14. Analysis of Nutritional Compositions and Quality of Shishen (Eremurus Chinensis Fedtsch.),S647
  15. 1 - deoxynojirimycin synthetic route design and process optimization,TQ463.5
  16. Optimization of Fermentation Conditions, Purification, Cloning and Expression of a Cold-active Lipase from Pseudomonas Sp.RT-1,TQ925
  17. Breeding of Fungal α-amylase High-producing Strain by Genome Shuffling,TQ925
  18. Hot air drying characteristics of lettuce osmotic dehydration mass transfer kinetics and permeability,TS255.52
  19. Study on Application of Red Yeast Rice in Fermented Sausage,TS251.65
  20. Domestication of Acidithiobacillus Ferroxidans and Its Application to Bio-desulfuration of Coal,X701.3
  21. Active Power Filter and Its Application in Distribution Network,TN713.8

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Machine-assisted technology
© 2012 www.DissertationTopic.Net  Mobile