Aseem Baranwal ; James Currie ; Lucas Mol ; Pascal Ochem ; Narad Rampersad et al. - Antisquares and Critical Exponents

dmtcs:10063 - Discrete Mathematics & Theoretical Computer Science, September 6, 2023, vol. 25:2 - https://doi.org/10.46298/dmtcs.10063
Antisquares and Critical ExponentsArticle

Authors: Aseem Baranwal ; James Currie ; Lucas Mol ; Pascal Ochem ; Narad Rampersad ; Jeffrey Shallit

    The (bitwise) complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. An $\textit{antisquare}$ is a nonempty word of the form $x\, \overline{x}$. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is $(5+\sqrt{5})/2$. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number. We say a binary word is $\textit{good}$ if the only antisquares it contains are $01$ and $10$. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length $n$ and determine the repetition threshold between polynomial and exponential growth for the number of good words.


    Volume: vol. 25:2
    Section: Combinatorics
    Published on: September 6, 2023
    Accepted on: August 2, 2023
    Submitted on: September 20, 2022
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,Computer Science - Formal Languages and Automata Theory
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Classifications

    Mathematics Subject Classification 20201

    Consultation statistics

    This page has been seen 792 times.
    This article's PDF has been downloaded 433 times.