Presburger Arithmetic with algebraic scalar multiplications
share
We study complexity of integer sentences in S_α = (R, <, +,Z, x α x), which is known to be decidable for quadratic α, and undecidable for non-quadratic irrationals. When α is quadratic and the sentence has r alternating quantifier blocks, we prove both lower and upper bounds as towers of height (r-3) and r, respectively. We also show that for α non-quadratic, already r=4 alternating quantifier blocks suffice for undecidability.
READ FULL TEXT