Avoidable patterns in strings of symbols
From MaRDI portal
Publication:1137038
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
free semigroupsinfinite wordscircular wordsfinite alphabetformal linguisticslinguisticsavoidableBurnside problem for semigroupsfinite string of letterskth power-freen-dimensional arrayspartitioned linear orders
Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Enumerative combinatorics (05A99)
Related Items (only showing first 100 items - show all)
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 ⋮ Power-free complementary binary morphisms ⋮ Avoiding Multiple Repetitions in Euclidean Spaces ⋮ Splitting necklaces and measurable colorings of the real line ⋮ The lexicographically least binary rich word achieving the repetition threshold ⋮ 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 ⋮ 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\)
This page was built for publication: Avoidable patterns in strings of symbols
