The complexity of Presburger arithmetic with power or powers
M Benedikt, D Chistikov, A Mansutti - arXiv preprint arXiv:2305.03037, 2023 - arxiv.org
We investigate expansions of Presburger arithmetic, ie, the theory of the integers with
addition and order, with additional structure related to exponentiation: either a function that …
addition and order, with additional structure related to exponentiation: either a function that …
Combinatory Array Logic with Sums
R Raya - arXiv preprint arXiv:2311.06582, 2023 - arxiv.org
We prove an NP upper bound on a theory of integer-indexed integer-valued arrays that
extends combinatory array logic with an ordering relation on the index set and the ability to …
extends combinatory array logic with an ordering relation on the index set and the ability to …