Automaticity of one-relator semigroups with length less than or equal to three

Abstract

The main results of this paper is to give a complete characterization of the automaticity of one-relator semigroups with length less than or equal to three. Let $S=sgp⟨A|u=v⟩$ be a semigroup generated by a set $A=\{a_1,a_2,\dots ,a_n\},n\in \mathbb{N}$ with defining relation $u=v$, where $u,v\in A^{\ast }$ and $A^{\ast }$ is the free monoid generated by $A$. Such a semigroup is called a one-relator semigroup. Suppose that $|v|\le |u|\le 3$, where $|u|$ is the length of the word $u$. Suppose that $a,b\in A,a\ne b$. Then we have the following: (1) $S$ is prefix-automatic if $u=v\notin \{aba=ba,aab=ba,abb=bb\}$. Moreover, if $u=v\in \{aba=ba,aab=ba,abb=bb\}$ then $S$ is not automatic. (2) $S$ is biautomatic if one of the following holds: (i) $|u|=3,|v|=0$, (ii) $|u|=|v|=3$, (iii) $|u|=2$ and $u=v\notin \{ab=a,ab=b\}$. Moreover, if $u=v\in \{ab=a,ab=b\}$ then $S$ is not biautomatic.

44 pages

References in corpus (1)

• Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids