Complexity and (Un)decidability of Fragments of 〈ωωλ;×〉
Alexis Bès, Christian Choffrut · Fundamenta Informaticae · 2019
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 [Formula: see text] for every ordinal λ. Moreover, we prove (by reduction from Hilbert Tenth Problem) that the ∃*∀ 6 -fragment of [Formula: see text] is undecidable for every ordinal λ.