A pseudo-quasi-polynomial algorithm for mean-payoff parity games

DOI10.1145/3209108.3209162zbMath1452.91053arXiv1803.04756OpenAlexW3102493341MaRDI QIDQ5145306

Laure Daviaud, Martin Jurdziński, Ranko Lazić

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 2-person games (91A05) Games involving graphs (91A43)

Related Items (11)

The Theory of Universal Graphs for Infinite Duration Games ⋮ Unnamed Item ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simple stochastic games with almost-sure energy-parity objectives are in NP and conp ⋮ Unnamed Item ⋮ Improving parity games in practice ⋮ Quasipolynomial computation of nested fixpoints ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games

This page was built for publication: A pseudo-quasi-polynomial algorithm for mean-payoff parity games