Search for dissertations about: "constraint predicates"

Showing result 1 - 5 of 6 swedish dissertations containing the words constraint predicates.

  2. 1. Analysis, synthesis and application of automaton-based constraint descriptions

    Author : María Andreína Francisco Rodríguez; Justin Pearson; Pierre Flener; Christopher Jefferson; Uppsala universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; constraint programming; constraint predicates; global constraints; automata; automaton-described constraint predicates; automaton-induced constraint decompositions; implied constraints; time-series constraints; transducers; automaton invariants; Computer Science; Datavetenskap;

    Abstract : Constraint programming (CP) is a technology in which a combinatorial problem is modelled as a conjunction of constraints on variables ranging over given initial domains, and optionally an objective function on the variables. Such a model is given to a general-purpose solver performing systematic search to find constraint-satisfying domain values for the variables, giving an optimal value to the objective function. READ MORE

  4. 2. Beating a Random Assignment : Approximating Constraint Satisfaction Problems

    Author : Gustav Hast; Johan Håstad; Uri Zwick; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Datalogi; Computer science; Datalogi;

    Abstract : An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. READ MORE

  5. 3. 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 : 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

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

    Author : Cenny Wenner; Johan Håstad; Viggo Kann; Irit Dinur; Stockholms universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Combinatorial Optimization; Complexity Theory; Approximation; Approximability; Inapproximability; Computational Hardness; NP; Optimization; Constraint Satisfaction; Kombinatorisk optimering; Komplexitetsteori; Beräkningsteori; Approximation; Approximerbarhet; Beräkningssvårighet; NP; Optimering; Vilkorssatisfiering; Vilkorsuppfyllning; Vilkorstillfredställand; datalogi; Computer Science;

    Abstract : Combinatorial optimization include such tasks as finding the quickest route to work, scheduling jobs to specialists, and placing bus stops so as to minimize commuter times. We consider problems where one is given a collection of constraints with the objective of finding an assignment satisfying as many constraints as possible, also known as Constraint Satisfaction Problems (CSPs). READ MORE

  7. 5. Contributions to program- and specification-based test data generation

    Author : Jon Edvardsson; Linköpings universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Computer science; Datavetenskap;

    Abstract : Software testing is complex and time consuming. One way to reduce testing effort is to automatically generate test data. In the first part of this thesis we consider a framework by Gupta et al. for generating tests from programs. READ MORE