----------

Jacques Duparc


Institut d'informatique et organisation
College Propedeutique 1,
CH - 1015 Lausanne

Tel: +41 (0)21 692 35 88
FAX: +41 (0)21 692 35 85

- jduparc@unil.ch

-


Interested in how I look ?

----------



Research Areas

  • Mathematical Logic

  • Descriptive Complexity

  • Finite Model Theory

  • Set Theory

  • Descriptive Set Theory

  • Determinacy Principles

  • Games Involving Topology or Set Theory

  • 2-Person Games

  • Logic in Computer Science

  • Hierarchies




    Publications

  • Journal Papers

  • Conference Papers

  • On the Desk

  • Ph. D. Thesis


    -Journal Papers -


    1. The Missing Link for ω-Rational Sets, Automata, and Semigroups

    2. Joint paper with
      Mariane Riss

      (pdf version) or (ps version)

      to appear in the International Journal of Algebra and Computation

      Abstract: In 1997, following the works of Klaus W. Wagner on ω-regular sets, Olivier Carton and Dominique Perrin introduced the notions of Chains and Superchains for ω-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 ω-rational sets, automata and semigroups" ( Int. J. Alg. Comput. , vol. 7, no. 7, pp. 673-695, 1997).


    3. A Coarsification of the Wagner Hierarchy

    4. (pdf version) or (ps version)

      submitted to Theoretical Computer Science

      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.


    5. The Steel Hierarchy of Ordinal Valued Borel Mappings

    6. Journal of Symbolic Logic 68 (2003), no. 1, 187--234.

      Abstract: Given well ordered countable sets of the form A, we consider Borel mappings from A with countable image inside the ordinals. The ordinals and A are respectively equipped with the discrete topology and the product of the discrete topology on A. The Steel well-ordering on such mappings is defined by φ ≤S ψ iff there exists a continuous function f such that φ(x) ≤ ψ(f(x)) holds for any x ∈ A. It induces a hierachy of mappings which we give a complete description of. We provide, for each ordinal α, a mapping Tα whose rank is precisely α in this hierarchy and we also compute the height of the hierarchy restricted to mappings with image bounded by α. 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.


    7. A Hierarchy of Deterministic Context-Free ω-languages
    8. Theoretical Computer Science, Volume 290 (2003), no. 3, 1253-1300.

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


    9. Wadge Hierarchy and Veblen Hierarchy. Part I: Borel Sets of Finite Rank

    10. Journal of Symbolic Logic 66 (2001), no. 1, 56--86.

      Abstract: We consider Borel sets of finite rank A ⊆ Λω 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. 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 Κ, under the map which sends every Borel set A of finite rank to its Wadge degree.


    11. Wadge Hierarchy and Veblen Hierarchy. Part II: Borel Sets of Infinite Rank

    12. (pdf version) or (ps version)

      submitted to the Journal of Symbolic Logic

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


    13. A Normal Form of Borel Sets of Finite Rank

    14. (pdf version) or (ps version)

      submitted to Notre-Dame Journal of Formal Logic
      radically different proofs and tools than the ones in the article submitted to JSL. These proofs are close to the ones in my Ph.D. Thesis, but extremely reduced.

      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.


    15. Computer Science and the Fine Structure of Borel Sets

    16. Joint paper with Olivier Finkel and Jean-Pierre Ressayre

      Theoretical Computer Science, Volume 257 (1-2), April 2001, p.85-105.

      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.


    17. Anti-Chains of Mappings from ωω on some BQO

    18. (pdf version) or (ps version)

      temporary version, to be submitted

      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.


    19. Wadge Degrees of Louveau's (Wadge) Classes

    20. (pdf version) or (ps version)

      related to the extended abstract below (temporary version)

      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.


    21. A Normal Form for Borel Sets

    22. (pdf version) or (ps version)

      extended abstract, not submitted


      Abstract: For each Borel setA 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 thatA andΩ continuously reduce to each other.Ω only depend on the equivalence class ofA 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.


    23. The Normal Form of Borel Sets. Part I: Borel Sets of Finite Rank

    24. C. R. Acad. Sci. Paris, t. 320, Série I, p. 651-656, 1995

      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.


    25. The Normal Form of Borel Sets. Part II: Borel Sets of Infinite Rank

    26. C. R. Acad. Sci. Paris, t. 328, Série I, p. 735-740, 1999

      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.



      -Conference Papers -


    27. Positive Games and Persistent Strategies


    28. (pdf version) or (ps version)
      12th Annual Conference of the European Association for Computer Science Logic, and 8th Kurt Gödel Colloquium CSL 2003,

      Abstract: At CSL 2002, Jerzy Marcinkowsi and Tomasz Truderung presented the notions of positive games and persistent strategies. A strategy is persistent if, given any finite or infinite run played on a game graph, each time the player visits some vertex already encountered, this player repeats the decision made when visiting this vertex for the first time. Such strategies require memory, but once a choice is made, it is made for ever. So, persistent strategies are a weakening of memoryless strategies. The same authors established a direct relation between positive games and the existence of persistent winning strategies. We give a description of such games by means of their topological complexity. In games played on finite graphs, positive games are unexpectedly simple. On the contrary, infinite game graphs, as well as infinite alphabets, yield positive sets involved in non determined games. Last, we discuss positive Muller winning conditions. Although they do not help to discriminate between memoryless and LAR winning strategies, they bear a strong topological characterization.


    29. Solving Pushdown Games with a Σ3 Winning Condition

    30. Joint paper with Thierry. Cachat and Wolfgang Thomas
      (pdf version) or (ps version)
      Proceedings of the 11th Annual Conference of the European Association for Computer Science Logic, CSL 2002,
      Lecture Notes in Computer Science 2471. Springer, 2471 (2002), 322--336

      Abstract: We study infinite two-player games over pushdown graphs with a winning condition that refers explicitly to the infinity of the game graph: A play is won by player 0 if some vertex is visited infinity often during the play. We show that the set of winning plays is a proper Σ3-set in the Borel hierarchy, thus transcending the boolean closure of Σ2-sets which arises with the standard automata theoretic winning conditions (such as the Muller-, Rabin-, or parity condition). We also show that this Σ3-game over pushdown graphs can be solved effectively (by a computation of the winning region of player 0 and his memoryless winning strategy). This seems to be a first example of an effectively solvable game beyond the second level of the Borel hierarchy.


    31. Infinite Games, Finite Machines

    32. Joint paper with Olivier Finkel and Jean-Pierre Ressayre
      Proceedings of the Joint Conference of the 5th Barcelona Logic Meeting
      and the 6th Kurt Gödel colloquium, Collegium Logicum, Annals of the Kurt-Gödel-Society Vol 4, 2000.



    33. The Normal Form of Borel Sets of Finite Rank


    34. Contibuted Papers of the Logic Colloquium'94



      -On the Desk -




    35. On the fine Structure of Omega Context Free Languages

    36. (in preparation)


      Abstract: In A Hierarchy of Deterministic Context-Free ω-languages ( Theoretical Computer Science, Volume 290 (2003), no. 3, 1253-1300. ) I described the Wadge hierarchy of deterministic context-free ω-languages, which stands as an extension of Wagner's work from Automata to deterministic Pushdown Automata. In particular, I showed it contains only boolean combinations of Σ02 sets and has length ω2). In "On the Wadge Hierarchy of Omega Context Free Languages", Finkel showed that this hierarchy was deeply extended when replacing determinism by non determinism. He proved that the length of the Wadge hierarchy of context-free ω-languages (sets of infinite words recognized by Non determisitic Pushdown Automata) was at least εω (the ωth fixed point of the operation α gives ω α), and that it contains Σ0α-complete sets for all α < ω+1. I extend these results by showing that this hierarchy contains Σ0α-complete sets for all α < ωω, and its length is at least Vω(0). Where Vβ is the Veblen ordinal function defined by induction on β: V0 is the exponentiation of base ω; Vβ enumerates the ordinals that are fixed points of all Vξ (any ξ < β).





      Ph. D. Thesis -



    37. Ph.D. in mathematics: logic and foundations of computer sciences


    38. (pdf version) or (ps version)
      University Paris 7. July the 13th, 1995 in Paris (in french).

      Abstract: In the combinatorial part of his Ph. D. thesis, Wadge focuses on the similarities between set theoretical operations on Borel sets and arithmetical operations on ordinals. Indeed, he defines operations that are analogous to ordianl sum, ordinal supremum (in case of countable ordinals). Then, inductively, by combining these two operations, he obtains a third one that is very close to countable multiplication. Finally, granted with operations "sharp" and "flat" (which only differ in the that one leads to a complete set for a "Sigma" class, while the other leads to a complete set for the dual class) Wadge defines an analog of the multiplication by ω1, by going the limit with the operation that simulates the ordinal sum. In fact, Wadge wished to carry further this analogy between arithmetical ordinal operations and others on the Borel subsets of the Baire space. In the conclusion of his Ph. D. thesis he writes:

      "Of course, a number of questions still remains to be resolved. It would be very nice to learn of some connection between properties of the ordinal of a degree, and properties of the corresponding initial class (a few such connections have been discovered). It would also be very interesting to know of some ``inductive'' definition of the degrees, which allows a given degree to be constructed from those below it. This might, for example, allow properties of subsets of ωω to be proved by induction on the degree of the set involved"
      W.W. Wadge Reducibility and Determinateness on the Baire Space Ph.D. Thesis, University of California, Berkeley, 1984. p. 323-.

      This work tries to bring a solution to this endeavor in case of Borel sets of finite rank, It does also, although this is only roughly sketched in the conclusion, generalize to transinite ranks. This undertaking consists in producing a new solution, that is canonical in the sense that it yields a description of Borel sets that is isomorphic to the canonical description of the ordinals that witness their topological complexity. In case of Borel sets of finite ranks, these ordinals are all below the first fixpoint of the operation x → ω1x, and their canonical description is nothing but their Cantor normal form of base ω1.

      ----------

      ----------


      Jacques Duparc's Home Page / LuFG Mathematische Grundlagen der Informatik / duparc@informatik.rwth-aachen.de