Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

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

Jérémie Cabessa;  Jacques Duparc — 2009

RAIRO - Theoretical Informatics and Applications

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...

A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I

Jérémie Cabessa;  Jacques Duparc — 2009

RAIRO - Theoretical Informatics and Applications

The algebraic study of formal languages shows that -rational sets correspond precisely to the -languages 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 show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation on finite...

Page 1

Download Results (CSV)