Bounds on Zimin Word Avoidance
Autor: | Cooper, Joshua, Rorabaugh, Danny |
---|---|
Rok vydání: | 2014 |
Předmět: | |
Druh dokumentu: | Working Paper |
Popis: | How long can a word be that avoids the unavoidable? Word $W$ encounters word $V$ provided there is a homomorphism $\phi$ defined by mapping letters to nonempty words such that $\phi(V)$ is a subword of $W$. Otherwise, $W$ is said to avoid $V$. If, on any arbitrary finite alphabet, there are finitely many words that avoid $V$, then we say $V$ is unavoidable. Zimin (1982) proved that every unavoidable word is encountered by some word $Z_n$, defined by: $Z_1 = x_1$ and $Z_{n+1} = Z_n x_{n+1} Z_n$. Here we explore bounds on how long words can be and still avoid the unavoidable Zimin words. Comment: 9 pages; presented 4 March 2014 at the 45th Southeastern International Conference on Combinatorics, Graph Theory, and Computing at Florida Atlantic University; accepted to appear in Congressus Numerantum |
Databáze: | arXiv |
Externí odkaz: |