A262500 - OEIS

%I #20 Sep 27 2015 10:30:42

%S 1,3,1751

%N Number of binary, minimal instances of Zimin word Z_n that begin with 0.

%C Zimin words are defined recursively by Z_1 = x_1, Z_{n+1} = Z_nx_{n+1}Z_n. Using a different alphabet: Z_1 = a, Z_2 = aba, Z_3 = abacaba, ... .

%C Word W over alphabet L is an instance of Z_n provided there exists a nonerasing monoid homomorphism f:{x_1,...,x_n}*->L* such that f(W)=Z_n. For example "abracadabra" is an instance of Z_2 via the homomorphism defined by f(x_1)=abra, f(x_2)=cad.

%C An instance W is minimal if no proper substring of W is also an instance.

%C The total number of minimal Z_n-instances over the alphabet {0,1} is 2*a(n).

%C The minimal, binary Z_3-instances have lengths ranging from 7 to 25. There exist minimal, binary Z_4-instances over 10000 letters long.

%H D. Rorabaugh, <a href="http://arxiv.org/abs/1509.04372">Toward the Combinatorial Limit Theory of Free Words</a>, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 2.3.

%H Danny Rorabaugh, <a href="/A262500/a262500.txt">Binary, minimal Z_3-instances that begin with 0</a>

%H W. Rytter, and A. Shur, <a href="http://dx.doi.org/10.1016/j.tcs.2015.01.004">Searching for Zimin patterns</a>, Theoretical Comp. Sci., 571 (2015), 50-57. [Preprint: <a href="http://arxiv.org/abs/1409.8235">On Searching Zimin Patterns</a> (2014). See section 4.2.]

%H A. I. Zimin, <a href="http://mi.mathnet.ru/msb2889">Blokirujushhie mnozhestva termov</a> (Russian), Mat. Sbornik, 119 (1982), 363-375; <a href="http://mi.mathnet.ru/eng/msb2889">Blocking sets of terms</a> (English), Math. USSR-Sbornik, 47 (1984), 353-364.

%e The a(1)=1 instance of Z_1 is '0'.

%e The a(2)=3 instances of Z_2 are '000', '010', and '0110'. '01110' is not a minimal instance because it contains Z_2-instance '111' as a proper subword.

%Y Cf. A123121, A262312, A262313.

%K nonn,bref,hard,more

%O 1,2

%A _Danny Rorabaugh_, Sep 24 2015