Undecidability conjecture for three-block Presburger arithmetic with non-quadratic scalar multiplication
Undecidability conjecture for three-block Presburger arithmetic with non-quadratic scalar multiplication
Let be a non-quadratic scalar. Undecidability conjecture. -Presburger arithmetic sentences with three alternating blocks of quantifiers are undecidable. The paper contrasts this with the known complexity results for one and three alternating blocks in the quadratic case; the conjecture concerns the unresolved complexity and decidability landscape for non-quadratic scalar multiplication.
Sources & referencesView supporting material
Primary source
Philipp Hieronymi, Danny Nguyen and Igor Pak, “Presburger Arithmetic with algebraic scalar multiplications”, arXiv:1805.03624 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.