Quasi-automatic semigroups (Q2422022)

Several notions of automaticity have been proposed for semigroups. The paper presents a new such version which enjoys some nice properties. The key idea is to consider rational relations rather than rational languages. More precisely, a finitely generated semigroup $S$ admits a quasi-automatic structure $\langle A,\mu,L,R,(R_a)_{a\in A}\rangle$ if $A$ is a finite set, $\mu:A^+\to S$ is an onto homomorphism, $L\subseteq A^+$ is a rational language, and $R,R_a\subseteq A^+\times A^+$ are rational relations such that: \begin{itemize} \item[(1)] $\mu(L)=S$; \item[(2)] $R=\{(u,v)\in L\times L: \mu(u)=\mu(v)\}$; \item[(3)] for each $a\in A$, $R_a=\{(u,v)\in L\times L: \mu(ua)=\mu(v)\}$. \end{itemize} A similar notion may be considered for monoids but it turns out that a monoid is quasi-automatic as a monoid if and only if it is quasi-automatic as a semigroup. It is observed in the paper that the class of quasi-automatic semigroups is strictly larger than the class of rational semigroups of \textit{J. Sakarovitch} [Inf. Comput. 74, 173--197 (1987; Zbl 0642.20043)] and also than the class of synchronous automatic semigroups as considered by \textit{C. M. Campbell} et. al. [Theor. Comput. Sci. 250, No. 1--2, 365--391 (2001; Zbl 0987.20033)]; for the asynchronous version of automaticity for semigroups, it is only shown that such semigroups are quasi-automatic. Among others, the following theorems are established: \begin{itemize} \item[(a)] unlike automaticity, quasi-automaticity does not depend on the generating set; \item[(b)] for a semigroup with a quasi-automatic structure $\langle A,\mu,L,R,(R_a)_{a\in A}\rangle$, one may compute in exponential time with respect to the length of a given word $u$, a word $v\in L$ such that $\mu(u)=\mu(v)$; \item[(c)] a quasi-automatic semigroup admits a (rational) presentation for which the word problem is decidable in exponential time; \item[(d)] a semigroup with a quasi-automatic structure $\langle A,\mu,L,R,(R_a)_{a\in A}\rangle$ satisfies a weak form of the fellow traveler property called weak Lipschitz property; \item[(e)] graded quasi-automatic semigroups are automatic; \item[(f)] quasi-automatic groups are finitely presented with an exponential isoperimetric inequality and they are characterized by the weak Lipschitz property. \end{itemize} The paper concludes with several open problems.