Decidability of the existential fragment of some infinitely generated trace monoids: an application to ordinals
Alexis Bès, Christian Choffrut · arXiv (Cornell University) · 2018
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 $λ$ less than $\varepsilon_0$, the existential theory of the set of successor ordinals less than $λ$ equipped with multiplication is decidable.