The Ehrenfeucht-Fraisse game is a two-person game of perfect information which is connected to the Zero-One Laws of first order logic. We give bounds for roughly how quickly the Zero-One Laws converge for random bit strings and random circular bit sequences. We measure the tenaciousness of the second player ("Duplicator") in playing the Ehrenfeucht-Fraisse game, by bounding the numbers of moves Duplicator can play and win with probability 1-∈. We show that for random bit strings and random circular sequences of length n generated with a low probability (p ≪ n -1), the number of moves, T ∈(n), is Θ(log 2 n). For random bit strings and circular sequences with isolated ones (n -1 ≪ p ≪ n -1/2), T ∈(n) = O(min(log 2 np,-log 2 np 2)). For n -1/2 ≪ p and (1 - p) ≪ n -1/2, we show that T ∈(n) = O(log* n) for random circular sequences, where log* n has the usual definition-the least number of times you iteratively apply the logarithm to get a value less than one.
|Original language||English (US)|
|Number of pages||14|
|Journal||Electronic Journal of Combinatorics|
|Issue number||2 R|
|State||Published - 2001|
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics