Avoiding large squares in infinite binary words
From MaRDI portal
Publication:557912
DOI10.1016/J.TCS.2005.01.005zbMATH Open1099.68080arXivmath/0306081OpenAlexW2086666778MaRDI QIDQ557912FDOQ557912
Authors: Narad Rampersad, Jeffrey Shallit, Ming-wei Wang 
Publication date: 30 June 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/math/0306081
Recommendations
Cites Work
- How many squares must a binary sequence contain?
- Automatic Sequences
- Title not available (Why is that?)
- Infinite 0-1 sequences without long adjacent identical blocks
- The Goulden—Jackson cluster method: extensions, applications and implementations
- On nonrepetitive sequences
- Polynomial versus exponential growth in repetition-free binary words
- On repetitions of blocks in binary sequences
Cited In (31)
- New results on pseudosquare avoidance
- Infinite words containing the minimal number of repetitions
- 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
- SIMULTANEOUS AVOIDANCE OF LARGE SQUARES AND FRACTIONAL POWERS IN INFINITE BINARY WORDS
- Efficient big integer multiplication and squaring algorithms for cryptographic applications
- 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
- The simplest binary word with only three squares
- A generalization of Thue freeness for partial words
- Infinite words containing squares at every position
- Words avoiding repetitions in arithmetic progressions
- Hairpin structures defined by DNA trajectories
- Fewest repetitions in infinite binary words
- Cyclically repetition-free words on small alphabets
- Title not available (Why is that?)
- 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)
