# zbMATH — the first resource for mathematics

On graph products of automatic and biautomatic monoids. (English) Zbl 1124.20040
Let $$A$$ be any non-empty finite set and $$A^*$$ denotes the set of all words over $$A$$ including the empty word $$\varepsilon$$. Let $$\emptyset\not\in A$$ be a symbol and $$A(2,\emptyset)=(A\cup\{\emptyset\})\times (A\cup\{\emptyset\})\setminus\{(\emptyset,\emptyset)\}$$. The convolution is defined as a special map $$\otimes\colon A^*\times A^*\to A(2,\emptyset)^*$$. Let $$M$$ be a monoid, $$A$$ a finite set, $$\theta_A\colon A^*\to M$$ a homomorphism, and $$L\subseteq A^*$$. Then $$(A,\theta_A,L)$$ is an ‘automatic structure’ for $$M$$ if $$L$$ and all the sets $$L_a=\{v\otimes w\mid v,w\in L$$, $$\theta_A(va)=\theta_A(w)\}\subseteq A(2,\emptyset)^*$$ for $$a\in A$$ are regular in $$A(2,\emptyset)^*$$ and if $$\theta_A$$ maps $$L$$ bijectively onto $$M$$. An automatic structure $$(A,\theta_A,L)$$ for $$M$$ is ‘biautomatic’ if, in addition, the sets $$_aL=\{v\otimes w\mid v,w\in L$$, $$\theta_A(av)=\theta_A(w)\}\subseteq A(2,\emptyset)^*$$ for $$a\in A$$ are regular. A monoid $$M$$ is ‘(bi)automatic’ if there is exists a (bi)automatic structure for $$M$$. Suppose that $$M_1,\dots,M_n$$ are monoids presented by $$(A_1,R_1),\dots,(A_n,R_n)$$ (we assume that the sets $$A_1,\dots,A_n$$ are mutually disjoint), $$[n]=\{1,\dots,n\}$$ and $$\Gamma=([n],E)$$ is an undirected and loop free graph. The ‘graph product’ $$\Gamma(M_1,\dots,M_n)$$ is the monoid presented by $$(A,R)$$, where $$A=\bigcup_{i\in [n]}A_i$$, $$R=\bigcup_{i\in[n]}R_i\cup\bigcup_{(i,j)\in E}\{ab=ba\mid a\in A_i$$, $$b\in A_j\}$$.
The main results of the paper are the following. The graph product $$\Gamma(M_1,\dots,M_n)$$ of monoids is always automatic thereby improving on a result by A. Veloso da Costa who showed this result provided the factors have finite geometric type [Theor. Inform. Appl. 35, No. 5, 403-417 (2001; Zbl 1019.20028) and Semigroup Forum 63, No. 2, 247-277 (2001; Zbl 0992.20042)]. Secondly, it is shown that, in general, the free product (and therefore the graph product) of biautomatic monoids need not be biautomatic. If for all $$i\in[n]$$, the monoid $$M_i$$ is biautomatic and the equation $$px=q$$ has only finitely many solutions for any $$p,q\in M_i$$, then the graph product $$\Gamma(M_1,\dots,M_n)$$ is biautomatic.

##### MSC:
 20M05 Free semigroups, generators and relations, word problems 20M35 Semigroups in automata theory, linguistics, etc. 68Q45 Formal languages and automata 68Q70 Algebraic theory of languages and automata
Full Text: