Avoidable patterns in strings of symbols

DOI10.2140/pjm.1979.85.261zbMath0428.05001OpenAlexW2086965829MaRDI QIDQ1137038

Dwight R. Bean, George F. McNulty, Andrzej Ehrenfeucht

Publication date: 1979

Published in: Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2140/pjm.1979.85.261

zbMATH Keywords

free semigroups infinite words circular words finite alphabet formal linguistics linguistics avoidable Burnside problem for semigroups finite string of letters kth power-free n-dimensional arrays partitioned linear orders

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Enumerative combinatorics (05A99)

Related Items

On the aperiodic avoidability of binary patterns with variables and reversals ⋮ Non-repetitive colorings of infinite sets ⋮ Repetition-free words ⋮ Initial non-repetitive complexity of infinite words ⋮ Applications of an infinite square-free co-CFL ⋮ On the facial Thue choice number of plane graphs via entropy compression method ⋮ On the structure and extendibility of \(k\)-power free words ⋮ Long binary patterns are abelian 2-avoidable ⋮ On the entropy and letter frequencies of powerfree words ⋮ Doubled patterns are 3-avoidable ⋮ Exponential lower bounds for the number of words of uniform length avoiding a pattern ⋮ Existence of finite test-sets for \(k\)-power-freeness of uniform morphisms ⋮ Long unavoidable patterns ⋮ Which graphs allow infinite nonrepetitive walks? ⋮ Multidimensional unrepetitive configurations ⋮ The complexity of unavoidable word patterns ⋮ Nonrepetitive colorings of trees ⋮ On the avoidability index of palindromes ⋮ Avoidable patterns on two letters ⋮ Non-repetitive words: Ages and essences ⋮ On the Facial Thue Choice Index via Entropy Compression ⋮ On the generation of powers by OS schemes ⋮ The origins of combinatorics on words ⋮ Crucial words and the complexity of some extremal problems for sets of prohibited words ⋮ Sequence avoiding any complete word ⋮ On abelian 2-avoidable binary patterns ⋮ Pattern avoidance on graphs ⋮ Some results in square-free and strong square-free edge-colorings of graphs ⋮ On the number of Abelian square-free words on four letters ⋮ String cadences ⋮ Power semigroups of finite groups and the INFB property. ⋮ Avoidability of formulas with two variables ⋮ Binary words avoided by the Thue-Morse sequence ⋮ Inventories of unavoidable languages and the word-extension conjecture ⋮ Infinite 0-1 sequences without long adjacent identical blocks ⋮ Computing the partial word avoidability indices of binary patterns ⋮ Computing the partial word avoidability indices of ternary patterns ⋮ Computing Depths of Patterns ⋮ Application of entropy compression in pattern avoidance ⋮ On the algorithmic decidability of the square-free word problem relative to a system of two defining relations ⋮ Thue choosability of trees ⋮ Growth problems for avoidable words ⋮ Sharp characterizations of squarefree morphisms ⋮ Structural diversity in the lattice of equational theories ⋮ Growth, unavoidable words, and M. Sapir's conjecture for semigroup varieties. ⋮ Permutations are not context-free: An application of the interchange lemma ⋮ On the atoms of algebraic lattices arising in 𝔮-theory ⋮ Nonrepetitive colorings of graphs -- a survey ⋮ Avoidability of palindrome patterns ⋮ Words strongly avoiding fractional powers ⋮ Thue type problems for graphs, points, and numbers ⋮ Square-free shuffles of words ⋮ Every binary pattern of length six is avoidable on the two-letter alphabet ⋮ Pattern systems ⋮ A new solution for Thue's problem ⋮ Multi-pattern languages ⋮ 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 ⋮ Breaking the rhythm on graphs ⋮ CONJECTURES AND RESULTS ON MORPHISMS GENERATING k-POWER-FREE WORDS ⋮ There are \(k\)-uniform cubefree binary morphisms for all \(k \geq 0\) ⋮ The entropy of square-free words ⋮ Patterns in words and languages ⋮ Formulas with reversal ⋮ Chains and fixing blocks in irreducible binary sequences ⋮ Pattern avoidance: themes and variations ⋮ On identities of finite involution semigroups. ⋮ Pattern avoidance by palindromes ⋮ Grasshopper avoidance of patterns ⋮ Nonrepetitive list colorings of the integers ⋮ Searching for Zimin patterns ⋮ A generalization of Thue freeness for partial words ⋮ Avoidability of Formulas with Two Variables ⋮ Extremal square-free words ⋮ Syntactic semigroups of avoided languages ⋮ The ascending varietal chain of a variety of semigroups ⋮ Cyclically repetition-free words on small alphabets ⋮ Avoidable binary patterns in partial words ⋮ Detecting leftmost maximal periodicities ⋮ On long words avoiding Zimin patterns ⋮ On cube-free \(\omega\)-words generated by binary morphisms ⋮ An optimal test on finite unavoidable sets of words ⋮ On repetition-free binary words of minimal density ⋮ Uniformly growing k-th power-free homomorphisms ⋮ On the size of a square-free morphism on a three letter alphabet ⋮ Repetitive perhaps, but certainly not boring ⋮ On the size of the alphabet and the subword complexity of square-free DOL languages ⋮ Some non finitely generated monoids of repetition-free endomorphisms. ⋮ Infinite arrays and controlled deterministic table 0L array systems ⋮ On the product of square-free words ⋮ On the centers of the set of weakly square-free words on a two letter alphabet ⋮ On regularity of languages generated by copying systems ⋮ A characterization of power-free morphisms ⋮ Many aspects of formal languages ⋮ Unsolvability of problems of equality and divisibility in certain varieties of semigroups ⋮ Some results on \(k\)-power-free morphisms ⋮ Avoidability index for binary patterns with reversal ⋮ Unavoidable binary patterns ⋮ A non-learnable class of E-pattern languages ⋮ On the Tree of Ternary Square-Free Words ⋮ Anagram-Free Colourings of Graphs ⋮ Lengths of extremal square-free ternary words. ⋮ Undecidability of the identity problem for finite semigroups ⋮ Abelian combinatorics on words: a survey ⋮ Unavoidable regularities and factor permutations of words ⋮ Unavoidable languages, cuts and innocent sets of words ⋮ The lengths for which bicrucial square-free permutations exist ⋮ A tight upper bound on the length of maximal bordered box repetition-free words ⋮ Extensions and reductions of squarefree words ⋮ From Bi-ideals to Periodicity ⋮ Avoiding or Limiting Regularities in Words ⋮ Inclusion is undecidable for pattern languages ⋮ Unnamed Item ⋮ Avoiding conjugacy classes on the 5-letter alphabet ⋮ Finite degrees of ambiguity in pattern languages ⋮ On avoidability of formulas with reversal ⋮ A uniform cube-free morphism isk-power-free for all integersk≥ 4 ⋮ New approach to nonrepetitive sequences ⋮ Unnamed Item ⋮ ALGORITHMIC COMBINATORICS ON PARTIAL WORDS ⋮ Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries ⋮ Partially abelian squarefree words ⋮ On combinatorial properties of the Arshon sequence ⋮ Highly nonrepetitive sequences: Winning strategies from the local lemma ⋮ Nonrepetitive list colourings of paths ⋮ Avoiding Multiple Repetitions in Euclidean Spaces ⋮ Splitting necklaces and measurable colorings of the real line ⋮ TYPES OF GROWTH AND IDENTITIES OF SEMIGROUPS ⋮ Square-free extensions of words ⋮ THE EXISTENCE OF A PATTERN WHICH IS 5-AVOIDABLE BUT 4-UNAVOIDABLE ⋮ Nonrepetitive colorings of graphs ⋮ Density dichotomy in random words ⋮ Tower-type bounds for unavoidable patterns in words ⋮ A generator of morphisms for infinite words ⋮ A Frameless 2-Coloring of the Plane Lattice