- Abstract:
-
In earlier work Bradfield found a link between finite differences formed by $Sigma^0_2$ sets and the mu-arithmetic introduced by Lubarski. We extend this approach into the transfinite: in allowing countable disjunctions we show that this kind of extended mu-calculus matches neatly to the transfinite difference hierarchy of $Sigma^0_2$ sets. The difference hierarchy is intimately related to parity games. When passing to infinitely many priorities, it might not longer be true that there is a positional winning strategy. However, if such games are derived from the difference hierarchy, this property still holds true. In the second part, we use the more refined Wadge hierarchy to understand further the links established in the first part, by connecting game-theoretic operations to operations on Wadge degrees.
- Copyright:
- 2010 by the authors.
- Links To Paper
- 1st Link
- Bibtex format
- @Misc{EDI-INF-RR-1366,
- author = {
Julian Bradfield
and Jacques Duparc
and Sandra Quickert
},
- title = {Fixpoint alternation and the Wadge hierarchy},
- year = 2010,
- month = {Mar},
- url = {http://homepages.inf.ed.ac.uk/jcb/Research/fixwadge.pdf},
- }
|