Avoiding large squares in infinite binary words
From MaRDI portal
Abstract: We consider three aspects of avoiding large squares in infinite binary words. First, we construct an infinite binary word avoiding both cubes xxx and squares yy with |y| >= 4; our construction is somewhat simpler than the original construction of Dekking. Second, we construct an infinite binary word avoiding all squares except 00, 11, and 0101; our construction is somewhat simpler than the original construction of Fraenkel and Simpson. In both cases, we also show how to modify our construction to obtain exponentially many words of length n with the given avoidance properties. Finally, we answer an open question of Prodinger and Urbanek from 1979 by demonstrating the existence of two infinite binary words, each avoiding arbitrarily large squares, such that their perfect shuffle has arbitrarily large squares.
Recommendations
Cites work
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- Automatic Sequences
- How many squares must a binary sequence contain?
- Infinite 0-1 sequences without long adjacent identical blocks
- On nonrepetitive sequences
- On repetitions of blocks in binary sequences
- Polynomial versus exponential growth in repetition-free binary words
- The Goulden—Jackson cluster method: extensions, applications and implementations
Cited in
(31)- New results on pseudosquare avoidance
- Chains and fixing blocks in irreducible binary sequences
- Inner palindromic closure
- Clusters of repetition roots: single chains
- Avoiding large squares in partial words
- Cyclically repetition-free words on small alphabets
- A generalization of Thue freeness for partial words
- AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
- Avoiding Approximate Squares
- Words avoiding repetitions in arithmetic progressions
- Infinite words containing the minimal number of repetitions
- Fewest repetitions versus maximal-exponent powers in infinite binary words
- Square-free shuffles of words
- Infinite words containing squares at every position
- A generator of morphisms for infinite words
- Avoiding squares and overlaps over the natural numbers
- Hairpin structures defined by DNA trajectories
- Avoiding letter patterns in ternary square-free words
- Characterization of some binary words with few squares
- Cubefree words with many squares
- On the number of frames in binary words
- A low-complexity LUT-based squaring algorithm
- Antisquares and critical exponents
- scientific article; zbMATH DE number 2051164 (Why is no real title available?)
- SIMULTANEOUS AVOIDANCE OF LARGE SQUARES AND FRACTIONAL POWERS IN INFINITE BINARY WORDS
- Efficient big integer multiplication and squaring algorithms for cryptographic applications
- On the aperiodic avoidability of binary patterns with variables and reversals
- Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101
- Fewest repetitions in infinite binary words
- Infinite binary words containing repetitions of odd period
- The simplest binary word with only three squares
This page was built for publication: Avoiding large squares in infinite binary words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557912)
