zbMATH — the first resource for mathematics

Graph products of monoids. (English) Zbl 0992.20042
Let \(M_1,\dots,M_n\) be monoids and let \(\Gamma\) be a graph without loops whose vertices are labeled by \(M_i\). If \(\langle X_i;\;R_i\rangle\) is a presentation of the monoid \(M_i\), \(1\leq i\leq n\), then the associated graph product is the monoid whose presentation is \(\langle\bigcup\{X_i:1\leq i\leq n\};\;R\rangle\), where \(R=S\cup\bigcup\{R_i:1\leq i\leq n\}\) and \(S=\{(ab,ba):a\in X_i,\;b\in X_j,\;(M_i,M_j)\in E(\Gamma)\}\). The author characterizes the Green relations for graph products of monoids. The author gives a new proof for the word problem for graph products and describes the idempotent, regular, completely regular and invertible elements of graph products of monoids. The algorithms are reductions to the monoids \(M_i\), \(1\leq i\leq n\). We quote here Theorem: Let \(M\) be the graph product of the monoids \(M_1,M_2,\dots,M_n\) associated to a graph \(\Gamma\). Then \(M\) has decidable word problem iff for every \(i\), \(M_i\) has decidable word problem. The author proves similar theorems on the decidability of Green’s relations for graph products of monoids.

20M05 Free semigroups, generators and relations, word problems
68R15 Combinatorics on words
20M10 General structure theory for semigroups
PDF BibTeX Cite
Full Text: DOI