CIAA2003

START ConferenceManager

The Ehrenfeucht-Mycielski Sequence

Klaus Sutner

Presented at Eighth International Conference on Implementation and Application of Automata (CIAA 2003), July 16-18, 2003 Santa Barbara, CA, USA

Abstract

We study the disjunctive binary sequence introduced by Ehrenfeucht and Mycielski. The match length associated to the bits of the sequence is shown to be a crucial tool in the analysis of the sequence. We show that the match length between two consecutive bits in the sequence differs at most by 1 and give a lower bound for the limiting density of the sequence. The results rest heavily on experimental computation in the automata package.