Finite derivation type for semigroups and congruences. (Q2461620)

A semigroup presentation is a pair \((X,\mathbf r)\) with \(\mathbf r\subseteq X^+\times X^+\). A semigroup presentation \(S\) is defined by the presentation \((X,\mathbf r)\) if it is isomorphic to the quotient of the free semigroup \(X^+\) by the smallest congruence generated by \(\mathbf r\). We have a graph \(\Gamma=\Gamma(X,\mathbf r)\) associated with \((X,\mathbf r)\), where the vertices are the elements of \(X^+\), and the edges are the 4-tuples \(e=(U,R,\varepsilon,V)\), where \(U,V\in X^*\), \(R=(R_{+1},R_{-1})\in\mathbf r)\), \(\varepsilon=\pm 1\). The initial, terminal and inversion functions for an edge \(e\) as above are given by \(i(e)=UR_\varepsilon V\), \(\tau(e)=UR_{-\varepsilon}V\) and \(e^{-1}=(U,R,-\varepsilon,V)\). There is a two-sided action of \(X^*\) on \(\Gamma\) as follows. If \(W,W'\in X^*\), then for any vertex \(V\) of \(\Gamma\), \(W\cdot V\cdot W'=WVW'\) (product in \(X^*\)), and for any edge \(e=(U,R,\varepsilon,V)\) of \(\Gamma\), \(W\cdot e\cdot W'=(WU,R,\varepsilon,VW')\). This action can be extended to the paths in \(\Gamma\). Let \(P(\Gamma)\) denote the set of all paths in \(\Gamma\), and let \(P^{(2)}(\Gamma)=\{(p,q)\mid p,q\in P(\Gamma)\), \(i(p)=i(q)\), \(\tau(p)=\tau(q)\}\). An equivalence relation \(\cong\) on \(P^{(2)}\) is called a homotopy relation if it satisfies the following conditions: (a) if \(e_1,e_2\) are edges of \(\Gamma\), then \((e_1\cdot i(e_2))(\tau(e_1)\cdot e_2)\cong (i(e_1)\cdot e_2)(e_1\cdot\tau(e_2))\); (b) if \(p\cong q\) and \(p,q\in P(\Gamma)\), then \(U\cdot p\cdot V\cong U\cdot q\cdot V\) for all \(U,V\in X^+\); (c) if \(p,q_1,q_2,r\in P(\Gamma)\), satisfy \(\tau(p)=i(q_1)=i(q_2)\), \(\tau(q_1)=\tau(q_2)=i(r)\), and \(q_1\cong q_2\), then \(pq_2r\cong pq_2r\); (d) if \(p\in P(\Gamma)\), then \(pp^{-1}\cong 1_{i(p)}\). Let \((X,\mathbf r)\) be a finite semigroup presentation and \(P(\Gamma)\) be the associated graph. We say that \((X,\mathbf r)\) has finite derivation type (FDT) if there is a finite subset \(C\subseteq P^{(2)}(\Gamma)\) which generates \(P^{(2)}(\Gamma)\) as a homotopy relation. Let \(S\) be a semigroup and let \(\rho\) be a congruence on \(S\). If \(\rho\) has FDT as a subsemigroup of the direct product \(S\times S\), then \(S\) has FDT.