The simplest binary word with only three squares

DOI10.1051/ITA/2021001MaRDI QIDQ5021107zbMATH OpenOpenAlexFDO

Authors Daniel Gabric, Jeffrey Shallit

Publication date 12 January 2022

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

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

zbMATH Keywords

automatic wordsquare-free wordThue-Morse word

Mathematics Subject Classification ID

Automata sequences (11B85) Combinatorics on words (68R15) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Abstract: We re-examine previous constructions of infinite binary words containing few distinct squares with the goal of finding the "simplest", in a certain sense. We exhibit several new constructions. Rather than using tedious case-based arguments to prove that the constructions have the desired property, we rely instead on theorem-proving software for their correctness.

Recommendations

• Squares in binary partial words
• Characterization of some binary words with few squares
• The number of positions starting a square in binary words
• The three-squares lemma for partial words with one hole
• Counting ternary square-free words quickly
• A note on the number of squares in a word
• BINARY PATTERNS IN BINARY WORDS
• Words with simple Burrows-Wheeler transforms
• Existence of words over three-letter alphabet not containing squares with replacement errors
• Recognizing 3-collapsing words over a binary alphabet

Cites work

• A generator of morphisms for infinite words
• Abelian complexity of fixed point of morphism 0 012, 1 02, 2 1
• Avoiding large squares in infinite binary words
• Enumeration and decidable properties of automatic sequences
• Fewest repetitions in infinite binary words
• How many squares must a binary sequence contain?
• scientific article; zbMATH DE number 5605093 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3668011 (Why is no real title available?)
• Infinite words containing the minimal number of repetitions
• On nonrepetitive sequences
• Uniform tag sequences

Cited in

(3)

• How many square occurrences must a binary sequence contain?
• More characterizations of morphic words
• Words avoiding the morphic images of most of their factors

Describes a project that uses

Uses Software

• Walnut

This page was built for publication: The simplest binary word with only three squares

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