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

Details

Serval ID
serval:BIB_137D145FE79A
Type
Article: article from journal or magazin.
Collection
Publications
Institution
Title
A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy: Part II
Journal
RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Author(s)
Cabessa J., Duparc J.
ISSN
0988-3754
Publication state
Published
Issued date
07/2009
Peer-reviewed
Oui
Volume
43
Number
3
Pages
463-515
Language
english
Abstract
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.
Keywords
ω-automata, ω-rational languages, ω-semigroups, infinite games, hierarchical games, Wadge game, Wadge hierarchy, Wagner hierarchy
Web of science
Create date
07/01/2010 16:34
Last modification date
27/11/2019 6:19
Usage data