The complexity of Presburger arithmetic with power or powers

Michael Benedikt, Dmitry Chistikov, Alessio Mansutti

We investigate expansions of Presburger arithmetic, i.e., the theory of the integers with addition and order, with additional structure related to exponentiation: either a function…