Deciding the winner in parity games is in UP intersection co-UP

We observe that the problem of deciding the winner in mean payoff games is in the complexity class UP intersection co-UP. We also show a simple reduction from parity games to mean payoff games. From this it follows that deciding the winner in parity games and the modal mu -calculus model checking ar...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1998-11, Vol.68 (3), p.119-124
Main Author: Jurdzinski, Marcin
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We observe that the problem of deciding the winner in mean payoff games is in the complexity class UP intersection co-UP. We also show a simple reduction from parity games to mean payoff games. From this it follows that deciding the winner in parity games and the modal mu -calculus model checking are in UP intersection co-UP.
ISSN:0020-0190