Presburger Arithmetic with algebraic scalar multiplications

arXiv1805.03624MaRDI QIDQ6301384FDOQ6301384

Authors: Philipp Hieronymi, Danny Nguyen, Igor Pak 

Publication date: 9 May 2018

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 $rgeq4$, deciding $alpha$-PA sentences with $r$ alternating quantifier blocks and at most $cr$ variables and inequalities requires space at least $K{2}^{cdo{t}^{cdo{t}^{cdo{t}^{2^{Cell(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 $exist{s}^{6}foral{l}^{4}exist{s}^{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.

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

This page was built for publication: Presburger Arithmetic with algebraic scalar multiplications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301384)