Informatics Report Series


Report   

EDI-INF-RR-1366


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Fixpoint alternation and the Wadge hierarchy
Authors: Julian Bradfield ; Jacques Duparc ; Sandra Quickert
Date:Mar 2010
Publication Type:Other Publication Status:Other
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},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh