A game theoretical approach to the algebraic counterpart of the Wagner hierarchy
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
The algebraic approach to formal languages introduces finite ω-semigroups and their subsets as the algebraic representatives of Buchi automata and ω-rational languages. The present dissertation fits within this framework, and provides a complete description of the algebraic counterpart of the Wagner hierarchy, by means of a game theoretical approach. For this purpose, we translate the Wadge theory from the ω-rational language to the ω-semigroup context. We define a Wadge like reduction between subsets of finite ω-semigroups, and prove that the resulting hierarchy is isomorphic to the Wagner hierarchy. This algebraic hierarchy thus consists of a partial ordering of height ωω and width 2, and it is moreover decidable. Therefrom, we describe an efficient decidability procedure of this hierarchy. We introduce a graph representation of subsets of finite ω-semigroups, and deduce an polynomial algorithm on graphs that computes the precise Wagner degree of every such subset. Consequently, the Wagner degree of every ω -rational language is proved to be computable directly on its syntactic ω-semigroup. Furthermore, we also provide both a direct and an inductive construction of a finite ω-semigroup of any given Wagner degree. We finally describe a topological invariant characterizing each Wagner class of this algebraic hierarchy.
Abstract FR:
L'idée de départ consiste à transposer la théorie des jeux de Wadge dans le cadre des ω- semigroupes. Ainsi, on définit d'abord une réduction de type Wadge sur les sous-ensembles des ω-semigroupes finis. La hiérarchie algébrique qui en résulte est alors isomorphe à la hiérarchie de Wagner, et correspond donc à un ordre partiel décidable de hauteur ω ω et de largeur 2. La description d'une procédure de décision efficace de cette hiérarchie s'ensuit alors. Pour ce faire, on introduit une représentation graphique des sous- ensembles des ω-semigroupes finis, ainsi qu'un algorithme graphique calculant précisément le degré de Wagner de tout tel sous-ensemble. Il en résulte que le degré de Wagner de tout langage ω -rationnel est calculable directement sur son ω-semigroupe syntaxique. Par la suite, on décrit également deux méthodes constructives, l'une directe et l'autre inductive, permettant de fournir un sous-ensemble d'un ω-semigroupe fini de degré de Wagner quelconque. On introduit finalement un invariant topologique caractérisant chaque classe de Wagner de cette hiérarchie algébrique.