On D0L and HDT0L sets in monoids (Q1976433)

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.