Automatic Rees matrix semigroups over categories.

Groupoids, semigroupoids, semigroups, groups (viewed as categories) (18B40) Groupoids (i.e. small categories in which all morphisms are isomorphisms) (20L05) Free semigroups, generators and relations, word problems (20M05) Connections of semigroups with homological algebra and category theory (20M50) Formal languages and automata (68Q45)

Abstract: We consider the preservation of the properties of automaticity and prefix-automaticity in Rees matrix semigroups over semigroupoids and small categories. Some of our results are new or improve upon existing results in the single-object case of Rees matrix semigroups over semigroups.

Review text

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)].

Recommendations

Cited in

(5)

This page was built for publication: Automatic Rees matrix semigroups over categories.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373412)