Some preprints on CNRS HAL Server

Journal papers

1. Langages de Büchi et Omega Langages Locaux

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

---

2. Stretchings

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.

---

3. Locally Finite Languages

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

---

4. Topological Properties of Omega Context Free Languages

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.

---

5. Computer Science and the Fine Structure of Borel Sets

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.

---

6. Wadge Hierarchy of Omega Context Free Languages

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₀, 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.

---

7. Borel Hierarchy and Omega Context Free 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.

---

8. Ambiguity in Omega Context Free Languages

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.

---

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

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

---

10. Topological Complexity of Locally Finite Omega Languages

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

---

11. Closure Properties of Locally Finite Omega Languages

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.

---

12. On the Topological Complexity of Infinitary Rational Relations

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

---

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

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⁰_omega-complete Borel sets, improving previous results on omega context free languages and the Borel hierarchy.

---

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

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⁰_alpha ( respectively Pi⁰_alpha). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a Sigma₁¹-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.

---

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

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

---

16. Topology and Ambiguity in Omega Context Free Languages

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.

---

17. On Recognizable Languages of Infinite Pictures

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 omega². 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² 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₂¹ 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₁¹ Borel sets, Journal of Symbolic Logic, Volume 54 (3), p. 915-920, 1989 ].

---

18. An Example of Pi₃⁰-complete Infinitary Rational Relation

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 Pi₃⁰-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.

---

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

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

---

20. On Decidability Properties of Local Sentences

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

---

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

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.

---

22. On Decision Problems for Timed Automata

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.

---

23. On the Shuffle of Timed Regular Languages

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

---

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

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 Sigma⁰_alpha-complete and some Pi⁰_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₂¹ 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].

---

25. Local Sentences and Mahlo Cardinals

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.

---

26. Classical and Effective Descriptive Complexities of omega-Powers

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 Sigma⁰_alpha-complete omega-powers, and some Pi⁰_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⁰_alpha-complete (respectively, Pi⁰_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⁰_alpha and Effective-Sigma⁰_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].

---

27. On the Continuity Set of an omega Rational Function

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 Pi₂⁰-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.

---

28. Wadge Degrees of Infinitary Rational Relations

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 Sigma⁰_alpha-complete and some Pi⁰_alpha-complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal gamma₂¹ 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].

---

29. Highly Undecidable Problems about Recognizability by Tiling Systems

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 Pi¹₂-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¹₁-complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all Pi¹₂-complete. It is also Pi¹₂-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².

---

30. On Recognizable Tree Languages Beyond the Borel Hierarchy

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_(omegaⁿ)(Sigma₁¹)-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_(omegaⁿ)(Sigma₁¹)-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₁¹) for alpha < omega^omega.

---

31. Highly Undecidable Problems For Infinite Computations

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 Pi¹₂-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¹₂-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.

---

32. On Decidability Properties of One-Dimensional Cellular Automata

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

---

33. Decision Problems For Turing Machines

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

---

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

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

---

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

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

---

36. The Isomorphism Relation Between Tree-Automatic Structures

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 Sigma₂¹-set nor a Pi₂¹-set.

---

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

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 Sigma₁¹-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₁¹-complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result that it is Pi₁¹-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₁¹-complete to determine whether a given omega-rational function has at least one point of continuity. Next we prove that it is Pi₁¹-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].

---

38. A Hierarchy of Tree-Automatic Structures

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 omegaⁿ-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length omegaⁿ 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²-automatic (resp. omegaⁿ-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ⁿ-automatic boolean algebras, n>1, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a Sigma₂¹-set nor a Pi₂¹-set. We obtain that there exist infinitely many omegaⁿ-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].

---

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

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 V₁ of ZFC in which L(A)^c is countable. (2). There is a model V₂ of ZFC in which L(A)^c has the cardinality of the continuum. (3). There is a model V₃ of ZFC in which L(A)^c has cardinal Aleph₁ with Aleph₀ < Aleph₁ < 2^Aleph₀. 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₃¹ but neither in Sigma₂¹ nor in Pi₂¹.

---

40. Automatic Ordinals

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 omegaⁿ-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ⁿ-automatic ordinals. As a by-product we obtain that the hierarchy of injectively omegaⁿ-automatic structures, n>0, which was considered in [Finkel-Todorcevic12], is strict.

---

41. The Determinacy of Context-Free Games

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

---

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

Joint paper with Michał Skrzypczak

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

(preprint, on HAL or ArXiv )

Abstract. We show that there are Sigma₃⁰-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.

---

43. Ambiguity of omega-Languages of Turing Machines

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 Sigma₁¹ 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.

---

44. The Exact Complexity of the Infinite Post Correspondence Problem

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

---

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

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( D_n(Sigma₂⁰) ) 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₂¹, 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₂¹.

---

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

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⁰-complete and some Pi_alpha⁰-complete locally finite omega-languages, and the supremum of the set of Borel ranks of locally finite omega-languages is the ordinal gamma₂¹ 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₂¹-complete, hence highly undecidable.

---

47. Infinite Games Specified by 2-Tape Automata

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.

---

48. Incompleteness Theorems, Large Cardinals, and Automata over Finite Words

International Journal of Foundations of Computer Science, Volume 30 (3), April 2019, p. 449-467.

(preprint, on HAL )

Abstract. We prove that one can construct various kinds of automata over finite words for which some elementary properties are actually independent from strong set theories like T_n =: ZFC + ``There exist (at least) n inaccessible cardinals", for integers n > 0. In particular, we prove independence results for languages of finite words generated by context-free grammars, or accepted by 2-tape or 1-counter automata. Moreover we get some independence results for weighted automata and for some related finitely generated subsemigroups of the set $\mathbb{Z}^{3\times 3}$ of 3-3 matrices with integer entries. Some of these latter results are independence results from the Peano axiomatic system PA.

---

49. Computational Capabilities of Analog and Evolving Neural Networks over Infinite Input Streams

Joint paper with Jérémie Cabessa


Journal of Computer and System Sciences, Volume 101, May 2019, p. 86-99.

(preprint, on HAL )

Abstract. Analog and evolving recurrent neural networks are super-Turing powerful. Here, we consider analog and evolving neural nets over infinite input streams. We then characterize the topological complexity of their $\omega$-languages as a function of the specific analog or evolving weights that they employ. As a consequence, two infinite hierarchies of classes of analog and evolving neural networks based on the complexity of their underlying weights can be derived. These results constitute an optimal refinement of the super-Turing expressive power of analog and evolving neural networks. They show that analog and evolving neural nets represent natural models for oracle-based infinite computation.

---

50. Polishness of Some Topologies Related to Word or Tree Automata

Joint paper with Olivier Carton and Dominique Lecomte


Logical Methods in Computer Science, Volume 15 (2:9), May 2019, p. 1-21.

(preprint, on HAL or ArXiv )

Abstract. We prove that the Büchi topology and the automatic topology are Polish. We also show that this cannot be fully extended to the case of a space of infinite labelled binary trees; in particular the Büchi and the Muller topologies are not Polish in this case.

---

51. Some Complete omega-Powers of a One-Counter Language, for Any Borel Class of Finite Rank

Joint paper with Dominique Lecomte


Archive for Mathematical Logic, Volume 60 (1-2), February 2021, p. 161–187.

(preprint, on HAL or ArXiv )

Abstract. We prove that, for any natural number n > 0, there exists a finitary language L which is accepted by a one-counter automaton and such that the omega-power $L^\infty$ is $\Pi^0_n$-complete. We prove a similar result for the class $Sigma^0_n$.

---

52. On the Expressive Power of Non-Deterministic and Unambiguous Petri Nets over Infinite Words

Joint paper with Michał Skrzypczak

Special Issue: Extended versions of papers from Petri Nets 2020.

Fundamenta Informaticae, Volume 183 (3-4), December 2021, p. 243–291.

(preprint, on HAL or ArXiv )

Abstract. We prove that omega-languages of (non-deterministic) Petri nets and omega-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of omega-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of omega-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net omega-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for omega-languages of Petri nets are $\Pi_2^1$-complete, hence also highly undecidable. Additionally, we show that the situation is quite the opposite when considering unambiguous Petri nets, which have the semantic property that at most one accepting run exists on every input. We provide a procedure of determinising them into deterministic Muller counter machines with counter copying. As a consequence, we entail that the omega-languages recognisable by unambiguous Petri nets are $\Delta^0_3$-sets.

---

53. Two Effective Properties of omega-Rational Functions

International Journal of Foundations of Computer Science, Volume 32 (7), November 2021, p. 901–920.

(preprint, on HAL )

Abstract. We prove two new effective properties of rational functions over infinite words which are realized by finite state Büchi transducers. Firstly, for each such function $F: X^\omega \rightarrow Y^\omega$, one can construct a deterministic Büchi automaton A accepting a dense $\Pi^0_2$-subset of $X^\omega$ such that the restriction of $F$ to $L(A)$ is continuous. Secondly, we give a new proof of the decidability of the first Baire class for synchronous omega-rational functions from which we get an extension of this result involving the notion of Wadge classes of regular omega-languages.

---

54. On Bi-infinite and Conjugate Post Correspondence Problems

Joint paper with Vesa Halava and Tero Harju and Esa Sahla


RAIRO- Theoretical Informatics and Applications, Volume 57, October 2023, Article number 7, p. 1-11.

(preprint, on HAL )

Abstract. We study two modifications of the Post Correspondence Problem (PCP), namely 1) the bi-infinite version, where it is asked whether there exists a bi-infinite word such that two given morphisms agree on it, and 2) the conjugate version, where we require the images of a solution for two given morphisms are conjugates of each other. For the bi-infinite PCP we show that it is in the class $\Sigma^0_2$ of the arithmetical hierarchy and for the conjugate PCP we give an undecidability proof by reducing it to the word problem for a special type of semi-Thue systems.

---

55. Wadge Degrees of $\Delta^0_2$ omega-Powers

Joint paper with Dominique Lecomte


Mathematical Logic Quaterly, to appear.

(preprint, on HAL or ArXiv )

Abstract. We provide, for each natural number n and each class among $D_n(\Sigma^0_1)$, $D^-_n(\Sigma^0_1)$, a regular language whose associated omega-power is complete for this class.