Blog
About

  • Record: found
  • Abstract: found
  • Article: found
Is Open Access

Asymptotic Density of Zimin Words

Preprint

Read this article at

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\).

      Related collections

      Author and article information

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

      http://arxiv.org/licenses/nonexclusive-distrib/1.0/

      Custom metadata
      Discrete Mathematics & Theoretical Computer Science, Vol. 18, no 3, Combinatorics (March 17, 2016) dmtcs:1414
      25 pages
      math.CO

      Combinatorics

      Comments

      Comment on this article

      Similar content 10,732