Algorithms for Stochastic Parity Games

Abstract

A stochastic graph game is played by two-players on a game graph with probabilistic transitions. We present a strategy improvement algorithm for stochastic graph games with omega-regular conditions specified as parity objectives. From the strategy improvement algorithm we obtain a randomized sub-exponential time algorithm to solve stochastic parity games.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2005
Accession Number
ADA603293

Entities

People

  • Krishnendu Chatterjee
  • Thomas Henzinger

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • California
  • Computer Science
  • Information Operations
  • Iterations
  • Linear Programming
  • Markov Chains
  • Mathematics
  • Polynomials
  • Probability
  • Probability Distributions
  • Random Walk
  • Sequences
  • Switches
  • Theorems
  • Transitions

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Game Theory.