The homomorphism problem for trace monoids. (Q1426045)

The free monoid on an alphabet \(X\) is denoted by \(X^*\). A congruence \(\tau\) on \(X^*\) is called a dependency relation on \(X^*\) if \(\tau\) is generated by a subset of \(\{(xy,yx)\mid x,y\in X\}\). In such case, \((X,\tau)\) is called a dependency alphabet. The monoid \(X^*/\tau\) is called the trace monoid defined by the dependency alphabet \((X,\tau)\) and is denoted by \(M(X,\tau)\). In this paper, the author proves the nontrivial homomorphism problem for trace monoids, that is, for any given finite subset \(F\) of \(X^*\), dependency alphabet \((Y,\tau)\), and mapping \(\varphi\colon F\to Y^*\), it is decidable whether or not \(\varphi\) can be extended to a monoid homomorphism from \(F^*\) to \(M(Y,\tau)\). This result extends previous work done by the author on the homomorphism problem for the free monoid [\textit{P. V. Silva}, Discrete Math. 259, No. 1-3, 189-200 (2002; Zbl 1022.20027)].