Name
Abstract | ||
|---|---|---|
Word W is said to encounter word V provided there is a homomorphism f mapping letters to nonempty words so that phi(V) is a substring of W. For example, taking phi such that phi(h) = c and phi(u) = ien, we see that "science" encounters "huh" since cienc = phi(huh). The density of V in W, delta(V,W), is the proportion of substrings of W that are homomorphic images of V. So the density of "huh" in "science" is 2/((8)(2)). A word is doubled if every letter that appears in the word appears at least twice. The dichotomy: Let V be a word over any alphabet, Sigma a finite alphabet with at least 2 letters, and W-n is an element of Sigma(n) chosen uniformly at random. Word V is doubled if and only if E(delta(V, W-n)) -> 0 as n -> infinity. We further explore convergence for nondoubled words and concentration of the limit distribution for doubled words around its mean. |
Year | Venue | Keywords |
|---|---|---|
2015 | CONTRIBUTIONS TO DISCRETE MATHEMATICS | Doubled words,homomorphism density,word patterns |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Substring,Limit distribution,Homomorphism,Mathematics,Alphabet | Journal | 13 |
Issue | ISSN | Citations |
1 | 1715-0868 | 1 |
PageRank | References | Authors |
0.51 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joshua Cooper | 1 | 13 | 2.56 |
| Danny Rorabaugh | 2 | 1 | 1.18 |