An infinite sequence x1, x2, ... (one- or two-sided, though I'll only show the one-sided case) of symbols is called strongly recurrent if the following holds:

  • For every word w=xm...xm+l-1 that appears in the sequence there exists some constant L such that w appears somewhere in every word xk...xk+L-1 of length L that appears in the sequence.

Obviously, every periodic sequence is strongly recurrent. But there also exist aperiodic sequences that are strongly recurrent; the Morse sequence is one example of such a sequence.

In fact, for words over the 2-symbol alphabet {,1}, there exist only countably many periodic sequences, but uncountably many strongly recurrent sequences.

In terms of the trajectory of the infinite sequence (under the shift operation Sx=x2x3...), we say that a strongly recurrent sequence returns to every neighbourhood it visits at bounded times.

Log in or register to write something here or to contact authors.