Avoiding large squares in infinite binary words
From MaRDI portal
(Redirected from Publication:557912)
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)- Infinite words containing the minimal number of repetitions
- New results on pseudosquare avoidance
- Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101
- Clusters of repetition roots: single chains
- A low-complexity LUT-based squaring algorithm
- Efficient big integer multiplication and squaring algorithms for cryptographic applications
- SIMULTANEOUS AVOIDANCE OF LARGE SQUARES AND FRACTIONAL POWERS IN INFINITE BINARY WORDS
- Chains and fixing blocks in irreducible binary sequences
- Avoiding large squares in partial words
- Inner palindromic closure
- Avoiding Approximate Squares
- On the number of frames in binary words
- Antisquares and critical exponents
- Square-free shuffles of words
- Avoiding squares and overlaps over the natural numbers
- Fewest repetitions versus maximal-exponent powers in infinite binary words
- On the aperiodic avoidability of binary patterns with variables and reversals
- A generalization of Thue freeness for partial words
- The simplest binary word with only three squares
- Infinite words containing squares at every position
- Words avoiding repetitions in arithmetic progressions
- Hairpin structures defined by DNA trajectories
- Cyclically repetition-free words on small alphabets
- Fewest repetitions in infinite binary words
- scientific article; zbMATH DE number 2051164 (Why is no real title available?)
- A generator of morphisms for infinite words
- Infinite binary words containing repetitions of odd period
- Cubefree words with many squares
- Avoiding letter patterns in ternary square-free words
- AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
- Characterization of some binary words with few 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)
