Antisquares and Critical Exponents
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...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-09-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/10063/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849387784213626880 |
|---|---|
| author | Aseem Baranwal James Currie Lucas Mol Pascal Ochem Narad Rampersad Jeffrey Shallit |
| author_facet | Aseem Baranwal James Currie Lucas Mol Pascal Ochem Narad Rampersad Jeffrey Shallit |
| author_sort | Aseem Baranwal |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-3d9f4a915cd44c29b73e8397b2fc2d26 |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-09-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-3d9f4a915cd44c29b73e8397b2fc2d262025-08-20T03:42:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-09-01vol. 25:2Combinatorics10.46298/dmtcs.1006310063Antisquares and Critical ExponentsAseem BaranwalJames CurrieLucas MolPascal OchemNarad RampersadJeffrey ShallitThe (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.http://dmtcs.episciences.org/10063/pdfmathematics - combinatoricscomputer science - discrete mathematicscomputer science - formal languages and automata theory |
| spellingShingle | Aseem Baranwal James Currie Lucas Mol Pascal Ochem Narad Rampersad Jeffrey Shallit Antisquares and Critical Exponents Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - discrete mathematics computer science - formal languages and automata theory |
| title | Antisquares and Critical Exponents |
| title_full | Antisquares and Critical Exponents |
| title_fullStr | Antisquares and Critical Exponents |
| title_full_unstemmed | Antisquares and Critical Exponents |
| title_short | Antisquares and Critical Exponents |
| title_sort | antisquares and critical exponents |
| topic | mathematics - combinatorics computer science - discrete mathematics computer science - formal languages and automata theory |
| url | http://dmtcs.episciences.org/10063/pdf |
| work_keys_str_mv | AT aseembaranwal antisquaresandcriticalexponents AT jamescurrie antisquaresandcriticalexponents AT lucasmol antisquaresandcriticalexponents AT pascalochem antisquaresandcriticalexponents AT naradrampersad antisquaresandcriticalexponents AT jeffreyshallit antisquaresandcriticalexponents |