Lecture Notes in Computer Science, 2001, Volume 2088/2001, 263-271, DOI: 10.1007/3-540-44674-5_22

Implementation of a Strategy Improvement Algorithm for Finite-State Parity Games

Dominik Schmitz and Jens Vöge

View Related Documents

Abstract

An implementation of a recent algorithm (Vüge, Jurdzinski, to appear in CAV 2000) for the construction of winning strategies in infinite games is presented. The games under consideration are “finite-state parity games”, i.e. games over finite graphs where the winning condition is inherited from ω-automata with parity acceptance. The emphasis of the paper is the development of a user interface which supports the researcher in case studies for algorithms of ω-automata theory. Examples of such case studies are provided which might help in evaluating the (so far open) asymptotic runtime of the presented algorithm.
Both authors are supported by the Deutsche Forschungsgemeinschaft (DFG), project Th 352/5-3.

Fulltext Preview

Image of the first page of the fulltext document