Loading...
Please wait, while we are loading the content...
Similar Documents
Deciding the Winner in Parity Games Is in UP ∩ co-UP
| Content Provider | Semantic Scholar |
|---|---|
| Author | Jurdzinski, Marcin |
| Copyright Year | 2017 |
| Abstract | We observe that the problem of deciding the winner in mean payoff games is in the complexity class UP ∩ 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 μ-calculus model checking are in UP ∩ co-UP. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.dcs.warwick.ac.uk/~mju/Papers/Jur98-IPL.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |