2014/01/31 by Christoph Haase · 2 citations
Computer Science · #Computability, Logic, AI Algorithms #Logic, programming, and type systems #acm:03B70 #cs.LO #msc:03B70 #semigroups and automata theory
paper · pdf · doi:10.1145/2603088.2603092
10 pages, 2 figures
arxiv created 2014/05/12 · openalex publication_date 2014/07/14 · arxiv updated 2014/10/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/30
It is shown that for any fixed i > 0, the Σi+1-fragment of Presburger arithmetic, i.e., its restriction to i + 1 quantifier alternations beginning with an existential quantifier, is complete for ΣiEXP, the i-th level of the weak EXP hierarchy, an analogue to the polynomial-time hierarchy residing between NEXP and EXPSPACE. This result completes the computational complexity landscape for Presburger arithmetic, a line of research which dates back to the seminal work by Fischer & Rabin in 1974. Moreover, we apply some of the techniques developed in the proof of the lower bound in order to establish bounds on sets of naturals definable in the Σ1-fragment of Presburger arithmetic: given a Σ1-formula Φ(x), it is shown that the set of non-negative solutions is an ultimately periodic set whose period is at most doubly-exponential and that this bound is tight.