Abstract
We propose a proof of the downward L\"owenheim-Skolem that relies on strategies deriving from evaluation games instead of the Skolem normal forms. This proof is simpler, and easily understood by the students, although it requires, when defining the semantics of first-order logic to introduce first a few notions inherited from game theory such as the one of an evaluation game.

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.

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

Abstract
In 1997, following the works of Klaus W. Wagner on omega-regular sets, Olivier Carton and Dominique Perrin introduced the notions of Chains and Superchains for omega-semigroups. There is a clear correspondance between the algebraic representation of each of these operations and the automata-theoretical one. Unfortunately, chains and superchains do not suffice to describe the whole Wagner hierarchy. We introduce a third notion which completes the task undertaken in Carton O., Perrin D.: "Chains and superchains for omega-rational sets, automata and semigroups" (Int. J. Alg. Comput., vol. 7, no. 7, pp. 673-695, 1997).

Abstract
Twenty years ago, Klaus. W. Wagner came up with a hierarchy of omega-regular sets that actually bears his name. It turned out to be exactly the Wadge hierarchy of the sets of omega-words recognized by deterministic finite automata. We describe the Wadge hierarchy of context-free omega-languages, which stands as an extension of Wagner's work from automata to pushdown automata.

Abstract
Given well ordered countable sets of the form $\lamphi$, we consider Borel mappings from $\lamphiom$ with countable image inside the ordinals. The ordinals and $\lamphiom$ are respectively equipped with the discrete topology and the product of the discrete topology on $\lamphi$. The Steel well-ordering on such mappings is defined by $\phi\minf\psi$ iff there exists a continuous function $f$ such that $\phi(x)\leq\psi\circ f(x)$ holds for any $x\in\lamphiom$. It induces a hierarchy of mappings which we give a complete description of. We provide, for each ordinal $\alpha$, a mapping $\T\alpha$ whose rank is precisely $\alpha$ in this hierarchy and we also compute the height of the hierarchy restricted to mappings with image bounded by $\alpha$. These mappings being viewed as partitions of the reals, there is, in most cases, a unique distinguished element of the partition. We analyze the relation between its topological complexity and the rank of the mapping in this hierarchy.

Abstract
I) Wadge defined a natural refinement of the Borel hierarchy, now called the Wadge hierarchy WH. The fundamental properties of WH follow from results of Kuratowski, Martin, Wadge and Louveau. We give a transparent restatement and proof of Wadge's main theorem. Our method is new for it yields a wide and unexpected extension: from Borel sets of reals to a class of natural but non Borel sets of infinite sequences. Wadge's theorem is quite uneffective and our generalization clearly worse in this respect. Yet paradoxically our method is appropriate to effectivize this whole theory in the context discussed below. II) Wagner defined on Büchi automata (accepting words of length ω) a hierarchy and proved for it an effective analog of Wadge's results. We extend Wagner's results to more general kinds of Automata: Counters, Push Down Automata and Büchi Automata reading transfinite words. The notions and methods developed in (I) are quite useful for this extension. And we start to use them in order to look for extensions of the fundamental effective determinacy results of Büchi-Landweber, Rabin; and of Courcelle-Walukiewicz.

Abstract
For each Borel set of reals of infinite rank A we obtain a ``normal form'' of A by finding a Borel set Ω such that A and Ω continuously reduce to each other. We do so by defining simple Borel operations which are homomorphic to the ω1 first Veblen ordinal operations of base ω1 required to compute the Wadge degree of a Borel set.

Abstract
For each Borel set of reals A, of finite rank, we obtain a "normal form" of A, by finding a Borel set Ω of maximum simplicity, such that A and Ω continuously reduce to each other. In more technical terms : we define simple Borel operations which are homomorphic to ordinal sum, to multiplication by a countable ordinal, and to ordinal exponentiation of base ω1, under the map which sends every Borel set A of finite rank to its Wadge degree.

Abstract
We describe the Wadge hierarchy of the omega-languages recognized by deterministic Petri nets. This is an extension of the celebrated Wagner hierarchy which turned out to be the Wadge hierarchy of the omega-regular languages. Petri nets are more powerful devices than finite automata. They may be defined as partially blind multi-counter automata. We show that the whole hierarchy has height omega(omega 2), and give a description of the restrictions of this hierarchy to partially blind multi-counter automata of some fixed positive number of counters.

Abstract
The article surveys recent results in the study of topological complexity of recognizable tree languages. Emphasis is put on the relation between topological hierarchies, like the Borel hierarchy or the Wadge hierarchy, and the hierarchies resulting from the structure of automata, as the Rabin-Mostowski index hierarchy. The topological complexity of recognizable tree languages is seen as an evidenceof their structural complexity, which also induces the computational complexity of the verification problems related to automata, as the non-emptiness problem. Indeed, the topological aspect can be seen as a rudiment of the infinite computation complexity theory.

Abstract
We describe the Wadge hierarchy of the ω-languages recognized by deterministic Petri nets. This is an extension of the celebrated Wagner hierarchy which turned out to be the Wadge hierarchy of the ω-regular languages. Petri nets are an improvement of automata. They may be defined as partially blind multi-counter automata. We show that the whole hierarchy has height ωω2, and give a description of the restrictions of this hierarchy to every fixed number of partially blind counters.

Abstract
Alternating automata on infinite trees induce operations on languages which do not preserve natural equivalence relations, like having the same Mostowski--Rabin index, the same Borel rank, or being continuously reducible to each other (Wadge equivalence). In order to prevent this, alternation needs to be restricted to the choice of direction in the tree. For weak alternating automata with restricted alternation a small set of computable operations generates all definable operations, which implies that the Wadge degree of a given automaton is computable. The weak index and the Borel rank coincide, and are computable. An equivalent automaton of minimal index can be computed in polynomial time (if the productive states of the automaton are given).

Abstract
Game theory describes and analyzes strategic interaction. It is usually distinguished between static games, which are strategic situations in which the players choose only once as well as simultaneously, and dynamic games, which are strategic situations involving sequential choices. In addition, dynamic games can be further classified according to perfect and imperfect information. Indeed, a dynamic game is said to exhibit perfect information, whenever at any point of the game every player has full informational access to all choices that have been conducted so far. However, in the case of imperfect information some players are not fully informed about some choices. Game-theoretic analysis proceeds in two steps. Firstly, games are modelled by so-called form structures which extract and formalize the significant parts of the underlying strategic interaction. The basic and most commonly used models of games are the normal form, which rather sparsely describes a game merely in terms of the players' strategy sets and utilities, and the extensive form, which models a game in a more detailed way as a tree. In fact, it is standard to formalize static games with the normal form and dynamic games with the extensive form. Secondly, solution concepts are developed to solve models of games in the sense of identifying the choices that should be taken by rational players. Indeed, the ultimate objective of the classical approach to game theory, which is of normative character, is the development of a solution concept that is capable of identifying a unique choice for every player in an arbitrary game. However, given the large variety of games, it is not at all certain whether it is possible to device a solution concept with such universal capability. Alternatively, interactive epistemology provides an epistemic approach to game theory of descriptive character. This rather recent discipline analyzes the relation between knowledge, belief and choice of game-playing agents in an epistemic framework. The description of the players' choices in a given game relative to various epistemic assumptions constitutes the fundamental problem addressed by an epistemic approach to game theory. In a general sense, the objective of interactive epistemology consists in characterizing existing game-theoretic solution concepts in terms of epistemic assumptions as well as in proposing novel solution concepts by studying the game-theoretic implications of refined or new epistemic hypotheses. Intuitively, an epistemic model of a game can be interpreted as representing the reasoning of the players. Indeed, before making a decision in a game, the players reason about the game and their respective opponents, given their knowledge and beliefs. Precisely these epistemic mental states on which players base their decisions are explicitly expressible in an epistemic framework. In this PhD thesis, we consider an epistemic approach to game theory from a foundational point of view. In Chapter 1, basic game-theoretic notions as well as Aumann's epistemic framework for games are expounded and illustrated. Also, Aumann's sufficient conditions for backward induction are presented and his conceptual views discussed. In Chapter 2, Aumann's interactive epistemology is conceptually analyzed. In Chapter 3, which is based on joint work with Conrad Heilmann, a three-stage account for dynamic games is introduced and a type-based epistemic model is extended with a notion of agent connectedness. Then, sufficient conditions for backward induction are derived. In Chapter 4, which is based on joint work with Jérémie Cabessa, a topological approach to interactive epistemology is initiated. In particular, the epistemic-topological operator limit knowledge is defined and some implications for games considered. In Chapter 5, which is based on joint work with Jérémie Cabessa and Andrés Perea, Aumann's impossibility theorem on agreeing to disagree is revisited and weakened in the sense that possible contexts are provided in which agents can indeed agree to disagree.

Abstract
Résumé¦Le μ-calcul est une extension de la logique modale par des opérateurs de point fixe. Dans ce travail nous étudions la complexité de certains fragments de cette logique selon deux points de vue, différents mais étroitement liés: l'un syntaxique (ou combinatoire) et l'autre topologique. Du point de vue syn¬taxique, les propriétés définissables dans ce formalisme sont classifiées selon la complexité combinatoire des formules de cette logique, c'est-à-dire selon le nombre d'alternances des opérateurs de point fixe. Comparer deux ensembles de modèles revient ainsi à comparer la complexité syntaxique des formules as¬sociées. Du point de vue topologique, les propriétés définissables dans cette logique sont comparées à l'aide de réductions continues ou selon leurs positions dans la hiérarchie de Borel ou dans celle projective.¦Dans la première partie de ce travail nous adoptons le point de vue syntax¬ique afin d'étudier le comportement du μ-calcul sur des classes restreintes de modèles. En particulier nous montrons que:¦(1) sur la classe des modèles symétriques et transitifs le μ-calcul est aussi expressif que la logique modale;¦(2) sur la classe des modèles transitifs, toute propriété définissable par une formule du μ-calcul est définissable par une formule sans alternance de points fixes,¦(3) sur la classe des modèles réflexifs, il y a pour tout η une propriété qui ne peut être définie que par une formule du μ-calcul ayant au moins η alternances de points fixes,¦(4) sur la classe des modèles bien fondés et transitifs le μ-calcul est aussi expressif que la logique modale.¦Le fait que le μ-calcul soit aussi expressif que la logique modale sur la classe des modèles bien fondés et transitifs est bien connu. Ce résultat est en ef¬fet la conséquence d'un théorème de point fixe prouvé indépendamment par De Jongh et Sambin au milieu des années 70. La preuve que nous donnons de l'effondrement de l'expressivité du μ-calcul sur cette classe de modèles est néanmoins indépendante de ce résultat. Par la suite, nous étendons le langage du μ-calcul en permettant aux opérateurs de point fixe de lier des occurrences négatives de variables libres. En montrant alors que ce formalisme est aussi ex¬pressif que le fragment modal, nous sommes en mesure de fournir une nouvelle preuve du théorème d'unicité des point fixes de Bernardi, De Jongh et Sambin et une preuve constructive du théorème d'existence de De Jongh et Sambin.¦RÉSUMɦPour ce qui concerne les modèles transitifs, du point de vue topologique cette fois, nous prouvons que la logique modale correspond au fragment borélien du μ-calcul sur cette classe des systèmes de transition. Autrement dit, nous vérifions que toute propriété définissable des modèles transitifs qui, du point de vue topologique, est une propriété borélienne, est nécessairement une propriété modale, et inversement. Cette caractérisation du fragment modal découle du fait que nous sommes en mesure de montrer que, modulo EF-bisimulation, un ensemble d'arbres est définissable dans la logique temporelle Ε F si et seulement il est borélien. Puisqu'il est possible de montrer que ces deux propriétés coïncident avec une caractérisation effective de la définissabilité dans la logique Ε F dans le cas des arbres à branchement fini donnée par Bojanczyk et Idziaszek [24], nous obtenons comme corollaire leur décidabilité.¦Dans une deuxième partie, nous étudions la complexité topologique d'un sous-fragment du fragment sans alternance de points fixes du μ-calcul. Nous montrons qu'un ensemble d'arbres est définissable par une formule de ce frag¬ment ayant au moins η alternances si et seulement si cette propriété se trouve au moins au n-ième niveau de la hiérarchie de Borel. Autrement dit, nous vérifions que pour ce fragment du μ-calcul, les points de vue topologique et combina- toire coïncident. De plus, nous décrivons une procédure effective capable de calculer pour toute propriété définissable dans ce langage sa position dans la hiérarchie de Borel, et donc le nombre d'alternances de points fixes nécessaires à la définir. Nous nous intéressons ensuite à la classification des ensembles d'arbres par réduction continue, et donnons une description effective de l'ordre de Wadge de la classe des ensembles d'arbres définissables dans le formalisme considéré. En particulier, la hiérarchie que nous obtenons a une hauteur (ωω)ω. Nous complétons ces résultats en décrivant un algorithme permettant de calculer la position dans cette hiérarchie de toute propriété définissable.

Abstract
La hiérarchie de Wagner constitue à ce jour la plus fine classification des langages ω-réguliers. Par ailleurs, l'approche algébrique de la théorie de langages formels montre que ces ensembles ω-réguliers correspondent précisément aux langages reconnaissables par des ω-semigroupes finis pointés. Ce travail s'inscrit dans ce contexte en fournissant une description complète de la contrepartie algébrique de la hiérarchie de Wagner, et ce par le biais de la théorie descriptive des jeux de Wadge. Plus précisément, nous montrons d'abord que le degré de Wagner d'un langage ω-régulier est effectivement un invariant syntaxique. Nous définissons ensuite une relation de réduction entre ω-semigroupes pointés par le biais d'un jeu infini de type Wadge. La collection de ces structures algébriques ordonnée par cette relation apparaît alors comme étant isomorphe à la hiérarchie de Wagner, soit un quasi bon ordre décidable de largeur 2 et de hauteur ω. Nous exposons par la suite une procédure de décidabilité de cette hiérarchie algébrique : on décrit une représentation graphique des ω-semigroupes finis pointés, puis un algorithme sur ces structures graphiques qui calcule le degré de Wagner de n'importe quel élément. Ainsi le degré de Wagner de tout langage ω-régulier peut être calculé de manière effective directement sur son image syntaxique. Nous montrons ensuite comment construire directement et inductivement une structure de n''importe quel degré. Nous terminons par une description détaillée des invariants algébriques qui caractérisent tous les degrés de cette hiérarchie.¦Abstract¦The Wagner hierarchy is known so far to be the most refined topological classification of ω-rational languages. Also, the algebraic study of formal languages shows that these ω-rational sets correspond precisely to the languages recognizable by finite pointed ω-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 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 well-founded and decidable partial ordering of width 2 and height $\omega^\omega$. We also describe a decidability procedure of this hierarchy: we introduce a graph representation of finite pointed ω-semigroups allowing to compute their precise Wagner degrees. The Wagner degree of every ω-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 Wagner degree of this hierarchy.

Abstract
For each Borel set of reals A, of finite rank, we obtain a ``normal form'' of A, by finding a canonical Borel set Ω, such that A and Ω continuously reduce to each other. In more technical terms: we define simple Borel operations which are homomorphic to ordinal sum, to multiplication by a countable ordinal, and to ordinal exponentiation of base ω1 , under the map which sends every Borel set A of finite rank to its Wadge degree.

Abstract
We consider Borel sets of the form A ⊆ Λω (with usual topology) where cardinality of Λ is less than some uncountable regular cardinal Κ. We obtain a ``normal form'' of A, by finding a Borel set Ω(α) such that A and Ω(α) continuously reduce to each other. We do so by defining Borel operations which are homomorphic to the Κ first Veblen ordinal functions of base Κ required to compute the Wadge degree of the set A: the ordinal α.

Abstract
For each Borel set A of reals, or more generally of infinite strings from a countable alphabet, we obtain a ``normal form'' ofA, by finding a Borel setΩ of maximum simplicity, such that A and Ω continuously reduce to each other.Ω only depend on the equivalence class of A modulo inter-reducibility, moreover, the map: A→Ω is defined in a simple way (in ZF+DC). In case of Borel sets of finite rank, we prove the above result essentially by defining simple Borel operations which are homomorphic to ordinal sum, to multiplication by a countable ordinal, and to ordinal exponentiation of base ω1 (under the map which sends every Borel setA of finite rank to its Wadge degree). Extension to transfinite ranks is provided by iterating both ordinal exponentiation and its Borel counterpart. And finally, we show that all these results can be extended to all Borel subsets of Xω when the alphabet X is of any cardinal.

Abstract
In 1979, Klaus W. Wagner introduced a hierarchy on ω-regular sets that has length ωω . It is the one induced by the ordering on Deterministic Automata: A < B iff the set accepted by A is the inverse image of the set accepted by B by a continuous function. Lately, Jean-Eric Pin conjectured that there might be a coarser hierarchy with length ω and that it could be given by the same ordering on DA except that continuous is replaced by a slightly weaker notion 2-continuous. We provide a positive answer to this conjecture and give a description of this new hierarchy.

Abstract
We give for, each Louveau's class Γu, a Γu-complete set Au, that is [Aub] =Γu , in our terminology. This allows to compute the level of this Wadge class in the Wadge hierarchy.

Abstract
Issue: Let (P,<) be some BQO. Louveau and Saint-Raymond showed that the following structure (F, <_F) is also a BQO: F={φ: from ωω into P: φ is Borel with countable image} with the usual topology on ωω and the discrete topology on the BQO P; and φ <_F ψ iff there exists some continuous function h: from ωω to ωω such that for all x ∈ ωω φ(x) < ψ(h(x)). The following proposition answers the question of the relation between cardinalities of anti-chains of P and anti-chains of F: 1) Every anti-chain in P has cardinality 1 ⇒ every anti-chain in F has cardinality 1. 2) There exists an anti-chain in P of cardinality 2, but no element of P is incomparable with two different elements ⇒ every anti-chain in F has cardinality at most 2. 3) There exists an element in P which is incomparable with two different elements ⇒ there exists anti-chains of any cardinality in F.