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

@inproceedings{Schmitz2000ImplementationOA,
title={Implementation of a Strategy Improvement Algorithm for Finite-State Parity Games},
author={Dominik Schmitz and Jens V{\"o}ge},
booktitle={CIAA},
year={2000}
}
• Published in CIAA 24 July 2000
• Computer Science
An implementation of a recent algorithm (Voge, 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…
10 Citations

### Strategien in unendlichen Spielen mit Liveness-Gewinnbedingungen: Syntheseverfahren, Optimierung und Implementierung

In this thesis we develop methods for the solution of infinite games and present implementations of corresponding algorithms in the framework of a platform for the experimental study of automata

### An experimental study of algorithms and optimisations for parity games, with an application to

The practical use of various optimisation techniques for solving parity games is investigated, showing that decomposition into strongly connected components and applying efficient algorithms for special cases are highly beneficial and the theoretic dependency on the number of priorities manifests itself in practice.

### Timed Control Synthesis for External Specifications

• Mathematics, Computer Science
STACS
• 2002
The problem of control synthesis for a timed plant and an external timed specification, modelled as timed automata is studied and it is shown that for deterministic specifications, if there is a controller at all, then there is one which uses the combined resources of the plant and specification.

### SOLVING BOOLEAN EQUATION SYSTEMS

An approach to solve a general form Boolean equation system, which simplifies the process of finding the solution by dividing the system into more simple subsystems and solving these by optimized procedures, is introduced and analyzed.

### Techniques for solving Boolean equation systems

This thesis presents a general framework that allows for dividing Boolean equation systems into individual blocks and solving these blocks in isolation with special techniques, and gives a translation of the problem of solving a general form Boolean equation system into the issue of finding a stable model of a logic program.

### A Bibliography of Papers in Lecture Notes in Computer Science (2003) (Part 1 of 4)

(2 + ε) [?]. (2) [?]. + [?, ?]. {0, ∗, 1} [?]. 0, 1 [?]. 0− 1 [?, ?]. 1 [?, ?]. 2 [?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?]. 2 [?]. 3 [?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?,

### Symbolic Synthesis of Finite-State Controllers for Request-Response Specifications

• Computer Science
CIAA
• 2003
A method to solve certain infinite games over finite state spaces and apply this for the automatic synthesis of finitestate controllers and a theoretical solution which synthesizes a finite-state controller for satisfiable specifications is sketched.

### A Discrete Strategy Improvement Algorithm for Solving Parity Games

• Computer Science
CAV
• 2000
A discrete strategy improvement algorithm is given for constructing winning strategies in parity games, thereby providing also a new solution of the model-checking problem for the modal μ-calculus.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8445085,"math_prob":0.7915752,"size":6137,"snap":"2022-40-2023-06","text_gpt3_token_len":1338,"char_repetition_ratio":0.1454427,"word_repetition_ratio":0.12607759,"special_character_ratio":0.21704416,"punctuation_ratio":0.14864865,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.96902114,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-09-29T02:05:32Z\",\"WARC-Record-ID\":\"<urn:uuid:f68fc411-5061-484b-bf78-c75817ec6eba>\",\"Content-Length\":\"358672\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:9b0a09ed-06d4-4348-8c5a-be0d14ce5e1e>\",\"WARC-Concurrent-To\":\"<urn:uuid:42e77bbb-fc24-4fba-94b1-2740dc4b5af8>\",\"WARC-IP-Address\":\"18.154.227.97\",\"WARC-Target-URI\":\"https://www.semanticscholar.org/paper/Implementation-of-a-Strategy-Improvement-Algorithm-Schmitz-V%C3%B6ge/8532dddea9f3dbc666b7ea51da19a401ad164110\",\"WARC-Payload-Digest\":\"sha1:R7DIXIR52ETD75A7KAW6TNYJJ6MQ4HTS\",\"WARC-Block-Digest\":\"sha1:IZL62HCMGERKH65SPAKD7YFV2XTS4N7E\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030335303.67_warc_CC-MAIN-20220929003121-20220929033121-00268.warc.gz\"}"}