Growth problems for avoidable words
type: Item
instance of: scholarly article
title: Growth problems for avoidable words
zbMATH Open document ID: 0693.68039
DOI: 10.1016/0304-3975(89)90071-6
author: Kirby A. Baker
author: Walter Taylor
author: George F. McNulty
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: A word w is said to avoid a word u if no subword of w is the homomorphic image of u. The word u is said to be avoidable on n letters if there are arbitrarily long words on an alphabet with n letters avoiding u. If u is avoidable on n letters for some n, let \(\mu\) (U) denote the minimum possible such n. It is proved that \(\mu\) (U) has a linear bound in terms the alphabet size of u and that there are 4-avoidable words which are not 3-avoidable. Such a word is \[ a b w b c x c a y b a z a c. \] The general case, of \((n+1)\)-avoidable words which are not n-avoidable, for \(n\geq 4\), remains open. Moreover, it is proved that if u is 4-avoidable and not 3-avoidable, then the number of words of length p on an \(\mu\) (U)-letter alphabet tha avoid u has a polynomial bound in terms of p. (In contrast, for xx this bound is known to be exponential.) Combinatorial, graph theory and topological instruments are involved in proofs; a list of open problems and a large bibliography end this beautiful paper.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 4135412
zbMATH Keywords: avoidable words
reviewed by: Gheorghe Păun
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90071-6
OpenAlex ID: W2025237878
cites work: New estimates of odd exponents of infinite Burnside groups.
cites work: Q5767794
cites work: Avoidable patterns in strings of symbols
cites work: Q3941433
cites work: Q5331549
cites work: Uniformly growing k-th power-free homomorphisms
cites work: NON-REPETITIVE SEQUENCES ON THREE SYMBOLS
cites work: Embedding the dual of \(\Pi^\infty\) in the lattice of equational classes of semigroups.
cites work: Q3343936
cites work: A Sequence Without Repeats on x, x -1 , y, y -1
cites work: Ergodic theory on compact spaces
cites work: Q5508167
cites work: Intervals in the lattice of varieties
cites work: Repetition-free words
cites work: Q4529547
cites work: Q3751631
cites work: Q3755660
cites work: Unending chess, symbolic dynamics and a problem in semi-groups
cites work: INFINITE PERIODIC GROUPS. I
cites work: Q3948608
cites work: INHERENTLY NONFINITELY BASED FINITE SEMIGROUPS
cites work: Avoidable patterns on two letters
cites work: Aperiodic words on three symbols.
cites work: Q5186754
cites work: Aperiodic words on three symbols. II.
cites work: Q3919722
cites work: Q3765976
cites work: Finite basis theorem for systems of semigroup identities
cites work: BLOCKING SETS OF TERMS
description: scientific article; zbMATH DE number 4135412