On graph products of automatic and biautomatic monoids. (Q2502268): Difference between revisions

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 \textit{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.