EDP Sciences Journals List

• All issues
• Special issues
• E-First
• Forthcoming
• News
• Search

Home Document

Subscriber Authentication Point

Journal homepage

Table of contents

 Previous article  Next article 

• Abstract
• - PDF (147.2 KB)
• - References

Services

• Same authors
  - Google Scholar
  - EDP Sciences database
• Related articles
  
  - EDP Sciences database
•  
• Recommend this article
• Download citation
• Alert me when this article is cited
• Alert me when this article is corrected

Bookmarking

• BibSonomy	CiteUlike
  Connotea	Del.icio.us
  Digg	Facebook

• EDPS account
• Email-alert

Issue		Theoret. Informatics Appl. Volume 33, Number 4/5, July-October 1999
Page(s)		329 - 339
DOI		10.1051/ita:1999121

DOI: 10.1051/ita:1999121
Theoret. Informatics Appl. 33 (1999) 329-339

The $\mu$-calculus alternation-depth hierarchy is strict on binary trees

André Arnold
LaBRI, Université de Bordeaux 1, CNRS, 351 cours de la Libération, 33405 Talence, France.

Received November 5, 1998. Revised May 1, 1999.

Abstract: In this paper we give a simple proof that the alternation-depth hierarchy of the $\mu$-calculus for binary trees is strict. The witnesses for this strictness are the automata that determine whether there is a winning strategy for the parity game played on a tree.

Résumé: Nous donnons dans cet article une preuve simple que la hiérarchie d'alternance de points fixes pour le $\mu$-calcul sur les arbres binaires est infinie. Les témoins en sont les automates qui déterminent l'existence d'une stratégie gagnante pour le jeu de parité joué sur un arbre binaire.

Keywords and phrases: Mu-calcul, alternating automata, parity games.

AMS Subject Classification: 68Q68, 03D05

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link containsarticle metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means:

• if your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages,
• you can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library,
• you can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.

Back to top

• EDP Sciences
• Credits
• Contacts