Name
Abstract | ||
|---|---|---|
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 f of w such that f = h(p) where h : Delta* -> Sigma* is a non-erasing morphism. A pattern p is said to be k-avoidable if there exists an infinite word over a k-letter alphabet that avoids p. We give a positive answer to Problem 3.3.2 in Lothaire's book "Algebraic combinatorics on words", that is, every pattern with k variables of length at least 2(k) (resp. 3 x 2(k-1)) is 3-avoidable (resp. 2-avoidable). This conjecture was first stated by Cassaigne in his thesis in 1994. This improves previous bounds due to Bell and Goh, and Rampersad. |
Year | Venue | Keywords |
|---|---|---|
2013 | ELECTRONIC JOURNAL OF COMBINATORICS | Word,Pattern avoidance |
DocType | Volume | Issue |
Journal | 21.0 | 2.0 |
ISSN | Citations | PageRank |
1077-8926 | 9 | 0.76 |
References | Authors | |
7 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pascal Ochem | 1 | 258 | 36.91 |
| Alexandre Pinlou | 2 | 167 | 20.47 |