Complexity and (un)decidability of fragments of $\langle ω^{ω^λ}; \times \rangle$
Alexis Bès, Christian Choffrut · arXiv (Cornell University) · 2018
We specify the frontier of decidability for fragments of the first-order theory of ordinal multiplication. We give a NEXPTIME lower bound for the complexity of the existential fragment of $\langle ω^{ω^λ}; \times, ω, ω+1, ω^2+1 \rangle$ for every ordinal $λ$. Moreover, we prove (by reduction from Hilbert Tenth Problem) that the $\exists^*\forall^{6}$-fragment of $\langle ω^{ω^λ}; \times \rangle$ is undecidable for every ordinal $λ$.