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 ?

**The Missing Link for ω-Rational Sets, Automata, and Semigroups****A Coarsification of the Wagner Hierarchy****The Steel Hierarchy of Ordinal Valued Borel Mappings****A Hierarchy of Deterministic Context-Free ω-languages****Wadge Hierarchy and Veblen Hierarchy. Part I: Borel Sets of Finite Rank****Wadge Hierarchy and Veblen Hierarchy. Part II: Borel Sets of Infinite Rank****A Normal Form of Borel Sets of Finite Rank****Computer Science and the Fine Structure of Borel Sets****Anti-Chains of Mappings from***ω*on some BQO^{ω}**Wadge Degrees of Louveau's (Wadge) Classes****A Normal Form for Borel Sets****The Normal Form of Borel Sets. Part I: Borel Sets of Finite Rank****The Normal Form of Borel Sets. Part II: Borel Sets of Infinite Rank****Positive Games and Persistent Strategies****Solving Pushdown Games with a Σ**_{3}Winning Condition**Infinite Games, Finite Machines****The Normal Form of Borel Sets of Finite Rank****On the fine Structure of Omega Context Free Languages****Ph.D. in mathematics: logic and foundations of computer sciences**

Joint paper with Mariane Riss

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

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

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

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

**Abstract:**
We consider Borel sets of finite rank *A ⊆ Λ ^{ω}
* where cardinality of

(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

(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

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.

(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

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

*
*

*
*

*
*

(pdf version) or (ps version)

*related to the extended abstract below (temporary version)*

**Abstract:**
We give for, each Louveau's class *Γ _{u}*,
a

(pdf version) or (ps version)

*extended abstract, not submitted*

**Abstract:**
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*Ω* 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 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:**
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

(pdf version) or (ps version)

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

Joint paper with Thierry. Cachat and Wolfgang Thomas

(pdf version) or (ps version)

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.

Joint paper with Olivier Finkel and Jean-Pierre Ressayre

and the 6th Kurt Gödel colloquium, Collegium Logicum, Annals of the Kurt-Gödel-Society Vol 4, 2000.

*(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 Σ^{0}_{2} 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 β: V_{0} is the exponentiation of base ω; V_{β} enumerates the ordinals that are fixed points of all V_{ξ} (any
ξ < β).
*

*
*

(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 → ω_{1}^{x}, and their canonical description is nothing but their
Cantor normal form of base ω_{1}.
*

*
*

*
*

*
*