Autocorrelation and the Enumeration of Strings Avoiding a Fixed String

Source abstract

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 a w ( 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 a w ( n ) > a w ′ ( n ) for all large enough n .