Automatic Rees matrix semigroups over categories. (Q2373412)

Automatic structures allow efficiently to perform computations in finitely generated groups and semigroups, e.g., to solve the word problem using a finite automaton. Let \(A\) be a finite set of generators of a semigroup \(S\), \(\$\notin A\), \(A(2,\$)=\{(A\cup\$)\times(A\cup\$)\}\setminus\{\$\times\$\}\). Define the mapping \(\delta_A\colon A^+\times A^+\to A(2,\$)\) by \[ (a_1\dots a_n,b_1\dots b_m)\delta_A=\begin{cases} (a_1,b_1)\dots(a_n,b_n), &\text{if \(n=m\)}\\ (a_1,b_1)\dots(a_n,b_n)(\$,b_{n+1})\dots(\$,b_m), &\text{if \(n<m\)}\\ (a_1,b_1)\dots(a_m,b_m)(a_{m+1},\$)\dots(a_n,\$), &\text{if \(n>m\).}\end{cases} \] If \(L\subseteq A^+\) is a regular language such that \(\overline L=S\) and for each \(a\in A\cup\{\varepsilon\}\) the set \(L_a=\{(u,v):u,v\in L,\;\overline{ua}=\overline v\}\delta_A\) is a regular language, then the semigroup \(S\) is called automatic and the pair \((A,L)\) an automatic structure for \(S\) (for more details see, e.g., \textit{C. M. Campbell, E. F. Robertson, N. Ruškuc} and \textit{R. M. Thomas} [Theor. Comput. Sci. 250, No. 1-2, 365-391 (2001; Zbl 0987.20033)]). The author has earlier generalized this notion for small categories and semigroupoids [\textit{M. Kambites}, Theor. Comput. Sci. 353, No. 1-3, 272-290 (2006; Zbl 1095.20032)]. Here is considered automaticity and prefix-automaticity in Rees matrix semigroups over semigroupoids and small categories. It is proved, e.g., that a finitely generated Rees matrix semigroup over an automatic semigroupoid is always automatic and provided some sufficient conditions for the underlying semigroupoid of an automatic Rees matrix semigroup to be automatic; these results are generalizations of corresponding results for Rees matrix semigroups over semigroups proved by \textit{L. Descalço} and \textit{N. Ruškuc} [Commun. Algebra 30, No. 3, 1207-1226 (2002; Zbl 1012.20052)].