### 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 language | English (US) |
---|---|

Pages (from-to) | 183-208 |

Number of pages | 26 |

Journal | Journal of Combinatorial Theory, Series A |

Volume | 30 |

Issue number | 2 |

DOIs | |

State | Published - Mar 1981 |

### Fingerprint

### Cite this

*Journal of Combinatorial Theory, Series A*,

*30*(2), 183-208. https://doi.org/10.1016/0097-3165(81)90005-4