Words avoiding repetitions in arithmetic progressions

DOI10.1016/J.TCS.2007.10.039MaRDI QIDQ2474231zbMATH OpenOpenAlexFDO

Authors Jui-Yi Kao, Narad Rampersad, Manuel Silva, Jeffrey Shallit

Publication date 5 March 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0608607

zbMATH Keywords

arithmetic progressionpaperfolding wordrepetition

Mathematics Subject Classification ID

Arithmetic progressions (11B25) Combinatorics on words (68R15)

Abstract: Carpi constructed an infinite word over a 4-letter alphabet that avoids squares in all subsequences indexed by arithmetic progressions of odd difference. We show a connection between Carpi's construction and the paperfolding words. We extend Carpi's result by constructing uncountably many words that avoid squares in arithmetic progressions of odd difference. We also construct infinite words avoiding overlaps and infinite words avoiding arbitrarily large squares in arithmetic progressions of odd difference. We use these words to construct labelings of the 2-dimensional integer lattice such that any line through the lattice encounters a squarefree (resp. overlapfree) sequence of labels.

Recommendations

• On square-free arithmetic progressions in infinite words
• Some further results on squarefree arithmetic progressions in infinite words
• Avoiding large squares in infinite binary words
• Infinite words containing the minimal number of repetitions
• scientific article; zbMATH DE number 2051164

Cites work

• Canonical positions for the factors in paperfolding sequences
• Factors of generalized Rudin-Shapiro sequences
• Folds!
• scientific article; zbMATH DE number 3874638 (Why is no real title available?)
• scientific article; zbMATH DE number 3773704 (Why is no real title available?)
• Infinite 0-1 sequences without long adjacent identical blocks
• Multidimensional unrepetitive configurations
• Non-repetitive tilings
• On nonrepetitive sequences
• Reading along arithmetic progressions
• The number of factors in a paperfolding sequence
• Thue type problems for graphs, points, and numbers

Cited in

(10)

• A word on 7 letters which is non-repetitive up to mod 5
• On square-free arithmetic progressions in infinite words
• Repetitions in Toeplitz words and the Thue threshold
• Some further results on squarefree arithmetic progressions in infinite words
• Avoiding triples in arithmetic progression
• A new approach to the paperfolding sequences
• scientific article; zbMATH DE number 5557896 (Why is no real title available?)
• Avoiding Multiple Repetitions in Euclidean Spaces
• Absent Subsequences in Words
• Runs in paperfolding sequences

This page was built for publication: Words avoiding repetitions in arithmetic progressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2474231)