Fix a finite alphabet Σ having at least two letters, and an arbitrary natural number n . We denote by D n ( Π 2 0 ) the class of differences of n Π 2 0 subsets of the Cantor space Σ ω , and by D n − ( Π 2 0 ) the class of complements of sets in D n ( Π 2 0 ) . We prove the existence of finitary regular languages U n and V n such that ( U n ) ω is D 2 n + 1 ( Π 2 0 ) -complete and ( V n ) ω is D 2 n + 2 − ( Π 2 0 ) -complete.

We prove that ω-languages of (non-deterministic) Petri nets and ω-languages of (nondeterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of ω-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of ω-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net ω-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for ω-languages of Petri nets are ∏21-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 ω-languages recognisable by unambiguous Petri nets are △30 sets.

We prove that the Büchi topology, the automatic topology, the alphabetic topology and the strong alphabetic topology are Polish, and provide consequences of this.

Abstract We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by realtime 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ω-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 and a Büchi automaton such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge gameW(L( ),L( )); (2) There exists a model of ZFC in which the Wadge gameW(L( ),L( )) 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 gameW(L( ),L( )).

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

Abstract We considerωn-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of lengthωnfor some integern≥ 1. We show that all these structures areω-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation forω2-automatic (resp.ωn-automatic forn> 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ωn-automatic boolean algebras,n≥ 2, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a -set nor a -set. We obtain that there exist infinitely manyωn-automatic, hence alsoω-tree-automatic, atomless boolean algebras , which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [14].

Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with usual acceptance conditions, such as the Büchi andMuller ones, in [1]. It was proved in [9] that it is undecidable whether a Büchirecognizable language of infinite pictures is E-recognizable (respectively, A-recognizable). We show here that these two decision problems are actually П-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 nonemptiness and the infiniteness problems are Σ-complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all П-complete. It is also П-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 ω.

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 ⩾ 1, there is a D _{ω^n} (Σ ^1_1 )-complete tree language L _n accepted by a (non deterministic) Muller tree automaton. On the other hand, we prove that a tree language accepted by an unambiguous Büchi tree automaton must be Borel. Then we consider the game tree languages W _{(ı,κ)} , for Mostowski-Rabin indices (ıκ). We prove that the D _{ω^n} (Σ ^1_1 )-complete tree languages L _n are Wadge reducible to the game tree language W _{(ı,κ)} for κ−ı⩾ 2. In particular these languages W _{(ı,κ)} are not in any class D _{α} (Σ ^1_1 ) for α<ω ^{ω} .

We show that the Borel hierarchy of the class of context free $\omega$ -languages, or even of the class of $\omega$ -languages accepted by Büchi 1-counter automata, is the same as the Borel hierarchy of the class of $\omega$ -languages accepted by Turing machines with a Büchi acceptance condition. In particular, for each recursive non-null ordinal $\alpha$ , there exist some ${\bf \Sigma}^0_\alpha$ -complete and some ${\bf \Pi}^0_\alpha$ -complete $\omega$ -languages accepted by Büchi 1-counter automata. And the supremum of the set of Borel ranks of context free $\omega$ -languages is an ordinal $\gamma_2^1$ that is strictly greater than the first non-recursive ordinal $\omega_1^{\mathrm{CK}}$ . We then extend this result, proving that the Wadge hierarchy of context free $\omega$ -languages, or even of $\omega$ -languages accepted by Büchi 1-counter automata, is the same as the Wadge hierarchy of $\omega$ -languages accepted by Turing machines with a Büchi or a Muller acceptance condition.

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, in a paper of this Journal, volume 53. 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(φ) of a local sentence φ, below ωω; where Sp(φ) is the set of ordinals α such that φ has a model of order type α (ii) proof that bethω = sup{Sp(φ): φ local sentence with a bounded spectrum} (iii) existence of a local sentence φ such that Sp(φ) contains all infinite ordinals except the inaccessible cardinals.