O problema do homomorfismo para monóides de traços

O problema de determinar se uma função de domínio finito pode ou não ser estendida a um homomorfismo entre dois monóides de traços (monóides parcialmente comutativos livres) é indecidível. No entanto, é possivel provar a decidibilidade se o monóide de partida for livre. Como consequência, demonstra-se a decidibilidade do problema do isomorfismo para o monóide livre.