On the Ehrenfeucht–Mycielski sequence |
| |
Authors: | Grzegorz Herman Michael Soltys |
| |
Affiliation: | aMcMaster University, Computing and Software, 1280 Main Street West, Hamilton, ON, Canada |
| |
Abstract: | We introduce the inverted prefix tries (a variation of suffix tries) as a convenient formalism for stating and proving properties of the Ehrenfeucht–Mycielski sequence [A. Ehrenfeucht, J. Mycielski, A pseudorandom sequence—how random is it? American Mathematical Monthly 99 (1992) 373-375]. We also prove an upper bound on the position in the sequence by which all strings of a given length will have appeared; our bound is given by the Ackermann function, which, in light of experimental data, may be a gross over-estimate. Still, it is the best explicitly known upper bound at the moment. Finally, we show how to compute the next bit in the sequence in a constant number of operations. |
| |
Keywords: | Ehrenfeucht– Mycielski sequence Prefix tries Ackermann function Pseudo-random |
本文献已被 ScienceDirect 等数据库收录! |
|