A parity game tale of two counters

MaRDI QIDQ5020527zbMATH OpenFDO

Authors Tom van Dijk

Publication date 6 January 2022

Full work available at URL https://arxiv.org/abs/1807.10210, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF2019.8

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Applications of game theory (91A80)

Recommendations

• Solving counter parity games
• Solving parity games via priority promotion
• Solving parity games via priority promotion
• Attracting tangles to solve parity games
• Solving parity games in practice

Cites work

• A subexponential lower bound for the random facet algorithm for parity games
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• A superpolynomial lower bound for strategy iteration based on snare memorization
• An exponential lower bound for Cunningham's rule
• An exponential lower bound for the latest deterministic strategy iteration algorithms
• Attracting tangles to solve parity games
• Automata, logics, and infinite games. A guide to current research
• Deciding parity games in quasipolynomial time
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Efficient parallel strategy improvement for parity games
• scientific article; zbMATH DE number 7445162 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• scientific article; zbMATH DE number 1775458 (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
• Non-oblivious strategy improvement
• On model checking for the -calculus and its fragments
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• Recursive algorithm for parity games requires exponential time
• Results on the propositional \(\mu\)-calculus
• Simple fixpoint iteration to solve parity games
• Solving parity games in practice
• Solving parity games using an automata-based algorithm
• Solving parity games via priority promotion
• Solving parity games via priority promotion
• Succinct progress measures for solving parity games
• The complexity of all-switches strategy improvement
• The fixpoint-iteration algorithm for parity games
• Zielonka's recursive algorithm: dull, weak and solitaire games and tighter bounds

Cited in

(4)

• scientific article; zbMATH DE number 5995255 (Why is no real title available?)
• Cooking Your Own Parity Game Preorders Through Matching Plays
• Priority promotion with Parysian flair
• The worst-case complexity of symmetric strategy improvement

Describes a project that uses

Uses Software

• Strix
• PGSolver
• Oink

This page was built for publication: A parity game tale of two counters

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