  Diekert, Matiyasevich and Muscholl proved that the existential first-order
theory of a trace monoid over a finite alphabet is decidable. We extend this
result to a natural class of trace monoids with infinitely many generators. As
an application, we prove that for every ordinal $\lambda$ less than
$\varepsilon_0$, the existential theory of the set of successor ordinals less
than $\lambda$ equipped with multiplication is decidable.
