Olivier Finkel




Équipe de Logique Mathématique
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
E-Mail: finkel_at_math.univ-paris-diderot.fr  



  • Thèmes de Recherche

  • Théorie des Modèles des Formules Locales
  • Complexité Descriptive
  • Théorie des Modèles Finis
  • Omega Langages Rationnels, Algébriques, Localement Finis
  • Relations Rationnelles Infinitaires
  • Propriétés Topologiques des Omega Langages
  • Machines Finies
  • Stratégies Gagnantes dans les Jeux Infinis
  • Automates et Langages Temporisés
  • Automates Cellulaires
  • Structures Automatiques

  • Research Areas

  • Model Theory of Local Sentences
  • Descriptive Complexity
  • Finite Model Theory
  • Regular, Context Free, and Locally Finite Omega Languages
  • Infinitary Rational Relations
  • Topological Properties of Omega Languages
  • Finite Machines
  • Winning Strategies in Infinite Games
  • Timed Automata and Timed Languages
  • Cellular Automata
  • Automatic Structures


  • Publications

  • Journal papers
  • Chapters of Books
  • Conference papers
  • Thesis
  • Habilitation

    Some preprints on CNRS HAL Server

  • Some talks


    Journal papers


    1. Langages de Büchi et Omega Langages Locaux

    2. 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."


    3. Stretchings

    4. 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 omegaomega ; 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.


    5. Locally Finite Languages

    6. 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 < omegaomega ) 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 , <).


    7. Topological Properties of Omega Context Free Languages

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


    9. Computer Science and the Fine Structure of Borel Sets

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


    11. Wadge Hierarchy of Omega Context Free Languages

    12. 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 epsilon0, 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.


    13. Borel Hierarchy and Omega Context Free Languages

    14. 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 Lomega 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.


    15. Ambiguity in Omega Context Free Languages

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


    17. On Omega Context Free Languages which are Borel Sets of Infinite Rank

    18. 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].


    19. Topological Complexity of Locally Finite Omega Languages

    20. 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 LOComega 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].


    21. Closure Properties of Locally Finite Omega Languages

    22. 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 LOComega of locally finite omega languages. In particular we show that the class LOComega is neither closed under intersection nor under complementation, giving an answer to a question of Ressayre.


    23. On the Topological Complexity of Infinitary Rational Relations

    24. 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].


    25. On the Length of the Wadge Hierarchy of Omega Context Free Languages

    26. 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 epsilonomega, which is the omegath 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 Sigma0omega-complete Borel sets, improving previous results on omega context free languages and the Borel hierarchy.


    27. Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations

    28. 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 Sigma0alpha ( respectively Pi0alpha). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a Sigma11-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.


    29. On Infinite Real Trace Rational Languages of Maximum Topological Complexity

    30. 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 Sigma11-complete, hence of maximum possible topological complexity.


    31. Topology and Ambiguity in Omega Context Free Languages

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


    33. On Recognizable Languages of Infinite Pictures

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

      (preprint, on HAL or ArXiv )

      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 omega2. 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 omega2 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 gamma21 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 [ Pi11 Borel sets, Journal of Symbolic Logic, Volume 54 (3), p. 915-920, 1989 ].


    35. An Example of Pi30-complete Infinitary Rational Relation

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

      (preprint, on HAL or ArXiv )

      Abstract. We give in this paper an example of infinitary rational relation, accepted by a 2-tape Büchi automaton, which is Pi30-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.


    37. An omega-Power of a Finitary Language Which is a Borel Set of Infinite Rank

    38. 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 Vomega, 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 Pin0-complete Borel sets, and in [ 7 ] that there exists a context free language L such that Lomega is analytic but not Borel. But the question was still open whether there exists a finitary language V such that Vomega 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.


    39. On Decidability Properties of Local Sentences

    40. 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 omega2 is not determined by the axiomatic system ZFC + GCH, where GCH is the generalized continuum hypothesis.


    41. On Winning Conditions of High Borel Complexity in Pushdown Games

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


    43. On Decision Problems for Timed Automata

    44. Bulletin of the European Association for Theoretical Computer Science, Volume 87, October 2005, p. 185-190.

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


    45. On the Shuffle of Timed Regular Languages

    46. Bulletin of the European Association for Theoretical Computer Science, Volume 88, February 2006, p. 182-184.

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


    47. Borel Ranks and Wadge Degrees of Omega Context Free Languages

    48. Mathematical Structures in Computer Science, Volume 16 ( 5), October 2006, p. 813-840.

      (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 Sigma0alpha-complete and some Pi0alpha-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 gamma21 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].


    49. Local Sentences and Mahlo Cardinals

    50. Joint paper with Stevo Todorcevic

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

      (preprint, on HAL or ArXiv )

      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.


    51. Classical and Effective Descriptive Complexities of omega-Powers

    52. Joint paper with Dominique Lecomte

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

      (preprint, on HAL or ArXiv )

      Abstract. We prove that, for each non null countable ordinal alpha, there exist some Sigma0alpha-complete omega-powers, and some Pi0alpha-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 Aomega is Sigma0alpha-complete (respectively, Pi0alpha-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-Pi0alpha and Effective-Sigma0alpha 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].


    53. On the Continuity Set of an omega Rational Function

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

      (preprint, on HAL or ArXiv )

      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 Pi20-subset of Xomega for some alphabet X is the continuity set C(F) of an omega-rational synchronous function F defined on Xomega.


    55. Wadge Degrees of Infinitary Rational Relations

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

      (preprint, on HAL or ArXiv )

      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 Sigma0alpha-complete and some Pi0alpha-complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal gamma21 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].


    57. Highly Undecidable Problems about Recognizability by Tiling Systems

    58. Special Issue on Machines, Computations and Universality.

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

      (preprint, on HAL or ArXiv )

      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 Pi12-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 Sigma11-complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all Pi12-complete. It is also Pi12-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 omega2.


    59. On Recognizable Tree Languages Beyond the Borel Hierarchy

    60. Joint paper with Pierre Simonnet

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

      (preprint, on HAL or ArXiv )

      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)(Sigma11)-complete tree language Ln 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)(Sigma11)-complete tree languages Ln 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)(Sigma11) for alpha < omegaomega.


    61. Highly Undecidable Problems For Infinite Computations

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

      (preprint, on HAL or ArXiv )

      Abstract. We show that many classical decision problems about 1-counter omega-languages, context free omega-languages, or infinitary rational relations, are Pi12-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 Pi12-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.


    63. On Decidability Properties of One-Dimensional Cellular Automata

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

      (preprint, on HAL or ArXiv )

      Abstract. In a recent paper Sutner proved that the first-order theory of the phase-space SA=(QZ, Succ) of a one-dimensional cellular automaton A whose configurations are elements of QZ 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 SA 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 SA 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.


    65. Decision Problems For Turing Machines

    66. Joint paper with Dominique Lecomte

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

      (preprint, on HAL or ArXiv )

      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 D2(Sigma11)-complete to determine whether the omega-language of a given Turing machine is countably infinite, where D2(Sigma11) is the class of 2-differences of Sigma11-sets. Secondly, it is Sigma11-complete to determine whether the omega-language of a given Turing machine is uncountable.


    67. On Some Sets of Dictionaries Whose omega-Powers Have a Given Complexity

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

      (preprint, on HAL or ArXiv )

      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(Sigmak0) (respectively,W(Pik0), W(Delta11) of dictionaries V whose omega-powers are Sigmak0-sets (respectively, Pik0-sets, Borel sets). As an application we improve the lower bound of the complexity of W(Delta11) given by Lecomte in [Omega-Powers and Descriptive Set Theory, Journal of Symbolic Logic, Volume 70 (4), 2005, p. 1210-1232].


    69. The Complexity of Infinite Computations In Models of Set Theory

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

      (preprint, on HAL or ArXiv )

      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 V1 of ZFC in which the omega-language L(A) and the infinitary rational relation L(B) are Pi20-sets, and (2) There is a model V2 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].


    71. The Isomorphism Relation Between Tree-Automatic Structures

    72. Joint paper with Stevo Todorcevic

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

      (preprint, on HAL or ArXiv )

      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 Sigma21-set nor a Pi21-set.


    73. Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language

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

      (preprint, on HAL or ArXiv )

      Abstract. It was noticed by Harel in [Har86] that ``one can define Sigma11-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 Sigma11-complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result that it is Pi11-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 Sigma11-complete to determine whether a given omega-rational function has at least one point of continuity. Next we prove that it is Pi11-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].


    75. A Hierarchy of Tree-Automatic Structures

    76. Joint paper with Stevo Todorcevic

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

      (preprint, on HAL or ArXiv )

      Abstract. We consider omegan-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length omegan 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 omega2-automatic (resp. omegan-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 omegan-automatic boolean algebras, n>1, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a Sigma21-set nor a Pi21-set. We obtain that there exist infinitely many omegan-automatic, hence also omega-tree-automatic, atomless boolean algebras Bn, 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].


    77. Some Problems in Automata Theory Which Depend on the Models of Set Theory

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

      (preprint, on HAL or ArXiv )

      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 V1 of ZFC in which L(A)c is countable. (2). There is a model V2 of ZFC in which L(A)c has the cardinality of the continuum. (3). There is a model V3 of ZFC in which L(A)c has cardinal Aleph1 with Aleph0 < Aleph1 < 2Aleph0. 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 Sigma31 but neither in Sigma21 nor in Pi21.


    79. Automatic Ordinals

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

      (preprint, on HAL or ArXiv )

      Abstract. We prove that the injectively omega-tree-automatic ordinals are the ordinals smaller than $\omega^{\omega^\omega}$. Then we show that the injectively omegan-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 omegan-automatic ordinals. As a by-product we obtain that the hierarchy of injectively omegan-automatic structures, n>0, which was considered in [Finkel-Todorcevic12], is strict.


    81. The Determinacy of Context-Free Games

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

      (preprint, on HAL or ArXiv )

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


    83. On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets

    84. Joint paper with Michal Skrzypczak

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

      (preprint, on HAL or ArXiv )

      Abstract. We show that there are Sigma30-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.


    85. Ambiguity of omega-Languages of Turing Machines

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

      (preprint, on HAL or ArXiv )

      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 Sigma11 of (effective) analytic subsets of Xomega 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.


    87. The Exact Complexity of the Infinite Post Correspondence Problem

    88. 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 Pi10-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 Sigma10-complete, but has the exact dual complexity. This gives an answer to a question of Simonnet.


    89. An Upper Bound on the Complexity of Recognizable Tree Languages

    90. Joint paper with Dominique Lecomte and Pierre Simonnet

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

      (preprint, on HAL or ArXiv )

      Abstract. The third author noticed in his 1992 PhD Thesis that every regular tree language of infinite trees is in a class G( Dn(Sigma20) ) 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 Delta21, 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 Delta21.


    91. Locally Finite omega-Languages and Effective Analytic Sets Have the Same Topological Complexity

    92. 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 Sigmaalpha0-complete and some Pialpha0-complete locally finite omega-languages, and the supremum of the set of Borel ranks of locally finite omega-languages is the ordinal gamma21 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 Pi21-complete, hence highly undecidable.


    93. Infinite Games Specified by 2-Tape Automata

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

      (preprint, on HAL or ArXiv )

      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.


    Chapters of Books


    1. Topological Complexity of Context-Free omega-Languages: A Survey

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

      (preprint, on HAL or ArXiv )


    3. The Wadge Hierarchy of Petri Nets omega-Languages

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


    Conference papers


    1. Infinite Games, Finite Machines
    2. 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.


    3. Propriétés Topologiques des Omega Langages Algébriques
    4. (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.


    5. On Locally Finite languages
    6. Abstract, in Contributed Papers of Logic Colloquium 2000 , Paris, 23-31 July 2000, p. 149-150


    7. An Effective Extension of the Wagner Hierarchy to Blind Counter Automata
    8. 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.


    9. On the Wadge Hierarchy of Omega Context Free Languages
    10. 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 epsilonomega, which is the omegath 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.


    11. Topological and Arithmetical Properties of Infinitary Rational Relations
    12. 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.


    13. Topology and Ambiguity in Context Free Omega Languages
    14. 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.


    15. On Infinitary Rational Relations and Borel Sets
    16. 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 Sigma30-complete Borel sets and some others which are Pi30-complete. This implies that there exists some infinitary rational relations which are Delta40-sets but not (Sigma30U Pi30)-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].


    17. On Infinite Real Trace Rational Languages of Maximum Topological Complexity
    18. 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.


    19. On Decidability Properties of Local Sentences
    20. 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 omega2 is not determined by the axiomatic system ZFC + GCH, where GCH is the generalized continuum hypothesis.


    21. On the Points of Continuity of an Omega Rational Function
    22. 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 Pi20-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 Pi20 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.


    23. An omega-Power of a Context Free Language which is Borel above Deltaomega0
    24. 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 Deltaomega0 in the Borel hierarchy.


    25. Borel Ranks and Wadge Degrees of Omega Context Free Languages
    26. 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.

      (preprint, ps file or pdf file )

      Abstract. We show that, for each recursive non null ordinal alpha, there exist some Sigma0alpha-complete and some Pi0alpha-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 gamma21 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 [ Pi11 Borel sets, Journal of Symbolic Logic, Volume 54 (3), p. 915-920, 1989 ].


    27. On the Accepting Power of 2-Tape Büchi Automata
    28. 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 Sigma0alpha-complete and some Pi0alpha-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].


    29. Undecidable Problems About Timed Automata
    30. 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 Pi11-hard, hence highly undecidable (located beyond the arithmetical hierarchy).


    31. There Exist some Omega-Powers of Any Borel Rank
    32. 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.

      (preprint, on HAL or ArXiv )

      Abstract. Omega-powers of finitary languages are omega languages in the form Vomega, 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 Pin0-complete Borel sets, and in [ 7 ] that there exists a context free language L such that Lomega is analytic but not Borel. It has been also proved in [ 19 ] that there exists a finitary language V such that Vomega 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 Sigma0alpha-complete omega-powers, and some Pi0alpha-complete omega-powers.


    33. Topological Complexity of omega-Powers : Extended Abstract
    34. 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.

      (preprint, on HAL or ArXiv )

      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.


    35. Decision Problems for Recognizable Languages of Infinite Pictures
    36. 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.

      (preprint, on HAL or ArXiv )

      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 Pi12-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 D2(Sigma11)-complete to determine whether a given Büchi-recognizable language of infinite pictures is countably infinite, and that it is Sigma11-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.


    37. Wadge Games Betweeen 1-Counter Automata and Models of Set Theory
    38. 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.


    39. The Determinacy of Context-Free Games
    40. 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.

      (preprint, on HAL or ArXiv )

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


    41. Ambiguity of omega-Languages of Turing Machines
    42. In Contributed Abstracts of Turing Centenary Conference, Computability in Europe, CiE 2012, Cambridge, June 18-23, 2012.

      (paper, on HAL or ArXiv )


    43. The Wadge Hierarchy of Petri Nets omega-Languages
    44. 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 )


    45. Infinite games specified by 2-tape automata
    46. In Contributed Abstracts of Logic Colloquium, LC 2014, part of Vienna Summer of Logic, Vienna, Autriche, 14-18 juillet 2014.


    47. Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words
    48. 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 )


    49. Independence Results in Automata Theory
    50. In Contributed Abstracts of the Twelfth International Conference on Computability in Europe, Pursuit of the Universal, CiE 2016, Paris, June 27th- July 1st, 2016.


    Thèses






      Home Page of Olivier Finkel / Logic team of Paris VII