Forbidden substrings on weighted alphabets

2009/06/20 by Amy N. Myers, Myers, Amy N. · 1 citation
Mathematics · #05A #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A

paper · pdf · doi:10.48550/arxiv.0906.3763

8 pages

arxiv created 2009/06/20 · arxiv updated 2009/12/01

Abstract

In an influential 1981 paper, Guibas and Odlyzko constructed a generating function for the number of length n strings over a finite alphabet that avoid all members of a given set of forbidden substrings. Here we extend this result to the case in which the strings are weighted. This investigation was inspired by the problem of counting compositions of an integer n that avoid all compositions of a smaller integer m, a notion which arose from the consideration of one-sided random walks.

Cited by

• Volume Entropy Rigidity for Random Groups at Low Densities

Related

• Avoiding substrings in compositons
• Words restricted by patterns with at most 2 distinct letters
• Counting Lyndon Subsequences
• Two bijections for sets of words with forbidden factors
• Finite automata and pattern avoidance in words