SpringerLink - Book Chapter

Ambiguous Classes in the Games μ-Calculus Hierarchy

Book Series

Lecture Notes in Computer Science

Publisher

Springer Berlin / Heidelberg

ISSN

0302-9743 (Print) 1611-3349 (Online)

Volume

Volume 2620/2003

Book

Foundations of Software Science and Computation Structures

DOI

10.1007/3-540-36576-1

2003

ISBN

978-3-540-00897-2

DOI

10.1007/3-540-36576-1_5

Pages

70-86

Subject Collection

Computer Science

SpringerLink Date

Wednesday, January 01, 2003

Ambiguous Classes in the Games μ-Calculus Hierarchy

André Arnold⁵ and Luigi Santocanale⁵

(5)	LaBRI, Université Bordeaux 1, Bordeaux

Abstract

Every parity game is a combinatorial representation of a closed Boolean μ-term. When interpreted in a distributive lattice every Boolean μ-term is equivalent to a fixed-point free term. The alternationdepth hierarchy is therefore trivial in this case. This is not the case for non distributive lattices, as the second author has shown that the alternation -depth hierarchy is infinite.

In this paper we show that the alternation-depth hierarchy of the games μ-calculus, with its interpretation in the class of all complete lattices, has a nice characterization of ambiguous classes: every parity game which is equivalent both to a game in σ_n+1 and to a game π_n+1 is also equivalent to a game obtained by composing games in σ_n and π_n.

The second author acknowledges .nancial support from the European Commission through an individual Marie Curie fellowship.

André Arnold
Email: andre.arnold@labri.fr

Luigi Santocanale
Email: santocan@labri.fr

Ambiguous Classes in the Games μ-Calculus Hierarchy

Fulltext Preview (Small, Large)