scientific article; zbMATH DE number 7533361

DOI10.4230/LIPICS.CSL.2018.36MaRDI QIDQ5079761zbMATH OpenFDO

Authors Sven Schewe, Alexander Weinert, Martín G. Zimmermann

Publication date 28 May 2022

Full work available at URL https://doi.org/10.4230/LIPICS.CSL.2018.36

zbMATH Keywords

infinite gamesparity gamesquantitative games

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving topology, set theory, or logic (91A44)

Recommendations

• Parity games with weights
• Generalized Parity Games
• Weighted and roughly weighted simple games
• A brief excursion to parity games
• Weighted games of best choice
• Parity and Streett games with costs
• Parity games on undirected graphs
• Values of games with weighted graphs
• A matrix-based approach to parity games

Cites work

• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• A Deterministic Subexponential Algorithm for Solving Parity Games
• A modal \(\mu\) perspective on solving parity games in quasi-polynomial time
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• An improved algorithm for the evaluation of fixpoint expressions
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Deciding parity games in quasipolynomial time
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Energy parity games
• Finitary winning in \({\omega}\)-regular games
• Formal Methods for Components and Objects
• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• scientific article; zbMATH DE number 6790166 (Why is no real title available?)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• Infinite-state games with finitary conditions
• McNaughton games and extracting strategies for concurrent programs
• On promptness in parity games
• Parity and Streett games with costs
• Results on the propositional \(\mu\)-calculus
• Solving parity games in big steps
• Succinct progress measures for solving parity games
• Symmetric strategy improvement
• The complexity of mean payoff games on graphs
• Tools and Algorithms for the Construction and Analysis of Systems

Cited in

(12)

• Quantitative reductions and vertex-ranked infinite games
• On weighted balls-into-bins games
• Solving counter parity games
• Cost-parity and cost-Streett games
• Cooking Your Own Parity Game Preorders Through Matching Plays
• Quantitative reductions and vertex-ranked infinite games
• Resource-aware automata and games for optimal synthesis
• The Theory of Universal Graphs for Infinite Duration Games
• Parity games with weights
• Easy to win, hard to master: optimal strategies in parity games with costs
• Mathematical Foundations of Computer Science 2005
• Parity and Streett games with costs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5079761)