Parity games with weights

MaRDI QIDQ5232902zbMATH OpenFDO

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

Publication date 13 September 2019

Full work available at URL https://arxiv.org/abs/1804.06168

zbMATH Keywords

infinite gamesparity gamesquantitative games

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7533361
• scientific article; zbMATH DE number 6790166
• Parity and Streett games with costs
• Easy to win, hard to master: optimal strategies in parity games with costs
• Cost-parity and cost-Streett games

Cites work

• 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?)
• A Deterministic Subexponential Algorithm for Solving Parity Games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• A modal \(\mu\) perspective on solving parity games in quasi-polynomial time
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• An improved algorithm for the evaluation of fixpoint expressions
• Borel determinacy
• Deciding parity games in quasipolynomial time
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Energy parity games
• 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
• Model Checking Probabilistic Timed Automata with One or Two Clocks
• On promptness in parity games
• Parity and Streett games with costs
• Parity games with weights
• Results on the propositional \(\mu\)-calculus
• Solving parity games in big steps
• Symmetric strategy improvement
• The complexity of mean payoff games on graphs
• Tools and Algorithms for the Construction and Analysis of Systems

Cited in

(12)

• scientific article; zbMATH DE number 7533361 (Why is no real title available?)
• Optimal strategies in weighted limit games
• Energy parity games
• Easy to win, hard to master: optimal strategies in parity games with costs
• Parity games with weights
• Parity and Streett games with costs
• Solving counter parity games
• Mathematical Foundations of Computer Science 2005
• On weighted balls-into-bins games
• New algorithms for combinations of objectives using separating automata
• Cooking Your Own Parity Game Preorders Through Matching Plays
• Cost-parity and cost-Streett games

This page was built for publication: Parity games with weights

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