A note on balanced immunity

Abstract

For a finite alphabet ∑ we define a binary relation on$2^{\Sigma *} \times 2^{2^{\Sigma ^* } }$, called balanced immunity. A setB ⊑ ∑* is said to be balancedC-immune (with respect to a classC ⊑ 2^Σ* of sets) iff, for all infiniteL εC,

$$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$

Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.