login
The Rote-Fibonacci infinite sequence.
24

%I #8 Jul 14 2018 21:00:35

%S 0,0,1,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0,1,0,0,

%T 1,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,1,1,0,1,1,

%U 0,0,1,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0,1,1

%N The Rote-Fibonacci infinite sequence.

%C This is an aperiodic sequence that avoids the pattern x x x^R, where x is a nonempty block and x^R denotes the reversal of x.

%C It can be generated as the limit of the words R(i), where R(0) = 0, R(1) = 00, and R(n) = R(n-1)R(n-2) if n == 0 (mod 3), and R(n) = R(n-1) c(R(n-2)) if n == 1, 2 (mod 3), where c flips 0 to 1 and vic-versa.

%C It can also be generated as the image, under the coding that maps a, b -> 0 and c, d -> 1, of the fixed point (see A316340), starting with a, of the morphism a -> abcab, b -> cda, c -> cdacd, d -> abc.

%H Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, Luca Q. Zamboni, <a href="https://arxiv.org/pdf/1711.10807.pdf">A Taxonomy of Morphic Sequences</a>, arXiv preprint arXiv:1711.10807, Nov 29 2017

%H C. F. Du, H. Mousavi, E. Rowland, L. Schaeffer, J. Shallit, <a href="https://cs.uwaterloo.ca/~shallit/Papers/part2e.pdf">Decision algorithms for Fibonacci-automatic words, II: related sequences and avoidability</a>, preprint, February 10 2016.

%Y Cf. A316340.

%K nonn

%O 0

%A _Jeffrey Shallit_, May 16 2016