Mathematics – Combinatorics
Scientific paper
2009-07-27
Mathematics
Combinatorics
7 pages
Scientific paper
In combinatorics on words, a word w over an alphabet Sigma is said to avoid a pattern p over an alphabet Delta if there is no factor x of w and no non-erasing morphism h from Delta^* to Sigma^* such that h(p) = x. Bell and Goh have recently applied an algebraic technique due to Golod to show that for a certain wide class of patterns p there are exponentially many words of length n over a 4-letter alphabet that avoid p. We consider some further consequences of their work. In particular, we show that any pattern with k variables of length at least 4^k is avoidable on the binary alphabet. This improves an earlier bound due to Cassaigne and Roth.
No associations
LandOfFree
Further applications of a power series method for pattern avoidance does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Further applications of a power series method for pattern avoidance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Further applications of a power series method for pattern avoidance will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-246277