Permanent URL to this publication: http://dx.doi.org/10.5167/uzh22128
Cakir, I; Chryssaphinou, O; Månsson, M (1999). On a conjecture by Eriksson concerning overlap in strings. Combinatorics, Probability & Computing, 8(5):429440.

PDF
188kB View at publisher 
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:][gtorequal, slanted]3, by giving a lower bound for aw(n)−aw′(n).
Citations  Altmetrics  Downloads 
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:  09635483 
Additional Information:  Copyright: Cambridge University Press 
Publisher DOI:  10.1017/S0963548399003806 
Related URLs:  http://www.ams.org/mathscinetgetitem?mr=1731978 http://www.zentralblattmath.org/zbmath/search/?q=an%3A0946.68111 
Users (please log in): suggest update or correction for this item
Repository Staff Only: item control page