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

We prove that for every countable ordinal α one cannot decidewhether a given infinitary rational relation is in the Borel class ${\bf \Sigma_{\alpha}^0}$ (respectively ${\bf \Pi_{\alpha}^0}$ ). Furthermoreone cannotdecide whether a given infinitary rational relation is a Borel set or a ${\bf \Sigma_{1}^1}$ -complete set. We prove some recursive analogues to theseproperties. In particular one cannot decide whether an infinitary rational relation is anarithmetical set.We then deduce from the proof ofthese results some other ones, like: one cannot decide whether thecomplement ofan infinitary rational relation is also an infinitary rational relation.

The aim of this paper is to study the threshold behavior for the satisfiability property of a random k-XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with k variables per equation. For k ≥ 3 we show the existence of a sharp threshold for the satisfiability of a random k-XOR-CNF formula, whereas there are smooth thresholds for k=1 and k=2.

We give a bound for the ω-equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.

We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.