Sökning: "Boolean Satisfiability"

Visar resultat 1 - 5 av 13 avhandlingar innehållade orden Boolean Satisfiability.

1. 1. Exact Algorithms for Exact Satisfiability Problems

   Författare :Vilhelm Dahllöf; Peter Jonsson; Fedor Fomin; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NP-hardness; exact algorithms; satisfiability; exact satisfiability; Computer science; Datalogi;

   Sammanfattning : This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. LÄS MER

3. 2. On random satisfiability and optimization problems

   Författare :Joel Larsson; Klas Markström; Roland Häggkvist; Victor Falgas Ravry; Stefanie Gerke; Umeå universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Random graphs; k-SAT; satisfiability; coupon collector; random cover time; threshold phenomenon; concentration of measure; combinatorial probability; perfect matching; assignment problem; local graph limit; mean-field; Mathematics; matematik;

   Sammanfattning : In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. LÄS MER

4. 3. Using Formal Methods for Product and Production Development -- Industrial Applications for Boolean Satisfiability Solvers

   Författare :Alexey Voronov; Chalmers tekniska högskola; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Formal Methods; Industrial Automation; Boolean Satisfiability; Product and Production Development;

   Sammanfattning : Highly customized products and frequent changes in the production systems pose high demands on engineers. The amount of data and the complexity of the relations within the data are high. Thus, it is both error-prone and time consuming to analyze the data without software support. LÄS MER

5. 4. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction

   Författare :Cenny Wenner; Johan Håstad; Irit Dinur; Numerical Analysis and Computer Science (NADA) Faculty of Science Stockholm University; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Optimization; NP; Approximation; Approximability; Inapproximability; Constraint Satisfaction; CSP; Boolean Analysis; Satisfiability; SAT; Acyclic Subgraph; Betweenness; Unique Games; Computer Science; Datalogi;

   Sammanfattning : Problem solving is an integral aspect of modern society and includes such tasks as picking the fastest route to work, optimizing a production line, scheduling computer tasks, placing new bus stops, or picking a meal from available ingredients.We study the hardness of solving Constraint Satisfaction Problems (CSPs). LÄS MER

7. 5. On Formal Methods for Large-Scale Product Configuration

   Författare :Alexey Voronov; Chalmers tekniska högskola; []
   Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; NATURVETENSKAP; NATURAL SCIENCES; constraint satisfaction; knowledge compilation; Boolean satisfiability; supervisory control theory; product configuration;

   Sammanfattning : In product development companies mass customization is widely used to achieve better customer satisfaction while keeping costs down. To efficiently implement mass customization, product platforms are often used. A product platform allows building a wide range of products from a set of predefined components. LÄS MER