Institut de Mathématiques de Jussieu - Paris Rive Gauche

CNRS et Université Paris Diderot

UFR de mathématiques case 7012

75205 Paris Cedex 13

FRANCE

**
**

**Langages de Büchi et Omega Langages Locaux****Stretchings****Locally Finite Languages****Topological Properties of Omega Context Free Languages****Computer Science and the Fine Structure of Borel Sets****Wadge Hierarchy of Omega Context Free Languages****Borel Hierarchy and Omega Context Free Languages****Ambiguity in Omega Context Free Languages****On Omega Context Free Languages which are Borel Sets of Infinite Rank****Topological Complexity of Locally Finite Omega Languages****Closure Properties of Locally Finite Omega Languages****On the Topological Complexity of Infinitary Rational Relations****On the Length of the Wadge Hierarchy of Omega Context Free Languages****Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations****On Infinite Real Trace Rational Languages of Maximum Topological Complexity****Topology and Ambiguity in Omega Context Free Languages****On Recognizable Languages of Infinite Pictures****An Example of Pi**_{3}^{0}-complete Infinitary Rational Relation**An omega-Power of a Finitary Language Which is a Borel Set of Infinite Rank****On Decidability Properties of Local Sentences****On Winning Conditions of High Borel Complexity in Pushdown Games****On Decision Problems for Timed Automata****On the Shuffle of Timed Regular Languages****Borel Ranks and Wadge Degrees of Omega Context Free Languages****Local Sentences and Mahlo Cardinals****Classical and Effective Descriptive Complexities of omega-Powers****On the Continuity Set of an omega Rational Function****Wadge Degrees of Infinitary Rational Relations****Highly Undecidable Problems about Recognizability by Tiling Systems****On Recognizable Tree Languages Beyond the Borel Hierarchy****Highly Undecidable Problems For Infinite Computations****On Decidability Properties of One-Dimensional Cellular Automata****Decision Problems For Turing Machines****On Some Sets of Dictionaries Whose omega-Powers Have a Given Complexity****The Complexity of Infinite Computations In Models of Set Theory****The Isomorphism Relation Between Tree-Automatic Structures****Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language****A Hierarchy of Tree-Automatic Structures****Some Problems in Automata Theory Which Depend on the Models of Set Theory****Automatic Ordinals****The Determinacy of Context-Free Games****On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets****Ambiguity of omega-Languages of Turing Machines****The Exact Complexity of the Infinite Post Correspondence Problem****An Upper Bound on the Complexity of Recognizable Tree Languages****Locally Finite omega-Languages and Effective Analytic Sets Have the Same Topological Complexity****Infinite Games Specified by 2-Tape Automata**

**Comptes
Rendus de l' Académie des Sciences, t. 309, Série I, p. 991-995,
1989.**

**Abstract.
There exist
similarities between the properties of Büchi languages, omega languages
recognized by finite automata or defined by monadic second-order sentences,
and those of local omega languages, defined by J.-P. Ressayre . We establish
some new ties between these two classes of omega languages, and show in
particular that Büchi languages are local omega languages canonically
connected with the regular expressions."
**

**
**

Joint paper with Jean-Pierre Ressayre

**
Journal of
Symbolic Logic, Volume 61, Number 2, June 1996, p. 563-585.**

**
Abstract.** A structure is
locally finite if every finitely generated substructure is finite; local
sentences are universal sentences all models of which are locally finite. The
stretching theorem for local sentences expresses a remarkable reflection
phenomenon between the finite and the infinite models of local sentences. This
result in part requires strong axioms to be proved; it was studied by the
second named author [J.S.L. 53, No. 4, 1009-1026]. Here we correct and extend
this paper; in particular we show that the stretching theorem implies the
existence of inaccessible cardinals, and has precisely the consistency
strength of Mahlo cardinals of finite order. And we present a sequel due to
the first named author: (i) decidability of the spectrum Sp( phi ) of a local
sentence phi, below omega^{omega} ; where Sp( phi ) is the set of
ordinals alpha such that phi has a model of order type alpha; (ii) proof that
beth_{ omega} =sup { Sp( phi ) : phi local sentence with a bounded
spectrum}; (iii) existence of a local sentence phi such that Sp( phi )
contains all infinite ordinals except the inaccessible cardinals.

**
Theoretical Computer Science,
Volume 255 (1-2), March 2001, p. 223-261.**

**
(preprint, dvi file
or ps file )
**

**
Abstract.** We investigate
properties of locally finite languages introduced by J-P. Ressayre. These
languages are defined by locally finite sentences and generalize languages
recognized by automata or defined by monadic second order sentences. We give
many examples, showing that numerous context free languages are locally
finite. Then we study closure properties of the family LOC of locally finite
languages, and show that most undecidability results that hold for context
free languages may be extended to locally finite languages. In a second part,
we consider an extension of these languages to infinite and transfinite length
words. We prove that each alpha-language which is recognized by a Büchi
automaton ( where alpha is an infinite ordinal and alpha <
omega^{omega} ) is defined by a locally finite sentence. This result,
combined with a preceding one of 2), provides a generalization of Büchi's
result about decidability of monadic second order theory of the structure
(alpha , <).

**
**

**
Theoretical
Computer Science, Volume 262 (1-2), July 2001, p. 669-697.**

**
(preprint, dvi file
or ps file
)
**

**
Abstract.** This paper is a study
of topological properties of omega context free languages (omega-CFL). We
first extend some decidability results for the deterministic ones
(omega-DCFL), proving that one can decide whether an omega-DCFL is in a given
Borel class, or in the Wadge class of a given omega regular language. We prove
that omega-CFL exhaust the hierarchy of Borel sets of finite rank, and that
one cannot decide the borel class of an omega-CFL, giving an answer to a
question of Lescow and Thomas [Logical Specifications of Infinite
Computations, In:"A Decade of Concurrency", Springer LNCS 803 (1994),
583-621]. We give also a (partial) answer to a question of Simonnet about
omega powers of finitary languages. We show that Büchi-Landweber's Theorem
cannot be extended to even closed omega-CFL: in a Gale-Stewart game with a
(closed) omega-CFL winning set, one cannot decide which player has a winning
strategy. From the proof of topological properties we derive some
arithmetical properties of omega-CFL.

**
**

Joint paper with Jacques Duparc and Jean-Pierre Ressayre

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

**
(preprint, dvi file
or ps file
)
**

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

**
**

**
Theoretical
Computer Science, Volume 269 (1-2), October 2001, p.283-315.
**

**
(preprint, dvi file
or ps file )
**

**
Abstract. The main result of
this paper is that the length of the Wadge hierarchy of omega context free
languages is greater than the Cantor ordinal epsilon_{0}, and the same
result holds for the conciliating Wadge hierarchy, defined by J. Duparc, of
infinitary context free languages, studied by D. Beauquier. In the course of
our proof, we get results on the Wadge hierarchy of iterated counter omega
languages, which we define as an extension to omega languages of classical
(finitary) iterated counter languages.
**

**
**

**
Theoretical Computer Science,
Volume 290 (3), January 2003, p.1385-1405. **

**
(preprint, dvi file
or ps file )
**

**
Abstract. We give in this paper
additional answers to questions of Lescow and Thomas [Logical Specifications
of Infinite Computations, In:"A Decade of Concurrency", Springer LNCS 803
(1994), 583-621], proving topological properties of omega context free
languages (omega-CFL) which extend those of 4): there exist some omega-CFL
which are non Borel sets. And one cannot decide whether an omega-CFL is a
Borel set. We give also an answer to questions of Niwinski and Simonnet about
omega powers of finitary languages, giving an example of a finitary context
free language L such that L^{omega} is not a Borel set. Then we prove
some recursive analogues to preceding properties: in particular one cannot
decide whether an omega-CFL is an arithmetical set.
**

**
**

**
Theoretical Computer Science,
Volume 301 (1-3), May 2003, p. 217-270. **

**
(preprint, dvi file
or ps file )
**

**
Abstract. We extend the well
known notions of ambiguity and of degrees of ambiguity of finitary context
free languages to the case of omega context free languages (omega-CFL)
accepted by Büchi or Muller pushdown automata. We show that these notions may
be defined independantly of the Büchi or Muller acceptance condition which is
considered. We investigate first properties of the subclasses of omega context
free languages we get in that way, giving many examples and studying
topological properties of omega-CFL of a given degree of ambiguity.
**

**
**

**
Theoretical Computer
Science, Volume 299 (1-3), April 2003, p. 327-346. **

**
(preprint, dvi file
or ps file )
**

**
Abstract. This paper is a
continuation of the study of topological properties of omega context free
languages (omega-CFL). We proved before that the class of omega-CFL exhausts
the hierarchy of Borel sets of finite rank, and that there exist some
omega-CFL which are analytic but non Borel sets. We prove here that there
exist some omega context free languages which are Borel sets of infinite (but
not finite) rank, giving additional answer to questions of Lescow and Thomas
[Logical Specifications of Infinite Computations, In:"A Decade of
Concurrency", Springer LNCS 803 (1994), 583-621].
**

**
**

**
Archive for Mathematical Logic, Volume 47 (6), September 2008, p. 625-651.**

**
(preprint, on HAL )
**

**
Abstract. Locally finite omega
languages were introduced by Ressayre in [Formal Languages Defined by the
Underlying Structure of their Words, Journal of Symbolic Logic 53, No. 4,
1009-1026]. These languages are defined by locally finite sentences and extend
omega languages accepted by Büchi automata or defined by monadic second order
sentences. We investigate their topological complexity. All locally finite
omega languages are analytic sets, the class LOC_{omega} of locally
finite omega languages exhausts the finite ranks of the Borel hierarchy and
there exist some locally finite omega languages which are Borel sets of
infinite rank or even analytic but non Borel sets. This gives (partial)
answers to questions of Simonnet [Automates et Théorie Descriptive, Ph. D.
Thesis, Université Paris 7, March 1992] and of Duparc, Finkel and Ressayre
[Computer Science and the Fine Structure of Borel Sets, Theoretical Computer
Science, Volume 257 (1-2), 2001, p.85-105].
**

**
**

**
Theoretical Computer
Science, Volume 322 (1), August 2004, p. 69-84. **

(preprint, dvi file or ps file )

**Abstract.** Locally finite omega
languages were introduced by Ressayre in [Journal of Symbolic Logic 53, No. 4,
1009-1026]. They generalize omega languages accepted by finite automata or
defined by monadic second order sentences. We study here closure properties of
the family LOC_{omega} of locally finite omega languages. In
particular we show that the class LOC_{omega} is neither closed under
intersection nor under complementation, giving an answer to a question of
Ressayre.

**
RAIRO-Theoretical
Informatics and Applications, Volume 37 (2), April-June 2003, p. 105-113. **

(preprint, dvi file or ps file )

**Abstract.** We prove in this
paper that there exists some infinitary rational relations which are analytic
but non Borel sets, giving an answer to a question of Simonnet [Automates et
Théorie Descriptive, Ph. D. Thesis, Université Paris 7, March 1992].

**
Journal of Automata,
Languages and Combinatorics, Volume 10 (4), 2005, p. 439-464. **

(preprint, dvi file or ps file )

**
Abstract.** We prove in this
paper that the length of the Wadge hierarchy of omega context free languages
is greater than the Cantor ordinal epsilon_{omega}, which is the
omega^{th} fixed point of the ordinal exponentiation of base omega.
The same result holds for the conciliating Wadge hierarchy, defined by J.
Duparc, of infinitary context free languages, studied by D. Beauquier. We show
also that there exist some omega context free languages which are
Sigma^{0}_{omega}-complete Borel sets, improving previous
results on omega context free languages and the Borel hierarchy.

**RAIRO-Theoretical
Informatics and Applications, Volume 37 (2), April-June 2003, p. 115-126. **

** (preprint, dvi
file or ps
file )
**

**
Abstract. We prove that for
every countable ordinal alpha one cannot decide whether a given infinitary
rational relation is in the Borel class Sigma^{0}_{alpha} (
respectively Pi^{0}_{alpha}). Furthermore one cannot decide
whether a given infinitary rational relation is a Borel set or a
Sigma_{1}^{1}-complete set. We prove some recursive analogues
to these properties. In particular one cannot decide whether an infinitary
rational relation is an arithmetical set. We then deduce from these results
that one cannot decide whether the complement of an infinitary rational
relation is also an infinitary rational relation.
**

**
**

Joint paper with Jean-Pierre Ressayre and Pierre Simonnet

**Zapiski Nauchnyh Seminarov
POMI, Volume 316, December 2004, p. 205-223. **

**(preprint, dvi
file or ps
file ) **

**Abstract.** We consider the set
of infinite real traces, over a dependence alphabet (Gamma, D) with no
isolated letter, equipped with the topology induced by the prefix metric. We
then prove that all rational languages of infinite real traces are analytic
sets and that there exist some rational languages of infinite real traces
which are analytic but non Borel sets, and even
Sigma_{1}^{1}-complete, hence of maximum possible topological
complexity.

Joint paper with Pierre Simonnet

**Bulletin of the
Belgian Mathematical Society, Volume 10 (5), December 2003, p. 707-722. **

**
(preprint,
dvi
file or
ps
file )
**

**
Abstract. We study the links
between the topological complexity of an omega context free language and its
degree of ambiguity. In particular, using known facts from classical
descriptive set theory, we prove that non Borel omega context free languages
which are recognized by Büchi pushdown automata have a maximum degree of
ambiguity. This result implies that degrees of ambiguity are really not
preserved by the operation of taking the omega power of a finitary context
free language. We prove also that taking the adherence or the delta-limit of a
finitary language preserves neither unambiguity nor inherent ambiguity. On the
other side we show that methods used in the study of omega context free
languages can also be applied to study the notion of ambiguity in infinitary
rational relations accepted by Büchi 2-tape automata and we get first results
in that direction.
**

**
**

**International Journal of
Foundations of Computer Science****, Volume 15 (6), December 2004, p. 823-840. **

**
Abstract. Languages of infinite
pictures which are recognizable by finite tiling systems with various
acceptance conditions have been recently investigated by Altenbernd, Thomas
and Wöhrle in [Tiling Systems over Infinite Pictures and their Acceptance
Conditions, in the Proceedings of the 6th International Conference on
Developements in Language Theory, DLT 2002, LNCS Volume 2450, Springer, p.
297-306]. The authors asked for comparing the tiling system acceptance with an
acceptance of pictures row by row using an automaton model over ordinal words
of length omega^{2}. We give in this paper a solution to this problem,
showing that all languages of infinite pictures which are accepted row by row
by Büchi or Choueka automata reading words of length omega^{2} are
Büchi recognized by a finite tiling system, but the converse is not true. We
give also the answer to two other questions which were raised in that paper,
showing that it is undecidable whether a Büchi recognizable language of
infinite pictures is E-recognizable (respectively, A-recognizable).
**

**
Erratum.
An erratum is added at the end of the preprint :
The supremum of the set of Borel ranks of Büchi recognizable
languages of infinite pictures is not the first non recursive ordinal
but an ordinal gamma_{2}^{1} which is strictly
greater than the first non recursive ordinal.
This follows from a result proved by
A. S. Kechris, D. Marker and R. L. Sami, in
[ Pi_{1}^{1} Borel sets, Journal of Symbolic Logic, Volume 54 (3), p. 915-920, 1989 ].
**

**
**

**
Computer Science Journal of Moldova, Volume 15 (1), June 2007, p. 3-21.**

**
Abstract.
We give in this paper an example of infinitary rational relation, accepted
by a 2-tape Büchi automaton, which is Pi_{3}^{0}-complete in the Borel hierarchy.
Moreover the example of infinitary rational relation
given in this paper has a very simple structure and can be easily
described by its sections.
**

**
**

**
Fundamenta
Informaticae****, Volume 62 (3-4), August 2004, p. 333-342. **

**(preprint, dvi
file or ps
file )
**

**
Abstract. omega-powers of
finitary languages are omega languages in the form V^{omega}, where V
is a finitary language over a finite alphabet X. Since the set of infinite
words over X can be equipped with the usual Cantor topology, the question of
the topological complexity of omega-powers naturally arises and has been
raised by Niwinski, by Simonnet, and by Staiger. It has been recently proved
in [ 4 ]
that for each integer n > 0 , there exist some omega-powers of context free
languages which are Pi_{n}^{0}-complete Borel sets, and in [ 7 ] that
there exists a context free language L such that L^{omega} is analytic
but not Borel. But the question was still open whether there exists a finitary
language V such that V^{omega} is a Borel set of infinite rank. We
answer this question in this paper, giving an example of a finitary language
whose omega-power is Borel of infinite rank.
**

**
**

**Theoretical Computer
Science****, Volume 364 (2), November 2006, p. 196-211. **

**(preprint, ps
file or pdf
file ) **

**Abstract.**
Local (first order)
sentences, introduced by Ressayre, enjoy very nice decidability properties,
following from some stretching theorems stating some remarkable links between
the finite and the infinite model theory of these sentences. We prove here several
additional results on local sentences. The first one is a new decidability
result in the case of local sentences whose function symbols are at most
unary: one can decide, for every regular cardinal k whether a local sentence
phi has a model of order type k. Secondly we show that this result can not be
extended to the general case. Assuming the consistency of an inaccessible
cardinal we prove that the set of local sentences having a model of order type
omega_{2} is not determined by the axiomatic system ZFC + GCH, where
GCH is the generalized continuum hypothesis.

*
Fundamenta
Informaticae, Volume 66 (3), April 2005, p. 277-298. *

**
(preprint, ps
file or pdf
file )
**

**
Abstract. Some decidable
winning conditions of arbitrarily high finite Borel complexity for games on
finite graphs or on pushdown graphs have been recently presented by O. Serre
in [ Games with Winning Conditions of High Borel Complexity, in the
Proceedings of the International Conference ICALP 2004, LNCS, Volume 3142, p.
1150-1162 ]. We answer in this paper several questions which were raised by
Serre in the above cited paper. We first show that, for every positive integer
n, the class C_{n}(A), which arises in the definition of decidable
winning conditions, is included in the class of non-ambiguous context free
omega languages, and that it is neither closed under union nor under
intersection. We prove also that there exists pushdown games, equipped with
such decidable winning conditions, where the winning sets are not
deterministic context free languages, giving examples of winning sets which
are non-deterministic non-ambiguous context free languages, inherently
ambiguous context free languages, or even non context free languages.
**

**
**

**
(preprint, ps file
or pdf
file )
**

**
Abstract.
We solve some decision problems for timed automata which were recently
raised by S. Tripakis in [ Folk Theorems on the Determinization and
Minimization of Timed Automata, in the Proceedings of the International Workshop
FORMATS'2003, LNCS, Volume 2791, p. 182-188, 2004 ]
and by E. Asarin in [ Challenges in Timed Languages, From Applied Theory to
Basic Theory, Bulletin of the EATCS, Volume
83, p. 106-120, 2004 ]. In particular,
we show that one cannot decide whether a given timed automaton is determinizable
or whether the complement of a timed regular language is timed regular.
**

**
**

**
(preprint, ps
file or pdf
file )
**

**
Abstract.
We show
that the class of regular timed languages is not closed under shuffle. This gives an answer to a question
which was raised by E. Asarin in [Challenges in Timed Languages, From Applied Theory to
Basic Theory, Bulletin of the EATCS, Volume
83, p. 106-120, 2004].
**

**
**

**(preprint, on HAL )
**

**
Abstract.**
We show that, from a topological point of view, considering the Borel and the Wadge hierarchies,
1-counter Büchi automata have the same accepting power than
Turing machines equipped with a Büchi acceptance condition.
In particular, for every non null recursive ordinal alpha,
there exist some
Sigma^{0}_{alpha}-complete
and some Pi^{0}_{alpha}-complete
omega context free languages accepted by 1-counter Büchi automata, and the supremum of the set of Borel
ranks of context free omega languages is
the ordinal gamma_{2}^{1} which is strictly
greater than the first non recursive ordinal.
This very surprising result gives answers to
questions of H. Lescow and W. Thomas
[Logical Specifications of Infinite Computations, In:"A Decade of
Concurrency", Springer LNCS 803 (1994), 583-621].

Joint paper with Stevo Todorcevic

**Mathematical
Logic Quarterly****, Volume 53 (6), November 2007, p. 558-563. **

**
Abstract.**
Local sentences were introduced by Ressayre
who proved certain remarkable stretching
theorems establishing the equivalence between the existence of
finite models for these sentences and the existence of some infinite
well ordered models. Two of these stretching theorems were only
proved under certain large cardinal axioms but the
question of their exact (consistency) strength was left open in
[ 2 ],
Here, we solve this problem, using a combinatorial result
of J. H. Schmerl. In fact, we show that the
stretching principles are equivalent to the existence of
n-Mahlo cardinals for appropriate integers n. This is done
by proving first that for each integer n, there is a local
sentence phi_n which has well ordered models of order type
alpha, for every infinite ordinal alpha > omega which is not an
n-Mahlo cardinal.

Joint paper with Dominique Lecomte

**Annals of Pure and Applied
Logic****, Volume 160 (2), August 2009, p. 163-191. **

**
Abstract.**
We prove that, for each non null countable ordinal alpha, there exist some Sigma^{0}_{alpha}-complete omega-powers,
and some Pi^{0}_{alpha}-complete omega-powers, extending previous works on the topological complexity
of omega-powers.
We prove effective versions of these results. In particular, for each non null recursive ordinal alpha, there exists a recursive finitary language
A such that A^{omega} is Sigma^{0}_{alpha}-complete (respectively, Pi^{0}_{alpha}-complete).
To do this, we prove effective versions of a result by Kuratowski, describing a Borel set as the range of a closed subset of the Baire space
by a continuous bijection. This leads us to prove closure properties
for the classes Effective-Pi^{0}_{alpha} and Effective-Sigma^{0}_{alpha} of the
hyperarithmetical hierarchy in arbitrary recursively presented Polish spaces.
We apply our existence results to get better computations of the topological complexity of some sets of dictionaries considered by the second author
in [Omega-Powers and Descriptive Set Theory,
Journal of Symbolic Logic, Volume 70 (4), 2005, p. 1210-1232].

Joint paper with Olivier Carton and Pierre Simonnet

Special Issue: A nonstandard spirit among computer scientists: a tribute to Serge Grigorieff at the occasion of his 60th birthday.

**
RAIRO-Theoretical
Informatics and Applications, Volume 42 (1), January-March 2008, p. 183-196. **

**
Abstract.**
In this paper, we study the continuity of rational functions realized by
Büchi finite state transducers. It has been shown by Prieur that it
can be decided whether such a function is continuous. We prove here that
surprisingly, it cannot be decided whether such a function F has
at least one point of continuity and that its continuity set C(F)
cannot be computed.
In the case of a synchronous rational function, we show that its
continuity set is rational and that it can be computed. Furthermore we
prove that any rational Pi_{2}^{0}-subset of X^{omega} for some alphabet X
is the continuity set C(F) of an omega-rational synchronous
function F defined on X^{omega}.

Special Issue on Intensional Programming & Semantics in honour of Bill Wadge on the occasion of his 60th cycle.

**
Mathematics in Computer Science,
Volume 2 (1), November 2008, p. 85-102. **

**
Abstract.**
We show that, from the topological point of view, 2-tape Büchi automata have the same accepting power as
Turing machines equipped with a Büchi acceptance condition.
The Borel and the Wadge hierarchies of the class of infinitary rational relations accepted by 2-tape Büchi automata are
equal to the Borel and the Wadge hierarchies of
omega-languages accepted by real-time Büchi 1-counter automata or by Büchi Turing machines.
In particular, for every non null recursive ordinal alpha,
there exist some
Sigma^{0}_{alpha}-complete and some Pi^{0}_{alpha}-complete infinitary rational relations.
And the supremum of the set of Borel ranks of
infinitary rational relations is an ordinal gamma_{2}^{1} which is strictly
greater than the first non recursive ordinal.
This very surprising result gives answers to
questions of Simonnet [Automates et
Théorie Descriptive, Ph. D. Thesis, Université Paris 7, March 1992]
and of Lescow and Thomas [Logical Specifications of Infinite Computations, In:"A Decade of
Concurrency", Springer LNCS 803 (1994), 583-621].

Special Issue on Machines, Computations and Universality.

*
Fundamenta Informaticae,
Volume 91 (2), March 2009, p. 305-323. *

**
Abstract.**
Acceptance of
languages of infinite two-dimensional words (infinite pictures) by finite tiling systems,
with usual acceptance conditions, such as the
Büchi and Muller ones, has been firstly studied by Altenbernd, Thomas and
Wöhrle in
[Tiling Systems over Infinite Pictures and their Acceptance
Conditions, in the Proceedings of the 6th International Conference on
Developements in Language Theory, DLT 2002, LNCS Volume 2450, Springer, p.
297-306]. It was proved in [ 17 ]
that it is undecidable whether a Büchi-recognizable language of infinite pictures is E-recognizable
(respectively, A-recognizable).
We show here that these two decision problems are actually Pi^{1}_{2}-complete,
hence located at the second level of the analytical hierarchy, and ``highly undecidable".
We give the exact degree of numerous other undecidable problems for
Büchi-recognizable languages of infinite pictures. In particular,
the non-emptiness and the infiniteness problems are Sigma^{1}_{1}-complete,
and the universality
problem, the inclusion problem, the equivalence problem, the determinizability problem,
the complementability problem, are all Pi^{1}_{2}-complete.
It is also Pi^{1}_{2}-complete to determine whether a given Büchi
recognizable language of infinite pictures can be accepted row by row using
an automaton model over ordinal words of length
omega^{2}.

Joint paper with Pierre Simonnet

*
Fundamenta Informaticae,
Volume 95 (2-3), October 2009, p. 287-303. *

**
Abstract.**
We investigate the topological complexity of non Borel recognizable tree languages with regard to the difference hierarchy of analytic sets.
We show that, for each integer n>0, there is a D_{(omegan)}(Sigma_{1}^{1})-complete
tree language L_{n}
accepted by a non deterministic Muller tree automaton.
On the other hand, we prove that a tree language recognized by an unambiguous Büchi tree automaton must be Borel.
Then we consider the game tree languages W_{(l, k)}, for Mostowski-Rabin indices (l, k). We prove that
the D_{(omegan)}(Sigma_{1}^{1})-complete tree languages L_{n}
are Wadge reducible to the game tree language W_{(l, k)}
for $k--l >1$.
In particular these game tree languages are not in any class D_{(alpha)}(Sigma_{1}^{1})
for alpha < omega^{omega}.

*
RAIRO-Theoretical
Informatics and Applications, Volume 43 (2), April-June 2009, p. 339-364.
*

**
Abstract.**
We show that many classical decision problems
about 1-counter omega-languages, context free omega-languages, or infinitary rational relations, are
Pi^{1}_{2}-complete, hence located at the second level of the analytical hierarchy, and ``highly undecidable".
In particular, the universality
problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the
unambiguity problem are all Pi^{1}_{2}-complete for context-free omega-languages or for infinitary rational relations.
Topological and arithmetical properties of
1-counter omega-languages, context free omega-languages, or infinitary rational relations, are also highly undecidable.
These very surprising results provide the first examples of highly undecidable problems about the behaviour of very
simple finite machines like 1-counter automata or 2-tape
automata.

*
Journal of Cellular Automata, Volume 6 (2-3), 2011, p. 181-193.
*

**
Abstract.**
In a recent paper Sutner proved that the first-order theory of the phase-space
S_{A}=(Q^{Z}, Succ) of a one-dimensional
cellular automaton A whose configurations are elements of Q^{Z}
for a finite set of states Q, and where Succ is the ``next configuration relation", is decidable.
He asked whether this result could be extended to a more expressive logic.
We prove in this paper that this is actually the case. We first show that,
for each one-dimensional cellular automaton A, the phase-space S_{A}
is an omega-automatic structure. Then, applying recent results of Kuske and Lohrey
on omega-automatic structures, it follows that the first-order theory,
extended with some counting and cardinality quantifiers, of the structure S_{A}
is decidable. We give some examples of new decidable properties for one-dimensional
cellular automata. In the case of surjective cellular automata,
some more efficient algorithms can be deduced from results of Kuske and Lohrey on
structures of bounded degree.
On the other hand, we show that the case of cellular automata give new results on automatic graphs.

Joint paper with Dominique Lecomte

*
Information
Processing Letters, Volume 109 (23-24), November 2009, p. 1223-1226.
*

**
Abstract.**
We answer two questions posed by Castro and Cucker in [Nondeterministic omega-computations and the analytical
hierarchy, Z. Math. Logik Grundlag. Math., Volume 35, 1989, p. 333-342], giving
the exact complexities of two decision problems about cardinalities of omega-languages of Turing machines.
Firstly, it is D_{2}(Sigma_{1}^{1})-complete to determine whether the omega-language
of a given Turing machine is countably infinite, where D_{2}(Sigma_{1}^{1})
is the class of 2-differences of Sigma_{1}^{1}-sets.
Secondly, it is Sigma_{1}^{1}-complete to determine
whether the omega-language of a given Turing machine
is uncountable.

*
Mathematical Logic Quarterly, Volume 56 (5), October 2010, p. 452-460.
*

**
Abstract.**
A dictionary, or language, is a set of finite words V over some finite alphabet X.
The omega-power of V is the set of infinite words which are obtained by
infinite concatenations of words in V.
In this paper we establish new relations between the sets
W(Sigma_{k}^{0}) (respectively,W(Pi_{k}^{0}), W(Delta_{1}^{1})
of dictionaries V whose omega-powers are Sigma_{k}^{0}-sets
(respectively, Pi_{k}^{0}-sets, Borel sets).
As an application we improve the lower bound of the complexity of W(Delta_{1}^{1}) given by Lecomte
in [Omega-Powers and Descriptive Set Theory,
Journal of Symbolic Logic, Volume 70 (4), 2005, p. 1210-1232].

*
Logical Methods in Computer Science, Volume 5 (4:4), December 2009, p. 1-19.
*

**
Abstract.**
We prove the following surprising result: there exist a 1-counter Büchi automaton A and a 2-tape Büchi automaton B such that :
(1) There is a model V_{1} of ZFC in which the omega-language L(A) and the infinitary rational relation L(B)
are Pi_{2}^{0}-sets, and (2) There is a model V_{2} of ZFC in which the omega-language L(A) and the infinitary
rational relation L(B) are analytic but non Borel sets. This shows that the topological complexity of an
omega-language accepted by a 1-counter Büchi automaton or of an infinitary rational relation accepted by a 2-tape Büchi automaton
is not determined by the axiomatic system ZFC. We show that a similar result holds for the class of languages of infinite pictures which are
recognized by Büchi tiling systems. We infer from the proof of the above results an improvement of the lower bound of some decision problems
recently studied in previous papers [Fin09a, Fin09b].

Joint paper with Stevo Todorcevic

*
Central European Journal of Mathematics, Volume 8 (2), April 2010, p. 299-313.
*

**
Abstract.**
An omega-tree-automatic structure is a relational structure whose domain and relations are accepted by Muller or Rabin tree automata.
We investigate in this paper the isomorphism problem for omega-tree-automatic structures. We prove first that the isomorphism relation for
omega-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings,
non commutative rings, non commutative groups, nilpotent groups of class n > 1) is not determined by the axiomatic system ZFC.
Then we prove that
the isomorphism problem for omega-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings,
non commutative rings, non commutative groups, nilpotent groups of class n > 1)
is neither a Sigma_{2}^{1}-set nor a Pi_{2}^{1}-set.

Special Issue: Frontier Between Decidability and Undecidability and Related Problems.

*
International Journal of
Foundations of Computer Science, Volume 23 (7), November 2012, p. 1481-1498. *

**
Abstract.**
It was noticed by Harel in [Har86] that ``one can define Sigma_{1}^{1}-complete versions of the well-known Post Correspondence Problem".
We first give a complete proof of this result, showing that the infinite Post Correspondence Problem in a regular omega-language is
Sigma_{1}^{1}-complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result that it is Pi_{1}^{1}-complete
to determine whether two given infinitary rational relations are disjoint. Then we prove that there is an amazing gap between two decision problems about
omega-rational functions realized by finite state Büchi transducers. Indeed Prieur proved in [Pri01, Pri02] that it is decidable whether a given
omega-rational function is continuous, while we show here that it is Sigma_{1}^{1}-complete to determine whether a given omega-rational function has
at least one point of continuity. Next we prove that it is Pi_{1}^{1}-complete
to determine whether the continuity set of a given omega-rational function is omega-regular. This gives the exact complexity of two problems which
were shown to be undecidable in [CFS08].

Joint paper with Stevo Todorcevic

*
Journal of
Symbolic Logic, Volume 77 (1), March 2012, p. 350-368.
*

**
Abstract.**
We consider omega^{n}-automatic structures which are relational structures whose
domain and relations are accepted by automata reading ordinal words of length omega^{n} for some integer n>0.
We show that all these structures are omega-tree-automatic structures presentable by Muller or Rabin tree automata.
We prove that the isomorphism relation for
omega^{2}-automatic (resp. omega^{n}-automatic for n>2) boolean algebras (respectively, partial orders, rings, commutative rings,
non commutative rings, non commutative groups) is not determined by the axiomatic system ZFC.
We infer from the proof of the above result that
the isomorphism problem for omega^{n}-automatic boolean algebras, n>1, (respectively, rings, commutative rings,
non commutative rings, non commutative groups)
is neither a Sigma_{2}^{1}-set nor a Pi_{2}^{1}-set.
We obtain that there exist infinitely many omega^{n}-automatic, hence also omega-tree-automatic,
atomless boolean algebras B_{n}, n>0, which are pairwise isomorphic under
the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [FT10].

*
RAIRO-Theoretical
Informatics and Applications, Volume 45 (4), November 2011, p. 383 - 397.
*

**
Abstract.**
We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system
ZFC. We prove the following surprising result: there exists a 1-counter
Büchi automaton A
such that the cardinality of the complement L(A)^{c} of the
omega-language L(A) is not determined by ZFC:
(1).
There is a model V_{1} of ZFC in which L(A)^{c} is countable.
(2). There is a model V_{2} of ZFC in which L(A)^{c} has the cardinality of the continuum.
(3). There is a model V_{3} of ZFC in which L(A)^{c} has cardinal Aleph_{1} with
Aleph_{0} < Aleph_{1} < 2^{Aleph0}.
We prove a very similar result for the complement of an infinitary rational relation accepted by a
2-tape Büchi automaton B.
As a corollary, this proves that the Continuum Hypothesis may be not satisfied for complements of 1-counter
omega-languages and for complements of infinitary rational relations accepted by 2-tape Büchi automata.
We infer from the proof of the above results that basic decision problems about 1-counter
omega-languages or infinitary rational relations are actually located at the third level of the analytical hierarchy. In particular, the problem
to determine whether the complement of a 1-counter omega-language (respectively, infinitary rational relation) is countable is
in Sigma_{3}^{1} but neither in Sigma_{2}^{1} nor in Pi_{2}^{1}.

Joint paper with Stevo Todorcevic

Special Issue on New Worlds of Computation 2011.

*
International Journal of
Unconventional Computing, Volume 9 (1-2), 2013, p. 61-70.
*

**
Abstract.**
We prove that the injectively omega-tree-automatic ordinals are the ordinals smaller than $\omega^{\omega^\omega}$.
Then we show that the injectively omega^{n}-automatic ordinals, where n>0 is an integer, are the ordinals smaller
than $\omega^{\omega^n}$. This strengthens a recent result of Schlicht and Stephan who considered in [Schlicht-Stephan11]
the subclasses of finite word omega^{n}-automatic ordinals. As a by-product we obtain that the hierarchy of injectively
omega^{n}-automatic structures, n>0, which was considered in [Finkel-Todorcevic12], is strict.

*
Journal of
Symbolic Logic, Volume 78 (4), December 2013, p. 1115-1134.
*

**
Abstract.**
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by
real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal
assumption. We show also that the determinacy of Wadge games between two players in charge of
omega-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy.
Using some results of set theory we prove that one can effectively construct a
1-counter Büchi automaton A and a Büchi automaton B such that: (1) There exists a model of ZFC
in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B)); (2) There exists a model of ZFC
in which the Wadge game W(L(A), L(B)) is not determined.
Moreover these are the only two possibilities, i.e. there are no models of ZFC in which
Player 1 has a
winning strategy in the Wadge game W(L(A), L(B)).

Joint paper with Michal Skrzypczak

*
Information Processing Letters, Volume 114 (5), May 2014, p. 229-233.
*

**
Abstract.**
We show that there are Sigma_{3}^{0}-complete languages of infinite words accepted by non-deterministic Petri nets with Büchi acceptance condition,
or equivalently by Büchi blind counter automata.
This shows that omega-languages accepted by non-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.

*
Logical Methods in Computer Science, Volume 10 (3:12), August 2014, p. 1-18.
*

**
Abstract.**
An omega-language is a set of infinite words over a finite alphabet X. We consider the class of recursive omega-languages, i.e. the class of omega-languages
accepted by Turing machines with a Büchi acceptance condition, which is also the class Sigma_{1}^{1} of (effective) analytic subsets of X^{omega}
for some finite alphabet X.
We investigate here the notion of ambiguity for recursive omega-languages with regard to acceptance by Büchi Turing machines. We first present in detail essentials on the
literature on omega-languages accepted by Turing Machines. Then we give a complete and broad view on the notion of ambiguity and unambiguity
of Büchi Turing machines and of the omega-languages they accept. To obtain our new results, we make use of results and methods of effective descriptive set theory.

*
Information Processing Letters, Volume 115 (6-8), June–August 2015, p. 609-611.
*

**(preprint, on HAL
)
**

**
Abstract.**
In this short note, we give the exact complexity of the infinite Post Correspondence Problem,
showing that it is Pi_{1}^{0}-complete. Surprisingly, it turns out that the
infinite Post Correspondence Problem is not ``more complex" than the
Post Correspondence Problem, which is known to be Sigma_{1}^{0}-complete, but has the exact dual complexity.
This gives an answer
to a question of Simonnet.

Joint paper with Dominique Lecomte and Pierre Simonnet

*
RAIRO-Theoretical
Informatics and Applications, Volume 49 (2), April-June 2015, p. 121-137.
*

**
Abstract.**
The third author noticed in his 1992 PhD Thesis that every regular tree language of infinite trees is
in a class G( D_{n}(Sigma_{2}^{0}) ) for some natural number n>0, where G is the game quantifier.
We first give a detailed exposition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel
subsets of the Cantor space into the class Delta_{2}^{1}, and the notions of Wadge degree and Veblen function,
we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual Delta_{2}^{1}.

*
Mathematical Logic Quarterly,
Volume 62 (4-5), August 2016, p. 303-318.
*

**(preprint, on HAL
)
**

**
Abstract.**
Local sentences and the formal languages they define were introduced by Ressayre
in [Ress88].
We prove that locally finite omega-languages and effective analytic sets have the same topological complexity:
the Borel and Wadge hierarchies of the class of locally finite omega-languages are equal to the Borel and Wadge
hierarchies of the class of effective analytic sets. In particular, for each non-null recursive ordinal
alpha there
exist some Sigma_{alpha}^{0}-complete and some
Pi_{alpha}^{0}-complete locally finite omega-languages,
and the supremum
of the set of Borel ranks of locally finite omega-languages is the ordinal gamma_{2}^{1}
which is strictly greater than the first non-recursive ordinal.
This gives an answer to the question of the topological complexity of locally finite omega-languages, which was asked by
Simonnet [Sim92] and also by Duparc, Finkel, and Ressayre in [DFR01].
Moreover we show that the topological complexity of a locally finite omega-language defined by a local sentence phi
may depend on the models of the Zermelo-Fraenkel axiomatic system ZFC.
Using similar constructions as in the proof of the above results
we also show that the equivalence, the inclusion, and the universality problems for locally finite
omega-languages are Pi_{2}^{1}-complete, hence highly undecidable.

*
Annals of Pure and Applied Logic,
Volume 167 (12), December 2016, p. 1184-1212.
*

**
Abstract.**
We prove that the determinacy of Gale-Stewart games whose winning sets are infinitary rational relations accepted by 2-tape Büchi automata is equivalent to the determinacy of
(effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. Then we prove that winning strategies, when they exist, can be very complex, i.e.
highly non-effective, in these games. We prove the same results for Gale-Stewart games with winning sets accepted by real-time 1-counter Büchi automata, then extending previous
results obtained about these games. Then we consider the strenghs of determinacy for these games, and we prove that there is a transfinite sequence of 2-tape Büchi automata
(respectively, of real-time 1-counter Büchi automata) A_\alpha, indexed by recursive ordinals, such that the games G(L(A_\alpha)) have strictly increasing strenghs of determinacy. Moreover
there is a 2-tape Büchi automaton (respectively, a real-time 1-counter Büchi automaton) B such that the determinacy of G(L(B)) is equivalent to the (effective) analytic determinacy
and thus has the maximal strength of determinacy. We also show that the determinacy of Wadge games between two players in charge of infinitary rational relations accepted by 2-tape
Büchi automata is equivalent to the (effective) analytic determinacy, and thus not provable in ZFC.

**Topological Complexity of Context-Free omega-Languages: A Survey****The Wadge Hierarchy of Petri Nets omega-Languages**

**In:
Language, Culture, Computation: Studies in Honor of Yaacov Choueka. **

**Ed. by Nachum Dershowitz and Ephraim Nissan, Part I, Computing, Theory and Technology,
Lecture Notes in Computer Science, Volume 8001, Springer,
2014.
**

**
**

Joint paper with Jacques Duparc and Jean-Pierre Ressayre

**In: Logic, Computation, Hierarchies,
Festschrift Volume in Honor of Victor Selivanov at the occasion of his sixtieth birthday**.

Ed. by Vasco Brattka, Hannes Diener, and Dieter Spreen, Ontos Mathematical Logic, Volume 4, De Gruyter, 2014, p. 109–138,

**
**

**
(preprint, on HAL
)
**

**
**

**Infinite Games, Finite Machines****Propriétés Topologiques des Omega Langages Algébriques****On Locally Finite languages****An Effective Extension of the Wagner Hierarchy to Blind Counter Automata****On the Wadge Hierarchy of Omega Context Free Languages****Topological and Arithmetical Properties of Infinitary Rational Relations****Topology and Ambiguity in Context Free Omega Languages****On Infinitary Rational Relations and Borel Sets****On Infinite Real Trace Rational Languages of Maximum Topological Complexity****On Decidability Properties of Local Sentences****On the Points of Continuity of an Omega Rational Function****An omega-Power of a Context Free Language which is Borel above Delta**_{omega}^{0}**Borel Ranks and Wadge Degrees of Omega Context Free Languages****On the Accepting Power of 2-Tape Büchi Automata****Undecidable Problems About Timed Automata****There Exist some Omega-Powers of Any Borel Rank****Topological Complexity of omega-Powers : Extended Abstract****Decision Problems for Recognizable Languages of Infinite Pictures****Wadge Games Betweeen 1-Counter Automata and Models of Set Theory****The Determinacy of Context-Free Games**- Ambiguity of omega-Languages of Turing Machines
**The Wadge Hierarchy of Petri Nets omega-Languages**- Infinite games specified by 2-tape automata
- Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words
- Independence Results in Automata Theory

**
Joint paper with Jacques Duparc
and Jean-Pierre
Ressayre
**

*Abstract corresponding to the above journal paper [ 5 ],
in the Proceedings of the Joint Conference of the 5th Barcelona Logic
Meeting and the 6th Kurt Gödel colloquium, 16-19 June 1999, Collegium Logicum,
Annals of the Kurt-Gödel-Society, Vol
4, 2000.*

** **

*(Résumé correspondant aux articles [ 4 ] et [ 7 ]
ci-dessus) Actes des huitièmes Journées
Montoises d' Informatique Théorique à Marne-la-Vallée , 6-8 Mars 2000 , p.
53-55.*

** **

*Abstract, in Contributed Papers of Logic Colloquium 2000 , Paris, 23-31
July 2000, p. 149-150*

** **

*Extended abstract, in the Proceedings of Computer Science Logic , 15th
International Workshop, CSL 2001, 10th Annual Conference of the European
Association for Computer Science Logic Paris, September 10-13, 2001, Lecture
Notes in Computer Science, Volume 2142, (c) Springer, p. 369-383. *

** **

**(preprint, ps
file or pdf
file )
**

**Abstract.** The extension of the
Wagner hierarchy to blind counter automata accepting infinite words with a
Muller acceptance condition is effective. We determine precisely this
hierarchy.

** **

*Extended abstract, short version of the above journal paper [ 13 ],
in the Proceedings of International
Workshop on Logic and Complexity in Computer Science, held in honour to Anatol
Slissenko for his 60th birthday, September 3-5, 2001, Université Paris 12,
Créteil, France, p. 69-79. *

** **

**(preprint, ps
file or pdf
file )
**

**Abstract.** The main result of
this paper is that the length of the Wadge hierarchy of omega context free
languages is greater than the Cantor ordinal epsilon_{omega}, which is
the omega^{th} fixed point of the ordinal exponentiation of base omega
and the same result holds for the conciliating Wadge hierarchy, defined by J.
Duparc, of infinitary context free languages, studied by D. Beauquier.

** **

*Extended abstract, short version of the above journal papers [ 12 ] and
[ 14 ],
in the Proceedings of Denis Richard 60 th Birthday
Conference, May 16-17, 2002, Clermont Ferrand. *

** **

**(preprint, ps
file or pdf
file )
**

**Abstract.** We study the
topological complexity of infinitary rational relations, with regard to the
Borel and projective hierarchies. In particular we show that there exists some
infinitary rational relations which are analytic but non Borel sets hence also
non arithmetical sets, giving an answer to a question of Simonnet [Automates
et théorie descriptive, Ph. D. Thesis, Université Paris 7, March 1992]. We
then deduce the undecidability of numerous topological and arithmetical
properties of infinitary rational relations.

** **

**Joint paper with Pierre Simonnet
**

*Extended abstract, short version of the above journal paper [ 16 ],
in the Proceedings of the 9 th International Conference Journées Montoises on Theoretical Computer
Science, September 9-11, 2002 Montpellier, France. *

**Abstract.** We study the links
between the topological complexity of an omega context free language and its
degree of ambiguity. In particular we show that analytic but non Borel omega
context free languages have a maximum degree of ambiguity.

** **

*Extended abstract, in the Proceedings of the Fourth
International Conference on Discrete Mathematics and Theoretical Computer
Science DMTCS'03, 7 - 12 July 2003, Dijon, France, Lecture
Notes in Computer Science, Volume 2731, (c) Springer, 2003, p. 155-167.
*

** **

**(preprint, ps
file or pdf
file )
**

**Abstract.** We prove in this
paper that there exists some infinitary rational relations which are
Sigma_{3}^{0}-complete Borel sets and some others which are
Pi_{3}^{0}-complete. This implies that there exists some
infinitary rational relations which are Delta_{4}^{0}-sets but
not (Sigma_{3}^{0}U Pi_{3}^{0})-sets. These
results give additional answers to questions of Simonnet [Automates et Théorie
Descriptive, Ph. D. Thesis, Université Paris 7, March 1992] and of Lescow and
Thomas [Logical Specifications of Infinite Computations, In:"A Decade of
Concurrency", Springer LNCS 803 (1994), 583-621].

** **

**Joint paper with Jean-Pierre Ressayre and Pierre
Simonnet
**

** **

*Abstract, in
Contributed Papers of 22nd
Journées sur les Arithmétiques Faibles, June 11-14, 2003, Napoli, Italy.
*

** **

*in the Proceedings of the 11th Workshop on Logic,
Language, Information and Computation WoLLIC 2004, July 19th to 22nd,
2004, Paris-Fontainebleau, France, Electronic
Notes in Theoretical Computer Science, Volume 123, (c) Elsevier, March
2005, p. 75-92. *

** **

**(preprint, ps
file or pdf
file )
**

**Abstract.** Local (first order)
sentences, introduced by Ressayre, enjoy very nice decidability properties,
following from some stretching theorems stating some remarkable links between
the finite and the infinite model theory of these sentences. We prove here two
additional results on local sentences. The first one is a new decidability
result in the case of local sentences whose function symbols are at most
unary: one can decide, for every regular cardinal k whether a local sentence
phi has a model of order type k. Secondly we show that this result can not be
extended to the general case. Assuming the consistency of an inaccessible
cardinal we prove that the set of local sentences having a model of order type
omega_{2} is not determined by the axiomatic system ZFC + GCH, where
GCH is the generalized continuum hypothesis.

** **

**
Joint paper with Olivier Carton and Pierre Simonnet
**

*Abstract, in the Proceedings of the 10 th International Conference Journées Montoises on Theoretical Computer
Science, September 8-11, 2004, Liège, Belgique. *

**Abstract.** An omega rational
function is a function whose graph is recognized by a Büchi finite state
transducer, or accepted by a 2-tape Büchi automaton with two reading heads,
i.e. is an infinitary rational relation. We study the set C(F) of points of
continuity of an omega rational function F which is always a Borel
Pi_{2}^{0}-set. In the case of a function F accepted by a
synchronous 2-tape Büchi automaton we show that the set C(F) is an omega
regular set which can be computed. Conversely every Pi_{2}^{0}
omega regular set is the set of points of continuity C(F) of some function F
accepted by a synchronous 2-tape Büchi automaton. This result cannot be
extended to the case of asynchronous omega rational functions: one cannot
decide whether the set C(F) of an omega rational function F is empty,
rational, or context free.

**
**

**Joint paper with Jacques Duparc
**

*in the Proceedings
of the International Conference Foundations of the Formal
Sciences V : Infinite Games, November 26th to 29th, 2004, Bonn, Germany,
Stefan Bold, Benedikt Löwe, Thoralf Räsch, Johan van Benthem (eds.),
College Publications at King's College, Studies in Logic, Volume 11, London, 2007, p. 109-122.
*

**
(preprint, on HAL
)
**

**
Abstract. We show, using a
backspace operation that arises very naturally when studying the Wadge
hierarchy of Borel sets, that there is a context free language whose omega
power is both Borel and strictly above Delta_{omega}^{0} in
the Borel hierarchy.
**

**
**

*
Extended Abstract, in the Proceedings of New
Computational Paradigms: First Conference on Computability in
Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005.
Lecture Notes in
Computer Science, Volume 3526, (c) Springer, 2005, p. 129-138. *

**
Abstract.
We show that, for each recursive non null
ordinal alpha, there exist some Sigma^{0}_{alpha}-complete
and some Pi^{0}_{alpha}-complete omega languages
accepted by Büchi 1-counter automata. **

**Erratum.**
An error appeared in this paper and is corrected in the journal paper
[ 24 ]: the supremum of the set of Borel
ranks of context free omega languages is not the first non recursive ordinal but
an ordinal gamma_{2}^{1} which is strictly
greater than the first non recursive ordinal. This follows from a result proved by
A. S. Kechris, D. Marker and R. L. Sami, in [ Pi_{1}^{1} Borel sets, Journal of Symbolic Logic, Volume 54 (3), p. 915-920, 1989 ].

*
Extended Abstract, in the Proceedings of
23rd International Symposium on Theoretical Aspects of Computer Science, STACS 2006, Marseille, France,
February 23-25, 2006,
Lecture Notes in
Computer Science, Volume 3884, (c) Springer, 2006, p. 301-312 .*

**(preprint, on HAL
)
**

**
Abstract.****
We show that, from a topological point of view, 2-tape Büchi automata have the same accepting power than
Turing machines equipped with a Büchi acceptance condition.
In particular, we show that for every non null recursive ordinal alpha,
there exist some
Sigma ^{0}_{alpha}-complete
and some Pi^{0}_{alpha}-complete
infinitary rational relations accepted by 2-tape Büchi automata.
This very surprising result gives answers to
questions of W. Thomas [Automata and Quantifier Hierarchies, in: Formal Properties
of Finite automata and Applications, Ramatuelle, 1988, LNCS
386, Springer, 1989, p.104-119 ] ,
of P. Simonnet [Automates et Théorie Descriptive, Ph. D.
Thesis, Université Paris 7, March 1992], and of H. Lescow and W. Thomas
[Logical Specifications of Infinite Computations, In:"A Decade of
Concurrency", Springer LNCS 803 (1994), 583-621].
**

**
**

* in the Proceedings of the
4th International Conference on Formal Modelling and Analysis of Timed Systems, FORMATS'06, Paris, France, September 25-27, 2006,
Lecture Notes in
Computer Science, Volume 4202, (c) Springer, 2006, p. 187-199.*

**(preprint, on HAL
)
**

**
Abstract. **
We solve some decision problems for timed automata which were recently
raised by S. Tripakis in [ Folk Theorems on the Determinization and
Minimization of Timed Automata, in the Proceedings of the International Workshop
FORMATS'2003, LNCS, Volume 2791, p. 182-188, 2004 ]
and by E. Asarin in [ Challenges in Timed Languages, From Applied Theory to
Basic Theory, Bulletin of the EATCS, Volume
83, p. 106-120, 2004 ]. In particular,
we show that one cannot decide whether a given timed automaton is determinizable
or whether the complement of a timed regular language is timed regular.
We show that the problem of the minimization of the number of clocks of a timed automaton
is undecidable.
It is also undecidable whether the shuffle of two timed regular languages is timed regular.
We show that in the case of timed Büchi automata accepting infinite timed words some of these
problems are Pi

Joint paper with Dominique Lecomte

* in the Proceedings of the
16th EACSL Annual Conference on Computer Science and Logic, CSL 2007, Lausanne, Switzerland, September 11-15, 2007,
Lecture Notes in
Computer Science, Volume 4646, (c) Springer, 2007, p. 115-129.*

**
Abstract. Omega-powers of
finitary languages are omega languages in the form V^{omega}, where V
is a finitary language over a finite alphabet X. They appear very naturally in the characterizaton of regular or context-free omega-languages.
Since the set of infinite words over a finite alphabet X can be equipped
with the usual Cantor topology, the question of the topological complexity of omega-powers of
finitary languages naturally arises and has been posed by
Niwinski (1990), Simonnet (1992) and Staiger (1997). It has been recently proved
in [ 4 ]
that for each integer n > 0 , there exist some omega-powers of context free
languages which are Pi_{n}^{0}-complete Borel sets, and in [ 7 ] that
there exists a context free language L such that L^{omega} is analytic
but not Borel. It has been also proved in [ 19 ]
that there exists a finitary language V
such that V^{omega} is a Borel set of infinite rank, but it was still unknown which could be the possible infinite Borel ranks of omega-powers.
We fill this gap here, proving the following very surprising result which shows that omega-powers exhibit a great topological complexity:
for each non-null countable ordinal alpha, there exist
some Sigma^{0}_{alpha}-complete omega-powers, and some Pi^{0}_{alpha}-complete omega-powers.
**

**
**

Joint paper with Dominique Lecomte

* in the Proceedings of
Dagstuhl Seminar on "Topological and Game-Theoretic Aspects of Infinite
Computations" 29.06.08 - 04.07.08, Dagstuhl, Germany.*

**
Abstract.
This is an extended abstract presenting new results on the topological complexity of omega-powers
(which are included in a paper "Classical and effective descriptive complexities of omega-powers" published in the Annals of Pure and Applied Logic)
and reflecting also some open questions which were discussed during the Dagstuhl seminar on "Topological and Game-Theoretic Aspects of Infinite Computations" 29.06.08 - 04.07.08.
**

**
**

* in: ``Studies in Weak Arithmetics",
Proceedings of the International Conference
28 th Weak Arithmetic Days, Fontainebleau, France, June 17-19, 2009, edited by P. Cegielski,
Publications of the Center for the Study of Language and Information, Lecture Notes, Volume 196,
Stanford University, 2010, p. 127-151.
*

**
Abstract.
Altenbernd, Thomas and
Wöhrle have considered acceptance of
languages of infinite two-dimensional words (infinite pictures) by finite tiling systems,
with the usual acceptance conditions, such as the
Büchi and Muller ones, firstly used for infinite words.
Many classical decision problems are studied in formal language theory and in automata theory and arise now naturally about
recognizable languages of infinite pictures.
We first review in this paper some recent results of [ 29 ] where
we gave the exact degree of numerous undecidable problems for Büchi-recognizable
languages of infinite pictures, which are actually located at the first or at the
second level of the analytical hierarchy, and ``highly undecidable".
Then we prove here some more (high) undecidability results. We first show that it is Pi^{1}_{2}-complete to determine whether a given
Büchi-recognizable language of infinite pictures is unambiguous. Then we investigate cardinality problems.
We prove that it is D_{2}(Sigma_{1}^{1})-complete
to determine whether a given Büchi-recognizable language of infinite pictures is countably infinite, and that
it is Sigma^{1}_{1}-complete to determine whether a given Büchi-recognizable language of infinite pictures is uncountable.
Next we consider complements of recognizable languages of infinite pictures and
we show, using some results of Set Theory, that the cardinality of the complement of a Büchi-recognizable language of infinite pictures
may depend on the model of the axiomatic system ZFC.
**

**
**

*In Contributed Abstracts of the 2nd Workshop on Games for Design, Verification and Synthesis, GASICS 2010, Paris,
September 4, 2010. And
*

*
In
Contributed Abstracts of the Annual Workshop
of the ESF Networking Programme on Games for Design and Verification, GAMES 2010, Oxford, September 20-23, 2010.
*

Note: The results of this abstract are included in the following STACS conference paper.

*In the Proceedings
of the 29 th International Symposium on
Theoretical Aspects of Computer Science,
STACS 2012, Paris, France, February 29-March 3, 2012, Leibniz International
Proceedings in Informatics, Volume 14, 2012, p. 555-566. *

**
Abstract.
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by
real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal
assumption. We show also that the determinacy of Wadge games between two players in charge of
omega-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy.
Using some results of set theory we prove that one can effectively construct a
1-counter Büchi automaton A and a Büchi automaton B such that: (1) There exists a model of ZFC
in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B)); (2) There exists a model of ZFC
in which the Wadge game W(L(A), L(B)) is not determined.
Moreover these are the only two possibilities, i.e. there are no models of ZFC in which
Player 1 has a
winning strategy in the Wadge game W(L(A), L(B)).
**

**
**

*In Contributed Abstracts of Turing Centenary Conference,
Computability in Europe, CiE 2012, Cambridge,
June 18-23, 2012.
*

**
**

Joint paper with Jacques Duparc and Jean-Pierre Ressayre

*In the Proceedings of the International Symposium on Logical Foundations of Computer Science,
LFCS 2013, January 6 - 8, 2013,
San Diego, California, U.S.A, Lecture Notes in
Computer Science, Volume 7734, (c) Springer, 2013, p. 179-193.
*

* This paper was also exposed at the Annual Workshop of the ESF Networking Programme on Games for Design and Verification, GAMES 2012,
Napoli, Italy, September 7-12, 2012.
*

**(Extended version, on HAL
)
**

**
**

*In Contributed Abstracts of Logic Colloquium,
LC 2014, part of Vienna Summer of Logic, Vienna, Autriche, 14-18 juillet 2014.
*

*In the Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, Kyoto,
Japan, July 6-10, 2015,
Lecture Notes in
Computer Science, Volume 9135, (c) Springer, 2015, p. 222--233.
*

**(preprint, on HAL
)
**

**
**

*In Contributed Abstracts of the Twelfth International Conference on Computability in Europe, Pursuit of the Universal, CiE 2016, Paris,
June 27th- July 1st, 2016.
*