Simple fixpoint iteration to solve parity games

MaRDI QIDQ5020529zbMATH OpenFDO

Authors Tom van Dijk, Bob Rubbens

Publication date 6 January 2022

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

Mathematics Subject Classification ID

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

Recommendations

• The fixpoint-iteration algorithm for parity games
• Two local strategy iteration schemes for parity game solving
• Solving parity games in practice
• scientific article; zbMATH DE number 1670778
• Quasipolynomial computation of nested fixpoints

Cites work

• A comparison of BDD-based parity game solvers
• Attracting tangles to solve parity games
• Certification for -calculus with winning strategies
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• 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
• Monadic second order logic on tree-like structures
• On model checking for the -calculus and its fragments
• Results on the propositional \(\mu\)-calculus
• Solving parity games in practice
• Solving parity games using an automata-based algorithm
• Solving parity games via priority promotion
• Strix
• Succinct progress measures for solving parity games
• The fixpoint-iteration algorithm for parity games
• The mu-calculus and Model Checking

Cited in

(3)

• A parity game tale of two counters
• scientific article; zbMATH DE number 7455738 (Why is no real title available?)
• Justifications and a reconstruction of parity game solving algorithms

Describes a project that uses

Uses Software

• Strix
• PGSolver
• Oink

This page was built for publication: Simple fixpoint iteration to solve parity games

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