Solving parity games via priority promotion

Conference item

We consider parity games, a special form of two-player infinite-duration games on numerically labelled graphs, whose winning condition requires that the maximal value of a label occurring infinitely often during a play be of some specific parity. The problem has a rather intriguing status from a complexity theoretic viewpoint, since it belongs to the class UPTime ∩ CoUPTime, and still open is the question whether it can be solved in polynomial time. Parity games also have great practical interest, as they arise in many fields of theoretical computer science, most notably logic, automata theory, and formal verification. In this paper, we propose a new algorithm for the solution of the problem, based on the idea of promoting vertices to higher priorities during the search for winning regions. The proposed approach has nice computational properties, exhibiting the best space complexity among the currently known solutions. Experimental results on both random games and benchmark families show that the technique is also very effective in practice.

Authors: Benerecetti, M; Dell Erba, D; Mogavero, F

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Host title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
• Journal: Lecture Notes in Computer Science
• Publication date: 2016-07-13
• Acceptance date: 2016-04-15
• DOI: 10.1007/978-3-319-41540-6_15
• ISSN: 1611-3349 and 0302-9743
• ISBN: 9783319415390