Hostname: page-component-7b9c58cd5d-hxdxx Total loading time: 0 Render date: 2025-03-15T04:39:59.419Z Has data issue: false hasContentIssue false
  • English
  • Français

On a Conjecture by Eriksson Concerning Overlap in Strings

Published online by Cambridge University Press:  01 September 1999

ISA CAKIR ,
OURANIA CHRYSSAPHINOU  and
MARIANNE MÅNSSON
ISA CAKIR
Affiliation:
Abteilung für Angewandte Mathematik, Universität Zürich-Irchel, Winterthurerstrasse 190, CH 8057 Zürich, Switzerland (e-mail: isa.cakir@winterthur.ch)
OURANIA CHRYSSAPHINOU
Affiliation:
Department of Mathematics, University of Athens, Panepistemiopolis, GR 157 84 Athens, Greece (e-mail ocrysaf@atlas.uoa.gr)
MARIANNE MÅNSSON
Affiliation:
Department of Mathematics, Chalmers University of Technology, S 412 96 Göteborg, Sweden (e-mail marianne@math.chalmers.se)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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′), thenaw(n)>aw′(n) from the first n where equality no longer holds. We prove that this is true if [mid ]Ω[mid ][ges ]3, by giving a lower bound for aw(n)−aw′(n).

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 8 , Issue 5 , September 1999 , pp. 429 - 440
Copyright
1999 Cambridge University Press