A monoid $M$ is said to have the projection property if there exists a finite set $Y$, a surjective morphism $p\colon Y^*\to M$, and morphisms $t_1,\ldots,t_n\colon Y^*\to Y^*$ such that $\ker p=\ker t_1\cap\cdots\cap\ker t_n$. If, furthermore, $\ker p$ is contained in the kernel of the projection onto the free commutative monoid over~$Y$, then $M$ is said to have the strong projection property. The author shows that strong equivalence of HDT0L sets in a monoid with the strong projection property and equivalence of D0L sets in a monoid with the projection property are both decidable. Although these results apply to the case of free partially commutative monoids, the arguments actually allow the author to prove a stronger version in this case.
Reviewer: Jorge Almeida (Porto)