A length bound for binary equality words

Commentationes mathematicae Universitatis Carolinae

Jana Hadravová¹ 

关键词: combinatorics on words;    binary equality languages;   

DOI  :  

学科分类：物理化学和理论化学

来源: Univerzita Karlova v Praze * Matematicko-Fyzikalni Fakulta / Charles University in Prague, Faculty of Mathematics and Physics

【 摘 要 】

Let $w$ be an equality word of two binary non-periodic morphisms $g,h \{a,b\}^* \to \Delta^*$ with unique overflows. It is known that if $w$ contains at least 25 occurrences of each of the letters $a$ and $b$, then it has to have one of the following special forms up to the exchange of the letters $a$ and $b$ either $w=(ab)^ia$, or $w=a^ib^j$ with $\operatorname{gcd} (i,j)=1$. We will generalize the result, justify this bound and prove that it can be lowered to nine occurrences of each of the letters $a$ and~$b$.

【 授权许可】

CC BY