The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed -semigroups of width 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.
Keywords: $\omega $-automata, $\omega $-rational languages, $\omega $-semigroups, infinite games, hierarchical games, Wadge game, Wadge hierarchy, Wagner hierarchy
@article{ITA_2009__43_3_463_0,
author = {Cabessa, J\'er\'emie and Duparc, Jacques},
title = {A game theoretical approach to the algebraic counterpart of the {Wagner} hierarchy : part {II}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {463--515},
year = {2009},
publisher = {EDP-Sciences},
volume = {43},
number = {3},
doi = {10.1051/ita/2009007},
mrnumber = {2541208},
zbl = {1175.03022},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2009007/}
}
TY - JOUR AU - Cabessa, Jérémie AU - Duparc, Jacques TI - A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part II JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2009 SP - 463 EP - 515 VL - 43 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2009007/ DO - 10.1051/ita/2009007 LA - en ID - ITA_2009__43_3_463_0 ER -
%0 Journal Article %A Cabessa, Jérémie %A Duparc, Jacques %T A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part II %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2009 %P 463-515 %V 43 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2009007/ %R 10.1051/ita/2009007 %G en %F ITA_2009__43_3_463_0
Cabessa, Jérémie; Duparc, Jacques. A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : part II. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 463-515. doi: 10.1051/ita/2009007
Cité par Sources :