Growth problems for avoidable words

DOI10.1016/0304-3975(89)90071-6zbMath0693.68039OpenAlexW2025237878MaRDI QIDQ908709

Kirby A. Baker, Walter Taylor, George F. McNulty

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90071-6

zbMATH Keywords

avoidable words

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Enumerative combinatorics (05A99)

Related Items (37)

On the structure and extendibility of \(k\)-power free words ⋮ On the entropy and letter frequencies of powerfree words ⋮ Doubled patterns are 3-avoidable ⋮ Avoidance bases for formulas with reversal ⋮ Non-repetitive words: Ages and essences ⋮ The number of binary words avoiding Abelian fourth powers grows exponentially ⋮ Pattern avoidance on graphs ⋮ Avoidability of formulas with two variables ⋮ Avoiding square-free words on free groups ⋮ The set of \(k\)-power free words over \(\Sigma\) is empty or perfect ⋮ Growth rate of binary words avoiding \(xxx^{R}\) ⋮ A family of formulas with reversal of high avoidability index ⋮ Doubled patterns with reversal and square-free doubled patterns ⋮ Avoiding or Limiting Regularities in Words ⋮ Growth, unavoidable words, and M. Sapir's conjecture for semigroup varieties. ⋮ Growth properties of power-free languages ⋮ Avoidability of palindrome patterns ⋮ Avoiding conjugacy classes on the 5-letter alphabet ⋮ On some interesting ternary formulas ⋮ Thue type problems for graphs, points, and numbers ⋮ Every binary pattern of length six is avoidable on the two-letter alphabet ⋮ Avoidability of circular formulas ⋮ Polynomial growth in semigroup varieties. ⋮ Some variations on a theme of Irina Mel'nichuk concerning the avoidability of patterns in strings of symbols ⋮ Relatively free semigroups of intermediate growth ⋮ The unambiguity of segmented morphisms ⋮ Formulas with reversal ⋮ Pattern avoidance: themes and variations ⋮ Binary words avoiding the pattern AABBCABBA ⋮ A cyclic binary morphism avoiding abelian fourth powers ⋮ Avoidability of Formulas with Two Variables ⋮ THE EXISTENCE OF A PATTERN WHICH IS 5-AVOIDABLE BUT 4-UNAVOIDABLE ⋮ Density dichotomy in random words ⋮ On repetition-free binary words of minimal density ⋮ A generator of morphisms for infinite words ⋮ Characterization of some binary words with few squares ⋮ Unavoidable binary patterns

Cites Work

• New estimates of odd exponents of infinite Burnside groups.
• Finite basis theorem for systems of semigroup identities
• Repetition-free words
• Avoidable patterns on two letters
• Avoidable patterns in strings of symbols
• Ergodic theory on compact spaces
• Intervals in the lattice of varieties
• Uniformly growing k-th power-free homomorphisms
• Embedding the dual of \(\Pi^\infty\) in the lattice of equational classes of semigroups.
• Unending chess, symbolic dynamics and a problem in semi-groups
• NON-REPETITIVE SEQUENCES ON THREE SYMBOLS
• BLOCKING SETS OF TERMS
• INHERENTLY NONFINITELY BASED FINITE SEMIGROUPS
• Aperiodic words on three symbols.
• Aperiodic words on three symbols. II.
• A Sequence Without Repeats on x, x -1 , y, y -1
• INFINITE PERIODIC GROUPS. I
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Growth problems for avoidable words