UZH-Logo

Maintenance Infos

On a conjecture by Eriksson concerning overlap in strings


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

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

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

Citations

3 citations in Web of Science®
4 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

27 downloads since deposited on 29 Nov 2010
14 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:1999
Deposited On:29 Nov 2010 16:27
Last Modified:05 Apr 2016 13:26
Publisher:Cambridge University Press
ISSN:0963-5483
Additional Information:Copyright: Cambridge University Press
Publisher DOI:https://doi.org/10.1017/S0963548399003806
Related URLs:http://www.ams.org/mathscinet-getitem?mr=1731978
http://www.zentralblatt-math.org/zbmath/search/?q=an%3A0946.68111
Permanent URL: https://doi.org/10.5167/uzh-22128

Download

[img]
Preview
Filetype: PDF
Size: 188kB
View at publisher

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations