Complement Avoidance in Binary Words

2022/09/20 by James D. Currie, Currie, James, Pascal Ochem +7 · 1 citation
Computer Science · #semigroups and automata theory #Computability, Logic, AI Algorithms #Advanced Algebra and Logic

paper · pdf · doi:10.48550/arxiv.2209.09598

Abstract

The complement x of a binary word x is obtained by changing each 0 in x to 1 and vice versa. We study infinite binary words \bf w that avoid sufficiently large complementary factors; that is, if x is a factor of \bf w then x is not a factor of \bf w. In particular, we classify such words according to their critical exponents.

Cited by

• Critical exponent of ternary words with few distinct palindromes

Related

• For each α > 2 there is an infinite binary word with critical exponent α
• Low complexity binary words avoiding (5/2)⁺-powers
• New results on pseudosquare avoidance
• Critical exponent of binary words with few distinct palindromes
• Fewest repetitions in infinite binary words