Title: String overlaps, pattern matching, and nontransitive games
Abstract: This paper studies several topics concerning the way strings can overlap. The key notion of the correlation of two strings is introduced, which is a representation of how the second string can overlap into the first. This notion is then used to state and prove a formula for the generating function that enumerates the q-ary strings of length n which contain none of a given finite set of patterns. Various generalizations of this basic result are also discussed. This formula is next used to study a wide variety of seemingly unrelated problems. The first application is to the nontransitive dominance relations arising out of a probabilistic coin-tossing game. Another application shows that no algorithm can check for the presence of a given pattern in a text without examining essentially all characters of the text in the worst case. Finally, a class of polynomials arising in connection with the main result are shown to be irreducible.
Publication Year: 1981
Publication Date: 1981-03-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 401
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot