Presburger Arithmetic with algebraic scalar multiplications

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...

Full beskrivning

Bibliografiska uppgifter

Huvudupphov:	Philipp Hieronymi, Danny Nguyen, Igor Pak
Materialtyp:	Artigo
Språk:	Inglês
Utgiven:	Logical Methods in Computer Science e.V. 2021-07-01
Serie:	Logical Methods in Computer Science
Ämnen:	mathematics - logic computer science - computational complexity computer science - logic in computer science mathematics - combinatorics
Länkar:	https://lmcs.episciences.org/5916/pdf
Taggar:	Lägg till en tagg Inga taggar, Lägg till första taggen!