The homomorphism problem for trace monoids
It is proved to be decidable, for any given finite subset F of X* dependency alphabet (Y, tau) and mapping rho : F --> Y*, whether or not rho can be extended to a monoid homomorphism (p) over tilde : F* --> M(Y,tau). This contrasts with the undecidability of the symmetric problem, when we consider the dependency alphabet (X, tau) instead. Some other particular cases of homomorphism and isomorphism problems among trace monoids are also discussed. (C) 2003 Elsevier B.V. All rights reserved.
homomorphism trace monoids decidability