Permanent URL to this publication: http://dx.doi.org/10.5167/uzh-22128

**Cakir, I; Chryssaphinou, O; Månsson, M (1999). On a conjecture by Eriksson concerning overlap in strings. Combinatorics, Probability & Computing, 8(5):429-440.**

| PDF 183Kb |

## Abstract

Consider a finite alphabet Ω and strings consisting of elements from Ω. For a given string w, let cor(w) denote the autocorrelation, which can be seen as a measure of the amount of overlap in w. Furthermore, let aw(n) be the number of strings of length n that do not contain w as a substring. Eriksson [4] stated the following conjecture: if cor(w)>cor(w′), then aw(n)>aw′(n) from the first n where equality no longer holds. We prove that this is true if [mid R:]Ω[mid R:][gt-or-equal, slanted]3, by giving a lower bound for aw(n)−aw′(n).

Item Type: | Journal Article, refereed, original work |
---|---|

Communities & Collections: | 07 Faculty of Science > Institute of Mathematics |

DDC: | 510 Mathematics |

Language: | English |

Date: | 1999 |

Deposited On: | 29 Nov 2010 17:27 |

Last Modified: | 14 Dec 2013 18:37 |

Publisher: | Cambridge University Press |

ISSN: | 0963-5483 |

Additional Information: | Copyright: Cambridge University Press |

Publisher DOI: | 10.1017/S0963548399003806 |

Related URLs: | http://www.ams.org/mathscinet-getitem?mr=1731978 http://www.zentralblatt-math.org/zbmath/search/?q=an%3A0946.68111 |

Citations: | Web of Science®. Times Cited: 3 Google Scholar™ |

Users (please log in): suggest update or correction for this item

Repository Staff Only: item control page