Abstract of Paper

On selection functions that do not preserve normality
by Wolfgang Merkle and Jan Reimann

Abstract:

The subsequence selected from a sequence R(0)R(1)... by a language L is 
the sequence
of all bits R(n+1) such that the prefix R(0)...R(n) is in L. By a 
result of Agafonoff, a
sequence is normal if and only if any subsequence selected by a regular 
language is
again normal. Kamae and Weiss and others have raised the question of 
how complex a
language must be such that selecting according to the language does not 
preserve
normality. We show that there are such languages that are only slightly 
more complicated
than regular ones, namely, normality is neither preserved by linear 
languages nor by
languages recognized by deterministic push-down automata with unary 
stack alphabet.
In fact, for both types of languages it is possible to select a 
constant sequence from a
normal one.