Search for dissertations about: "Boolean satisfiability"

Showing result 1 - 5 of 12 swedish dissertations containing the words Boolean satisfiability.

  1. 1. Exact Algorithms for Exact Satisfiability Problems

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

    Abstract : 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. READ MORE

  2. 2. On random satisfiability and optimization problems

    Author : Joel Larsson; Klas Markström; Roland Häggkvist; Victor Falgas Ravry; Stefanie Gerke; Umeå universitet; []
    Keywords : NATURAL SCIENCES; NATURVETENSKAP; 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;

    Abstract : 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. READ MORE

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

    Author : Alexey Voronov; Chalmers University of Technology; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Formal Methods; Industrial Automation; Boolean Satisfiability; Product and Production Development;

    Abstract : 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. READ MORE

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

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

    Abstract : 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). READ MORE

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

    Author : Alexey Voronov; Chalmers University of Technology; []
    Keywords : NATURVETENSKAP; TEKNIK OCH TEKNOLOGIER; NATURAL SCIENCES; ENGINEERING AND TECHNOLOGY; constraint satisfaction; knowledge compilation; Boolean satisfiability; supervisory control theory; product configuration;

    Abstract : 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. READ MORE