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.

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
PDF BibTeX Cite
Full Text: DOI