Asymptotic Density of Zimin Words

Abstract

Word \(W\) is an instance of word \(V\) provided there is a homomorphism \(\phi\) mapping letters to nonempty words so that \(\phi(V) = W\). For example, taking \(\phi\) such that \(\phi(c)=fr\), \(\phi(o)=e\) and \(\phi(l)=zer\), we see that "freezer" is an instance of "cool". Let \(\mathbb{I}_n(V,[q])\) be the probability that a random length \(n\) word on the alphabet \([q] = \{1,2,\cdots q\}\) is an instance of \(V\). Having previously shown that \(\lim_{n \rightarrow \infty} \mathbb{I}_n(V,[q])\) exists, we now calculate this limit for two Zimin words, \(Z_2 = aba\) and \(Z_3 = abacaba\).