{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:01Z","timestamp":1753894381989,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T00:00:00Z","timestamp":1626739200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We consider Presburger arithmetic (PA) extended by scalar multiplication by\nan algebraic irrational number $\\alpha$, and call this extension\n$\\alpha$-Presburger arithmetic ($\\alpha$-PA). We show that the complexity of\ndeciding sentences in $\\alpha$-PA is substantially harder than in PA. Indeed,\nwhen $\\alpha$ is quadratic and $r\\geq 4$, deciding $\\alpha$-PA sentences with\n$r$ alternating quantifier blocks and at most $c\\ r$ variables and inequalities\nrequires space at least $K 2^{\\cdot^{\\cdot^{\\cdot^{2^{C\\ell(S)}}}}}$ (tower of\nheight $r-3$), where the constants $c, K, C&gt;0$ only depend on $\\alpha$, and\n$\\ell(S)$ is the length of the given $\\alpha$-PA sentence $S$. Furthermore\ndeciding $\\exists^{6}\\forall^{4}\\exists^{11}$ $\\alpha$-PA sentences with at\nmost $k$ inequalities is PSPACE-hard, where $k$ is another constant depending\nonly on~$\\alpha$. When $\\alpha$ is non-quadratic, already four alternating\nquantifier blocks suffice for undecidability of $\\alpha$-PA sentences.<\/jats:p>","DOI":"10.46298\/lmcs-17(3:4)2021","type":"journal-article","created":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T09:55:42Z","timestamp":1627379742000},"source":"Crossref","is-referenced-by-count":1,"title":["Presburger Arithmetic with algebraic scalar multiplications"],"prefix":"10.46298","volume":"Volume 17, Issue 3","author":[{"given":"Philipp","family":"Hieronymi","sequence":"first","affiliation":[]},{"given":"Danny","family":"Nguyen","sequence":"additional","affiliation":[]},{"given":"Igor","family":"Pak","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2021,7,20]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/7688\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/7688\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:17:24Z","timestamp":1687292244000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/5916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,20]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-17(3:4)2021","relation":{"has-preprint":[{"id-type":"arxiv","id":"1805.03624v5","asserted-by":"subject"},{"id-type":"arxiv","id":"1805.03624v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1805.03624","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1805.03624","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2021,7,20]]},"article-number":"5916"}}