Growth problems for avoidable words (Q908709): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: New estimates of odd exponents of infinite Burnside groups. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5767794 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Avoidable patterns in strings of symbols / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3941433 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5331549 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Uniformly growing k-th power-free homomorphisms / rank
 
Normal rank
Property / cites work
 
Property / cites work: NON-REPETITIVE SEQUENCES ON THREE SYMBOLS / rank
 
Normal rank
Property / cites work
 
Property / cites work: Embedding the dual of \(\Pi^\infty\) in the lattice of equational classes of semigroups. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3343936 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Sequence Without Repeats on x, x -1 , y, y -1 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ergodic theory on compact spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5508167 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Intervals in the lattice of varieties / rank
 
Normal rank
Property / cites work
 
Property / cites work: Repetition-free words / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4529547 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3751631 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3755660 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Unending chess, symbolic dynamics and a problem in semi-groups / rank
 
Normal rank
Property / cites work
 
Property / cites work: INFINITE PERIODIC GROUPS. I / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3948608 / rank
 
Normal rank
Property / cites work
 
Property / cites work: INHERENTLY NONFINITELY BASED FINITE SEMIGROUPS / rank
 
Normal rank
Property / cites work
 
Property / cites work: Avoidable patterns on two letters / rank
 
Normal rank
Property / cites work
 
Property / cites work: Aperiodic words on three symbols. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5186754 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Aperiodic words on three symbols. II. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3919722 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3765976 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finite basis theorem for systems of semigroup identities / rank
 
Normal rank
Property / cites work
 
Property / cites work: BLOCKING SETS OF TERMS / rank
 
Normal rank

Latest revision as of 12:19, 20 June 2024

scientific article
Language Label Description Also known as
English
Growth problems for avoidable words
scientific article

    Statements

    Growth problems for avoidable words (English)
    0 references
    0 references
    0 references
    0 references
    1989
    0 references
    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.
    0 references
    avoidable words
    0 references

    Identifiers