Complexity and (Un)decidability of Fragments of 〈ωωλ;×〉

Article type: Research Article

Authors: Bès, Alexis^a | Choffrut, Christian^{b; *}

Affiliations: [a] Université Paris-Est, LACL (EA 4219), UPEC, Créteil, France. [email protected] | [b] IRIF, CNRS and Université Paris 7 Denis Diderot, France. [email protected]

Correspondence: [*] Address for correspondence: Université Paris-Diderot, Case 7014 75205 Paris CEDEX 13 France.

Abstract: 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 〈ωωλ; ×, ω, ω+1, ω2+1〉 for every ordinal λ. Moreover, we prove (by reduction from Hilbert Tenth Problem) that the ∃*∀6-fragment of 〈ωωλ;×〉 is undecidable for every ordinal λ.

Keywords: ordinal multiplication, first-order logic, existential fragment

DOI: 10.3233/FI-2019-1752

Journal: Fundamenta Informaticae, vol. 164, no. 1, pp. 1-15, 2019