OFFSET
1,2
COMMENTS
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, ... .
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.
An instance W is minimal if no proper substring of W is also an instance.
The total number of minimal Z_n-instances over the alphabet {0,1} is 2*a(n).
The minimal, binary Z_3-instances have lengths ranging from 7 to 25. There exist minimal, binary Z_4-instances over 10000 letters long.
LINKS
D. Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 2.3.
Danny Rorabaugh, Binary, minimal Z_3-instances that begin with 0
W. Rytter, and A. Shur, Searching for Zimin patterns, Theoretical Comp. Sci., 571 (2015), 50-57. [Preprint: On Searching Zimin Patterns (2014). See section 4.2.]
A. I. Zimin, Blokirujushhie mnozhestva termov (Russian), Mat. Sbornik, 119 (1982), 363-375; Blocking sets of terms (English), Math. USSR-Sbornik, 47 (1984), 353-364.
EXAMPLE
The a(1)=1 instance of Z_1 is '0'.
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.
CROSSREFS
KEYWORD
nonn,bref,hard,more
AUTHOR
Danny Rorabaugh, Sep 24 2015
STATUS
approved