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 -
Presburger Arithmetic with algebraic scalar multiplicationsArticle

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

    1 Document citing this article

    Consultation statistics

    This page has been seen 998 times.
    This article's PDF has been downloaded 225 times.