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.

Voir la notice de l'article dans Numdam

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.

DOI : 10.1051/ita/2009007
Classification : O3D55, 20M35, 68Q70, 91A65
Mots-clés : $\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},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {3},
     year = {2009},
     doi = {10.1051/ita/2009007},
     zbl = {1175.03022},
     mrnumber = {2541208},
     language = {en},
     url = {https://geodesic-test.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  - https://geodesic-test.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 https://geodesic-test.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. https://geodesic-test.mathdoc.fr/articles/10.1051/ita/2009007/

Cité par Sources :