The Algebraic Counterpart of the Wagner Hierarchy
Details
Serval ID
serval:BIB_1E15A7A66040
Type
Article: article from journal or magazin.
Collection
Publications
Institution
Title
The Algebraic Counterpart of the Wagner Hierarchy
Journal
Lecture Notes in Computer Science
ISSN
0302-9743
Publication state
Published
Issued date
06/2008
Peer-reviewed
Oui
Volume
5028
Pages
100-109
Language
english
Abstract
The algebraic study of formal languages shows that ω-rational languages are exactly the sets recognizable by finite ω-semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the ω-rational language to the ω-semigroup context.
More precisely, we first define a reduction relation on finite pointed ω-semigroups by means of a Wadge-like infinite two-player game. The collection of these algebraic structures ordered by this reduction is then proven to be isomorphic to the Wagner hierarchy, namely a decidable and well-founded partial ordering of width 2 and height ωω.
More precisely, we first define a reduction relation on finite pointed ω-semigroups by means of a Wadge-like infinite two-player game. The collection of these algebraic structures ordered by this reduction is then proven to be isomorphic to the Wagner hierarchy, namely a decidable and well-founded partial ordering of width 2 and height ωω.
Keywords
ω-automata, ω-rational languages, ω-semigroups, infinite games, Wadge game, Wadge hierarchy, Wagner hierarchy
Web of science
Publisher's website
Create date
07/01/2010 16:43
Last modification date
27/11/2019 6:19