String overlaps, pattern matching, and nontransitive games

L. J. Guibas, A. M. Odlyzko

Research output: Contribution to journalArticle

224 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)183-208
Number of pages26
JournalJournal of Combinatorial Theory, Series A
Volume30
Issue number2
DOIs
StatePublished - Mar 1981

    Fingerprint

Cite this