Philipp Hieronymi ; Danny Nguyen ; Igor Pak - Presburger Arithmetic with algebraic scalar multiplications

lmcs:5916 - Logical Methods in Computer Science, July 20, 2021, Volume 17, Issue 3 - https://doi.org/10.46298/lmcs-17(3:4)2021
Presburger Arithmetic with algebraic scalar multiplications

Authors: Philipp Hieronymi ; Danny Nguyen ; Igor Pak

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\geq 4$, deciding $\alpha$-PA sentences with $r$ alternating quantifier blocks and at most $c\ r$ 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.


Volume: Volume 17, Issue 3
Published on: July 20, 2021
Accepted on: April 28, 2021
Submitted on: November 21, 2019
Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,Mathematics - Combinatorics


Share

Consultation statistics

This page has been seen 59 times.
This article's PDF has been downloaded 31 times.