Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-08T15:26:52.663Z Has data issue: false hasContentIssue false

Autocorrelation and the Enumeration of Strings Avoiding a Fixed String

Published online by Cambridge University Press:  01 March 1997

KIMMO ERIKSSON
Affiliation:
Stockholm University, S-106 09 Stockholm, Sweden (e-mail: kimmo@nada.kth.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.

Considering strings over a finite alphabet [Ascr], say that a string is w-avoiding if it does not contain w as a substring. It is known that the number aw(n) of w-avoiding strings of length n depends only on the autocorrelation of w as defined by Guibas–Odlyzko. We give a simple criterion on the autocorrelations of w and w′ for determining whether aw(n) > aw′(n) for all large enough n.

Information

Type
Research Article
Copyright
1997 Cambridge University Press