64
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

Asymptotic Density of Zimin Words

Preprint

,

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

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$$.

Author and article information

Journal
2015-10-13
2016-03-16
1510.03917