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

Jérémie Cabessa; Jacques Duparc

Displaying similar documents to “A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I”

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

Similarity:

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

Taming the wild in impartial combinatorial games.

Plambeck, Thane E. (2005)

Integers

Similarity:

Model theory for infinite quantifier languages

Tapani Hyttinen (1990)

Fundamenta Mathematicae

Similarity:

Classical hierarchies from a modern standpoint. Part II. R-sets

John Burgess (1983)

Fundamenta Mathematicae

Similarity:

Some applications of game determinacy

G. Debs, J. Saint Raymond (1996)

Acta Universitatis Carolinae. Mathematica et Physica

Similarity:

On dot-depth two

F. Blanchet-Sadri (1990)

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

Similarity:

Simplification of partizan games in misère play.

Mesdal, G.A., Ottaway, P. (2007)

Integers

Similarity:

On game-theoretic methods in the theory of Souslin sets

Ashok Maitra (1971)

Fundamenta Mathematicae

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

Fixpoints, games and the difference hierarchy

Julian C. Bradfield (2003)

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

Similarity:

Drawing on an analogy with temporal fixpoint logic, we relate the arithmetic fixpoint definable sets to the winning positions of certain games, namely games whose winning conditions lie in the difference hierarchy over $Σ_{2}^{0}$ . This both provides a simple characterization of the fixpoint hierarchy, and refines existing results on the power of the game quantifier in descriptive set theory. We raise the problem of transfinite fixpoint hierarchies.