A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy: Part II

Détails

ID Serval
serval:BIB_137D145FE79A
Type
Article: article d'un périodique ou d'un magazine.
Collection
Publications
Institution
Titre
A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy: Part II
Périodique
RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Auteur⸱e⸱s
Cabessa J., Duparc J.
ISSN
0988-3754
Statut éditorial
Publié
Date de publication
07/2009
Peer-reviewed
Oui
Volume
43
Numéro
3
Pages
463-515
Langue
anglais
Résumé
The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed ω-semigroups of width 2 and height ωω. This paper completes the description of this algebraic hierarchy. We first give a purely algebraic decidability procedure of this partial ordering by introducing a graph representation of finite pointed ω-semigroups allowing to compute their precise Wagner degrees. The Wagner degree of any ω-rational language can therefore be computed directly on its syntactic image. We then show how to build a finite pointed ω-semigroup of any given Wagner degree. We finally describe the algebraic invariants characterizing every degree of this hierarchy.
Mots-clé
ω-automata, ω-rational languages, ω-semigroups, infinite games, hierarchical games, Wadge game, Wadge hierarchy, Wagner hierarchy
Web of science
Création de la notice
07/01/2010 16:34
Dernière modification de la notice
27/11/2019 6:19
Données d'usage