Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: ordinal multiplication

Sortuj według:

Ogranicz wyniki do:

Complexity and (Un)decidability of Fragments of 〈ωωλ;×〉

Bès Alexis, Choffrut Christian

Fundamenta Informaticae

2019

Vol. 164, nr 1

1--15

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 λ.