Hostname: page-component-74656f9884-kv2lp Total loading time: 0 Render date: 2026-11-06T11:19:32.894Z Has data issue: false hasContentIssue false

Pattern Avoidance and Overlap in Strings

Published online by Cambridge University Press:  06 September 2002

MARIANNE MÅNSSON
Affiliation:
Department of Mathematics, Chalmers University of Technology, SE 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 patterns which consist of characters from Ω. For a given pattern w, let cor(w) denote its autocorrelation, which can be seen as a measure of the amount of overlap in w. Letting aw(n) denote the number of strings over Ω of length n which do not contain w as a substring, the main result of this paper is: If cor(w) > cor(w′) then aw(n)−aw′(n) > (|Ω|−1)(aw(n−1)−aw′(n−1)) for n [ges ] N, and the value of N is given. This result confirms a conjecture by Eriksson [2], which was previously proved to be true by Cakir, Chryssaphinou and Månsson [1] when |Ω| [ges ] 3.

Information

Type
Research Article
Copyright
2002 Cambridge University Press