Sökning: "parity games"

Hittade 3 avhandlingar innehållade orden parity games.

  1. 1. Games and Probabilistic Infinite-State Systems

    Författare :Sven Sandberg; Parosh Abdulla; Luca de Alfaro; Uppsala universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; program verification; model checking; determinacy; strategy improvement; infinite games; parity games; mean payoff games; stochastic games; Büchi games; reachability games; limiting average; limiting behavior; Markov chains; infinite-state systems; lossy channel systems; vector addition systems; noisy Turing machines; Computer science; Datavetenskap;

    Sammanfattning : Computer programs keep finding their ways into new safety-critical applications, while at the same time growing more complex. This calls for new and better methods to verify the correctness of software. We focus on one approach to verifying systems, namely that of model checking. LÄS MER

  3. 2. Combinatorial Optimization for Infinite Games on Graphs

    Författare :Henrik Björklund; Sergei Vorobyov; Erich Grädel; Uppsala universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; infinite games; combinatorial optimization; randomized algorithms; model checking; strategy evaluation functions; linear programming; iterative improvement; local search; Computer science; Datavetenskap;

    Sammanfattning : Games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in computer- aided verification, automata theory, logic, complexity theory, computational biology, etc. LÄS MER

  4. 3. 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