Avoidability of long k-abelian repetitions

DOI10.1090/MCOM/3085MaRDI QIDQ5741503zbMATH OpenOpenAlexFDO

Authors Michaël Rao, Matthieu Rosenfeld

Publication date 25 July 2016

Published in Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

abelian repetition\(k\)-abelian equivalenceMäkelä conjecture

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We study the avoidability of long $k$-abelian-squares and $k$-abelian-cubes on binary and ternary alphabets. For $k=1$, these are M"akel"a's questions. We show that one cannot avoid abelian-cubes of abelian period at least $2$ in infinite binary words, and therefore answering negatively one question from M"akel"a. Then we show that one can avoid $3$-abelian-squares of period at least $3$ in infinite binary words and $2$-abelian-squares of period at least 2 in infinite ternary words. Finally we study the minimum number of distinct $k$-abelian-squares that must appear in an infinite binary word.

Recommendations

• Problems in between words and abelian words: \(k\)-abelian avoidability
• 3-abelian cubes are avoidable on binary alphabets
• On \(k\)-abelian avoidability
• 5-abelian cubes are avoidable on binary alphabets
• On some generalizations of abelian power avoidability

Cites work

• scientific article; zbMATH DE number 3162927 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 2051154 (Why is no real title available?)
• scientific article; zbMATH DE number 3296252 (Why is no real title available?)
• scientific article; zbMATH DE number 3375509 (Why is no real title available?)
• Abelian squares are avoidable on 4 letters
• How many squares must a binary sequence contain?
• ON ABELIAN POWER-FREE MORPHISMS
• On a generalization of abelian equivalence and complexity of infinite words
• On nonrepetitive sequences
• On some generalizations of abelian power avoidability
• On the number of Abelian square-free words on four letters
• Some unsolved problems
• Strongly non-repetitive sequences and progression-free sets

Cited in

(22)

• Abelian combinatorics on words: a survey
• Strongly \(k\)-abelian repetitions
• Avoiding or limiting regularities in words
• Local squares, periodicity and finite automata
• Improved bounds on the length of maximal abelian square-free words
• Avoiding two consecutive blocks of same size and same sum over \(\mathbb{Z}^2\)
• On k-abelian palindromes
• On the number of words containing the factor \((aba)^k\)
• A compactness property of the \(k\)-abelian monoids
• Maximum number of distinct and nonequivalent nonstandard squares in a word
• Regularity of k-Abelian Equivalence Classes of Fixed Cardinality
• Existence of an infinite ternary 64-abelian square-free word
• Problems in between words and abelian words: \(k\)-abelian avoidability
• \(k\)-abelian equivalence and rationality
• Crucial Words for Abelian Powers
• On some generalizations of abelian power avoidability
• On shortest crucial words avoiding abelian powers
• scientific article; zbMATH DE number 1943964 (Why is no real title available?)
• Avoiding abelian powers cyclically
• On growth and fluctuation of \(k\)-abelian complexity
• Abelian repetition threshold revisited
• Crucial abelian \(k\)-power-free words

This page was built for publication: Avoidability of long \(k\)-abelian repetitions

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