2001

• J. Duparc. Wadge hierarchy and Veblen hierarchy. Part I: Borel sets of finite rank. Journal of Symbolic Logic, vol. 66(1), pp. 56–86, 2001.                                 
  Abstract   BibTeX

  We consider Borel sets of finite rank $A\subseteq\Lambda^\omega$ where cardinality of $\Lambda$ is less than some uncountable regular cardinal $\kappa$. We obtain a ''normal form'' of $A$, by finding a Borel set $\Omega$, such that $A$ and $\Omega$ 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 $\kappa$, under the map which sends every Borel set $A$ of finite rank to its Wadge degree.

  @article{JDjsl1,
       author = {Jacques Duparc},
       journal = {Journal of Symbolic Logic},
       number = {1},
       pages = {56--86},
       title = {{Wadge hierarchy and Veblen hierarchy. Part I: Borel sets of finite rank}},
       volume = {66},
       year = {2001},
  }
  

• J. Duparc. Wadge hierarchy and Veblen hierarchy. Part II: Borel sets of infinite rank. Submitted to Journal of Symbolic Logic, 2001.                                 
  Abstract   BibTeX

  We consider Borel sets of the form $A\subseteq\Lambda^\omega$ (with usual topology) where cardinality of $\Lambda$ is less than some uncountable regular cardinal $\kappa$. We obtain a ''normal form'' of $A$, by finding a Borel set $\Omega(\alpha)$ such that $A$ and $\Omega(\alpha)$ continuously reduce to each other. We do so by defining Borel operations which are homomorphic to the $\kappa$ first Veblen ordinal functions of base $\kappa$ required to compute the Wadge degree of the set $A$: the ordinal $\alpha$.

  @article{JDjsl2,
       author = {Jacques Duparc},
       journal = {Submitted to Journal of Symbolic Logic},
       title = {{Wadge hierarchy and Veblen hierarchy. Part II: Borel sets of infinite rank}},
       url = {http://www.logic.rwth-aachen.de/pub/duparc/jsl2.ps},
       year = {2001},
  }
  

• J. Duparc. The Steel Hierarchy of Ordinal Valued Borel Mappings. Submitted to Journal of Symbolic Logic, 2001.                                 
  Abstract   BibTeX

  Given well ordered countable sets of the form $\Lambda\_\phi$, we consider Borel mappings from $\Lambda\_\phi^\omega$ with countable image inside the ordinals. The ordinals and $\Lambda\_\phi^\omega$ are respectively equipped with the discrete topology and the product of the discrete topology on $\Lambda\_\phi$. The Steel well-ordering on such mappings is defined by $\phi\leq\_S\psi$ iff there exists a continuous function $f$ such that $\phi(x)\leq\psi\circ\psi(x)$ holds for any $x\in\Lambda\_\phi^\omega$. It induces a hierachy of mappings which we give a complete description of. We provide, for each ordinal $\alpha$, a mapping $\hbox$\mathbb{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.

  @article{JDjsl3,
       author = {Jacques Duparc},
       journal = {Submitted to Journal of Symbolic Logic},
       title = {{The Steel Hierarchy of Ordinal Valued Borel Mappings}},
       url = {http://www.logic.rwth-aachen.de/pub/duparc/jsl3.ps},
       year = {2001},
  }
  

• J. Duparc. Wadge degrees of Louveau's (Wadge) classes. 2001.                                 
  Abstract   BibTeX

  For each Wadge class of Borel sets of reals, as described in Louveau's works, we produce a set that is complete for this class, and is canonical in the sense it is defined by operations on sets that are the set theoretic counterparts of natural operations on ordinals. This allow to (inductively) compute the Wadge degree of all Louveau's (Wadge) classes

  @unpublished{JDns1,
       author = {Jacques Duparc},
       note = {To be extended, then submitted},
       title = {{Wadge degrees of Louveau's (Wadge) classes}},
       url = {http://www.logic.rwth-aachen.de/pub/duparc/ns1.ps},
       year = {2001},
  }
  

• J. Duparc. A coarsification of the Wagner Hierarchy. Submitted to Theoretical Computer Science, 2001.                                 
  Abstract   BibTeX

  In 1979, Klaus W. Wagner introduced a hierarchy on $\omega$-regular sets that has length $\omega^\omega$. It is the one induced by the ordering on Deterministic Automata: $\cal A\leq \cal B$ iff the set accepted by $\cal A$ is the inverse image of the set accepted by $\cal B$ by a continuous function. Lately, Jean-Eric Pin conjectured that there might be a coarser hierarchy with length $\omega$ 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.

  @article{JDtcs3,
       author = {Jacques Duparc},
       journal = {Submitted to Theoretical Computer Science},
       title = {{A coarsification of the Wagner Hierarchy}},
       url = {http://www.logic.rwth-aachen.de/pub/duparc/tcs3.ps},
       year = {2001},
  }
  

• O. Finkel, J. Duparc, and J. Ressayre. Computer Science and the fine structure of Borel sets. Theoretical Computer Science, pp. 85–105, 2001.                                 
  Abstract   BibTeX

  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.

  Wagner defined on Büchi automata (accepting words of length $\omega$) 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 \refone\ 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.

  @article{JDtcs1,
       author = {Olivier Finkel and Jacques Duparc and J-P. Ressayre},
       journal = {Theoretical Computer Science},
       number = {257},
       pages = {85--105},
       title = {{Computer Science and the fine structure of Borel sets}},
       year = {2001},
  }
  

2000

• J. Duparc. Anti-chains of mappings from ω^ω on some BQO. 2000.                                 
  Abstract   BibTeX

  \bf Issue: Let $(P,\leq\_P)$ be some BQO. Louveau and Saint-Raymond showed that the following structure $(\cal F, \leq\_F)$ is also a BQO: $\cal F=\\phi: {\omega^{\omega}\longmapsto P: \phi\mbox is Borel with countable image\}$ with the usual topology on $\omega^\omega$ and the discrete topology on the BQO $P$; and $\phi\leq\_F \psi$ iff there exists some continuous function $h: \omega^\omega\lmt\omega^\omega$ such that for all $x\in\omega^\omega$ $\phi(x)\leq\_P\psi\circ h(x)$.

  The following proposition answers the question of the relation between cardinalities of anti-chains of $P$ and anti-chains of $\cal F$?

  @unpublished{JDns2,
       author = {Jacques Duparc},
       note = {Preprint, unpublished},
       title = {{Anti-chains of mappings from $\omega^\omega$ on some BQO}},
       url = {http://www.logic.rwth-aachen.de/pub/duparc/ns2.ps},
       year = {2000},
  }
  

1999

• J. Duparc. The normal form of Borel sets. Part II : Borel sets of infinite rank. Comptes Rendus de l'Académie des Sciences, pp. 735–740, 1999.                                 
  Abstract   BibTeX

  For each Borel set of reals of infinite rank $A$ we obtain a normal form of $A$ by finding a Borel set $\Omega$ such that $A$ and $\Omega$ continuously reduce to each other. We do so by defining simple Borel operations which are homomorphic to the $\omega\_1$ first Veblen ordinal operations of base $\omega\_1$ required to compute the Wadge degree of a Borel set.

  @article{JDcras2,
       author = {Jacques Duparc},
       journal = {Comptes Rendus de l'Acad{\'e}mie des Sciences},
       number = {328},
       pages = {735--740},
       series = {{I}},
       title = {{The normal form of Borel sets. Part II : Borel sets of infinite rank}},
       url = {http://www.logic.rwth-aachen.de/pub/duparc/cras2.ps},
       year = {1999},
  }
  

1995

• J. Duparc. The normal form of Borel sets. Part I: Borel sets of finite rank. Comptes Rendus de l'Académie des Sciences, pp. 651–656, 1995.                                 
  Abstract   BibTeX

  For each Borel set of reals A, of finite rank, we obtain a ''normal form'' of A, by finding a Borel set $\Omega$ of maximum simplicity, such that A and $\Omega$ 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 $\omega\_1$, under the map which sends every Borel set A of finite rank to its Wadge degree.

  @article{JDcras1,
       author = {Jacques Duparc},
       journal = {Comptes Rendus de l'Acad{\'e}mie des Sciences},
       number = {320},
       pages = {651--656},
       series = {{I}},
       title = {{The normal form of Borel sets. Part I: Borel sets of finite rank}},
       url = {http://www.logic.rwth-aachen.de/pub/duparc/cras1.ps},
       year = {1995},
  }
  

• J. Duparc. La forme normale des Boréliens de rangs finis. PhD thesis, Université Paris VII, 1995.             
  BibTeX

  @phdthesis{JDphd,
       author = {Jacques Duparc},
       month = {July},
       note = {In French},
       school = {Universit{\'e} Paris VII},
       title = {{La forme normale des Bor{\'e}liens de rangs finis}},
       year = {1995},
  }
  

1994

• J. Duparc. A normal form for Borel sets. 1994.                                 
  Abstract   BibTeX

  For each Borel set $A$ of reals, or more generally of infinite strings from a countable alphabet, we obtain a normal form of $A$, by finding a Borel set $\Omega$ of maximum simplicity, such that $A$ and $\Omega$ continuously reduce to each other. $\Omega$ only depend on the equivalence class of $A$ modulo inter-reducibility, moreover, the map: $A\longmapsto\Omega$ 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 $\omega\_1$ (under the map which sends every Borel set $A$ 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^\omega$ when the alphabet $X$ is of any cardinal.

  @unpublished{JDns3,
       author = {Jacques Duparc},
       note = {Extended abstract},
       title = {{A normal form for Borel sets}},
       url = {http://www.logic.rwth-aachen.de/pub/duparc/ns3.ps},
       year = {1994},
  }
  

1990

• J. Duparc. A hierarchy of Context-free ω-languages. Theoretical Computer Science, 1990.                                 
  Abstract   BibTeX

  Twenty years ago, Klaus. W. Wagner came up with a hierarchy of $\omega$-regular sets that actually bares 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.

  @article{JDtcs2,
       author = {Jacques Duparc},
       journal = {Theoretical Computer Science},
       note = {To appear},
       title = {{A hierarchy of Context-free $\omega$-languages}},
       url = {http://www.logic.rwth-aachen.de/pub/duparc/tcs2.ps},
       year = {1990},
  }