Displaying similar documents to “A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II”

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

Similarity:

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

Two pile move-size dynamic Nim.

Holshouser, Arthur, Reiter, Harold (2005)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

Permissive strategies : from parity games to safety games

Julien Bernet, David Janin, Igor Walukiewicz (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

It is proposed to compare strategies in a parity game by comparing the sets of behaviours they allow. For such a game, there may be no winning strategy that encompasses all the behaviours of all winning strategies. It is shown, however, that there always exists a permissive strategy that encompasses all the behaviours of all memoryless strategies. An algorithm for finding such a permissive strategy is presented. Its complexity matches currently known upper bounds for the simpler problem...