Pattern avoidance: themes and variations
From MaRDI portal
This is a nice short survey on words avoiding patterns in the sense of \textit{D. R. Bean}, \textit{A. Ehrenfeucht} and \textit{G. F. McNulty} [Pac. J. Math. 85, 261--294 (1979; Zbl 0428.05001]. The author formulates a number of interesting open problems and demonstrates a neat example of application of the probabilistic method (involving the Lovász local lemma). Reviewer's remark. In the bibliography, items [17] and [18] are identical while items [11], [31], [33], [52] are missing. Fortunately, this does not seem to lead to any serious confusion.
Recommendations
Cites work
- A linear-time algorithm to decide whether a binary word contains an overlap
- A propos d'une conjecture de F. Dejean sur les répétitions dans les mots
- Abelian squares are avoidable on 4 letters
- ALGORITHMIC PROBLEMS IN VARIETIES
- Arithmetic progressions in partially ordered sets
- Avoidable patterns in strings of symbols
- Avoiding patterns in the abelian sense
- BLOCKING SETS OF TERMS
- Characterization of the repetitive commutative semigroups
- Enumeration of irreducible binary words
- Growth problems for avoidable words
- scientific article; zbMATH DE number 992016 (Why is no real title available?)
- scientific article; zbMATH DE number 1809720 (Why is no real title available?)
- scientific article; zbMATH DE number 3162927 (Why is no real title available?)
- scientific article; zbMATH DE number 3904598 (Why is no real title available?)
- scientific article; zbMATH DE number 3972211 (Why is no real title available?)
- scientific article; zbMATH DE number 3583296 (Why is no real title available?)
- scientific article; zbMATH DE number 1264511 (Why is no real title available?)
- scientific article; zbMATH DE number 512830 (Why is no real title available?)
- scientific article; zbMATH DE number 1948509 (Why is no real title available?)
- scientific article; zbMATH DE number 2000848 (Why is no real title available?)
- scientific article; zbMATH DE number 1919522 (Why is no real title available?)
- scientific article; zbMATH DE number 1361493 (Why is no real title available?)
- scientific article; zbMATH DE number 3894492 (Why is no real title available?)
- scientific article; zbMATH DE number 2188438 (Why is no real title available?)
- scientific article; zbMATH DE number 3375509 (Why is no real title available?)
- Improved bounds on the number of ternary square-free words
- Intervals in the lattice of varieties
- Multidimensional unrepetitive configurations
- New problems of pattern avoidance
- NON-REPETITIVE SEQUENCES ON THREE SYMBOLS
- Non-repetitive tilings
- Nonrepetitive colorings of graphs
- On Abelian squares and substitutions
- On cube-free \(\omega\)-words generated by binary morphisms
- On repetition-free binary words of minimal density
- ON REPRESENTATION SYSTEMS
- On the number of Abelian square-free words on four letters
- Overlap-free words and finite automata
- Polynomial versus exponential growth in repetition-free binary words
- Proof of Dejean's conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters
- Sharp characterizations of squarefree morphisms
- Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
- Strongly non-repetitive sequences and progression-free sets
- Sur un théorème de Thue
- The entropy of square-free words
- The Goulden—Jackson cluster method: extensions, applications and implementations
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- There are ternary circular square-free words of length \(n\) for \(n \geq\) 18
- Thue-like sequences and rainbow arithmetic progressions
- Uniformly growing k-th power-free homomorphisms
- Words strongly avoiding fractional powers
Cited in
(34)- A cyclic binary morphism avoiding abelian fourth powers
- The complexity of nonrepetitive coloring
- Unary patterns under permutations
- Pattern avoidance by palindromes
- Extremal square-free words
- On long words avoiding Zimin patterns
- How to play Thue games
- On a generalization of Thue sequences
- Cubic patterns with permutations
- Exponential lower bounds for the number of words of uniform length avoiding a pattern
- Searching for Zimin patterns
- On the facial Thue choice index via entropy compression
- Computing depths of patterns
- Facial non-repetitive edge-coloring of plane graphs
- Highly nonrepetitive sequences: winning strategies from the local Lemma
- Nonrepetitive list colourings of paths
- Unary patterns with permutations
- On the avoidability index of palindromes
- Thue choosability of trees
- Open Problems in Pattern Avoidance
- Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns
- Density dichotomy in random words
- New approach to nonrepetitive sequences
- Nonrepetitive colorings of line arrangements
- A Frameless 2-Coloring of the Plane Lattice
- Squarefree extensions of words
- Nonrepetitive colouring via entropy compression
- Pattern avoidance and dominating compositions
- Extensions and reductions of squarefree words
- A small morphism for which the fixed point has an abelian critical exponent less than 2
- Characterisations and examples of graph classes with bounded expansion
- Grasshopper avoidance of patterns
- Nonrepetitive colorings of graphs -- a survey
- Every real number greater than 1 is a critical exponent
This page was built for publication: Pattern avoidance: themes and variations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557911)
