Avoidability of long k-abelian repetitions

DOI10.1090/MCOM/3085zbMATH Open1359.68244arXiv1507.02581OpenAlexW2963924785MaRDI QIDQ5741503FDOQ5741503

Authors: Michaël Rao, Matthieu Rosenfeld 

Publication date: 25 July 2016

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

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• How many squares must a binary sequence contain?
• Title not available (Why is that?)
• Some unsolved problems
• Strongly non-repetitive sequences and progression-free sets
• Title not available (Why is that?)
• Abelian squares are avoidable on 4 letters
• Title not available (Why is that?)
• Title not available (Why is that?)
• On some generalizations of abelian power avoidability
• On a generalization of abelian equivalence and complexity of infinite words
• On nonrepetitive sequences
• Title not available (Why is that?)
• On the number of Abelian square-free words on four letters
• ON ABELIAN POWER-FREE MORPHISMS

Cited In (22)

• Strongly \(k\)-abelian repetitions
• Avoiding or limiting regularities in words
• Local squares, periodicity and finite automata
• Avoiding two consecutive blocks of same size and same sum over \(\mathbb{Z}^2\)
• Improved bounds on the length of maximal abelian square-free words
• On \(k\)-abelian palindromes
• On the number of words containing the factor \((aba)^k\)
• A compactness property of the \(k\)-abelian monoids
• Regularity of k-Abelian Equivalence Classes of Fixed Cardinality
• Maximum number of distinct and nonequivalent nonstandard squares in a word
• 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
• Title not available (Why is that?)
• Avoiding abelian powers cyclically
• On growth and fluctuation of \(k\)-abelian complexity
• Crucial abelian \(k\)-power-free words
• Abelian repetition threshold revisited
• Abelian combinatorics on words: a survey

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)