Publication: On a conjecture by Eriksson concerning overlap in strings
On a conjecture by Eriksson concerning overlap in strings
Date
Date
Date
Citations
Cakir, I., Chryssaphinou, O., & Månsson, M. (1999). On a conjecture by Eriksson concerning overlap in strings. Combinatorics, Probability & Computing, 8(5), 429–440. https://doi.org/10.1017/S0963548399003806
Abstract
Abstract
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).
Metrics
Downloads
Views
Additional indexing
Creators (Authors)
- Cakir, I
- Chryssaphinou, O
- Månsson, M
Journal/Series Title
Journal/Series Title
Journal/Series Title
Volume
Volume
Volume
Number
Number
Number
Page range/Item number
Page range/Item number
Page range/Item number
Page end
Page end
Page end
Item Type
Item Type
Item Type
In collections
Language
Language
Language
Publication date
Publication date
Publication date
Date available
Date available
Date available
ISSN or e-ISSN
ISSN or e-ISSN
ISSN or e-ISSN
Additional Information
Additional Information
Additional Information
OA Status
OA Status
OA Status
Publisher DOI
Related URLs
Related URLs
Related URLs
Metrics
Downloads
Views
Citations
Cakir, I., Chryssaphinou, O., & Månsson, M. (1999). On a conjecture by Eriksson concerning overlap in strings. Combinatorics, Probability & Computing, 8(5), 429–440. https://doi.org/10.1017/S0963548399003806
