Presburger Arithmetic with algebraic scalar multiplications

Abstract

We consider Presburger arithmetic (PA) extended by scalar multiplication by an algebraic irrational number $\alpha$, and call this extension $\alpha$-Presburger arithmetic ($\alpha$-PA). We show that the complexity of deciding sentences in $\alpha$-PA is substantially harder than in PA. Indeed, when $\alpha$ is quadratic and $r\ge 4$, deciding $\alpha$-PA sentences with $r$ alternating quantifier blocks and at most $cr$ variables and inequalities requires space at least $K{2}^{{\cdot }^{{\cdot }^{{\cdot }^{2^{C\ell (S)}}}}}$ (tower of height $r-3$), where the constants $c,K,C>0$ only depend on $\alpha$, and $\ell (S)$ is the length of the given $\alpha$-PA sentence $S$. Furthermore deciding ${\exists }^6{\forall }^4{\exists }^{11}$ $\alpha$-PA sentences with at most $k$ inequalities is PSPACE-hard, where $k$ is another constant depending only on~$\alpha$. When $\alpha$ is non-quadratic, already four alternating quantifier blocks suffice for undecidability of $\alpha$-PA sentences.

Cited by in corpus (1)

• Decidability for Sturmian words