Fact-checked by Grok 2 weeks ago

Presburger arithmetic

Presburger arithmetic is the first-order theory of the natural numbers equipped with the successor function, constants for zero and one, addition, and logical connectives, but excluding multiplication.^[1] Named after the Polish mathematician Mojżesz Presburger, who introduced it in 1929 at the First Congress of Mathematicians of the Slavic Countries in Warsaw, it represents a decidable fragment of arithmetic that avoids the undecidability arising from full multiplication.^[1] Presburger's seminal work demonstrated that this theory is both complete—meaning every valid formula is provable—and decidable, via a quantifier-elimination procedure that reduces arbitrary formulas to quantifier-free equivalents, such as linear Diophantine equations or congruences.^[1] The theory's decidability stems from its ability to express only semi-linear sets, which are unions of finitely many polyhedra defined by linear inequalities over the integers, allowing automated decision procedures despite the infinite domain.^[2] Early implementations of these procedures appeared in the 1950s, with Martin Davis providing one of the first computer-based solvers in 1954, highlighting its practical utility even then.^[1] Modern decision methods combine quantifier elimination with automata-theoretic approaches, achieving deterministic triply exponential time complexity, though lower bounds show at least doubly exponential time is necessary in the worst case.^[2] Presburger arithmetic finds applications in formal verification, where it models systems with unbounded counters or states, such as in software model checking and hardware design, due to its expressiveness for linear constraints without the complexity of multiplication.^[2] It also solves combinatorial problems like the Frobenius coin problem, determining the largest integer not representable as a non-negative integer combination of given coprime integers.^[2] Extensions incorporating multiplication by constants or limited powers remain decidable, but adding full multiplication yields the undecidable theory of Peano arithmetic, underscoring Presburger's boundary between tractable and intractable arithmetic.^[2]

History and Foundations

Origins and Development

Mojżesz Presburger, a Polish mathematician and student of Alfred Tarski at the University of Warsaw, who later perished in the Holocaust around 1943, introduced the theory now known as Presburger arithmetic in his 1929 master's thesis.^[3] The thesis was presented as a paper at the First Congress of Mathematicians of the Slavic Countries, held in Warsaw from September 23–27, 1929.^[4] In this work, titled Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, Presburger defined the theory as the first-order logic of the natural numbers with the successor function and addition as the primitive operations.^[5] Presburger established the completeness and decidability of this theory through a novel quantifier elimination procedure, demonstrating that every first-order formula could be transformed into an equivalent quantifier-free form whose satisfiability could be mechanically checked.^[6] This proof provided a decision procedure for the entire theory, resolving a key question about the formal tractability of arithmetic without multiplication. The development of Presburger arithmetic was influenced by David Hilbert's program, initiated in the 1920s, which aimed to formalize mathematics and determine the decidability of axiomatic systems, including fragments of arithmetic. Presburger's positive result on decidability offered an early success within this framework, contrasting with the broader challenges posed by Hilbert's Entscheidungsproblem. In 1931, Kurt Gödel referenced Presburger's work in his seminal paper on incompleteness theorems, noting it as an example of a complete and decidable system in contrast to the undecidability of full arithmetic with multiplication.^[5] This positioned Presburger arithmetic as a decidable fragment related to Peano arithmetic.^[5]

Motivations from Logic and Mathematics

The development of Presburger arithmetic was deeply rooted in David Hilbert's program for the foundations of mathematics, particularly his Entscheidungsproblem posed in 1928, which sought an algorithm to determine the validity of any statement in first-order logic relative to a given set of axioms. This problem aimed to establish the consistency of arithmetic and analysis, thereby resolving foundational issues such as the continuum hypothesis by providing a mechanical method to verify proofs and counterexamples in mathematical theories. Presburger arithmetic emerged as a key example of a decidable fragment of arithmetic, demonstrating that such algorithmic resolution was possible for restricted systems, even as the full Entscheidungsproblem was later shown undecidable by Alonzo Church and Alan Turing in 1936.^[2]^[7] A primary motivation was the desire for a theory of natural numbers weaker than Peano arithmetic, which incorporates both addition and multiplication and is known to be undecidable due to Gödel's incompleteness theorems. By excluding multiplication and focusing solely on addition, Presburger arithmetic avoids the expressive power that leads to undecidability, yet it remains sufficiently rich to capture essential properties of integers, such as linear Diophantine equations and order relations, making it suitable for logical analysis without the full complexity of multiplication. This simplification allowed researchers to explore the boundaries of decidability in arithmetic while retaining practical utility for modeling additive structures in mathematics and logic.^[2]^[1] Mojżesz Presburger's specific goal was to provide a complete and decidable axiomatization of the natural numbers using only addition, building on but contrasting with Thoralf Skolem's earlier 1919 work on quantifier elimination for monadic second-order logic, which did not fully address integer arithmetic with addition. Presburger sought to prove that every sentence in this language is either provable or refutable, thereby establishing a decidable subsystem of number theory that Hilbert's program could encompass. In one sentence, his 1929 proof technique relied on an effective quantifier elimination procedure to reduce arbitrary formulas to quantifier-free equivalents.^[1] Presburger's contributions were influenced by the vibrant 1920s Polish school of logic, centered at the University of Warsaw under figures like Alfred Tarski, whose 1927–1928 lectures on deductive systems and model theory emphasized the analysis of formal theories' completeness. Tarski later extended these ideas in his work on quantifier elimination for theories like real closed fields, inspiring further developments in decidable fragments, including Presburger arithmetic's role in understanding additive properties without multiplicative complications. This intellectual environment fostered Presburger's innovative approach, highlighting the Polish logicians' focus on bridging algebraic methods with logical decidability.^[1]^[2]

Formal Definition

Syntax and Language

Presburger arithmetic is formulated in a first-order language whose signature consists of the constant symbol $0, the unary function symbol S (representing the successor function), and the binary function symbol + (representing addition), along with the equality predicate =.^[8] The variables are typically denoted by symbols such as x, y, z, intended to range over the natural numbers.^[8] Additionally, the language includes the standard logical connectives \neg (negation), \wedge (conjunction), \vee (disjunction), \rightarrow (implication), \leftrightarrow (biconditional), and the quantifiers \forall (universal) and \exists (existential).^[8] Terms in this language are inductively defined starting from the constant $0 and variables, with applications of the successor function S and addition +.^[8] Specifically, any term t is either a variable, the constant $0, S(t') where t' is a term, or t_1 + t_2 where t_1 and t_2 are terms.^[8] For instance, the term S(S(0)) denotes the number 2, and x + y represents the sum of variables x and y.^[8] Atomic formulas are equations of the form t_1 = t_2, where t_1 and t_2 are terms.^[8] The full class of formulas is obtained by closing the atomic formulas under the logical connectives and quantifiers.^[8] In a formula, variables may be free (unquantified and occurring unbound) or bound (within the scope of a quantifier).^[8] An example of a formula is \forall x \, (x + 0 = x), which asserts that adding zero leaves any number unchanged.^[8]

Semantics and Models

Presburger arithmetic is interpreted in first-order structures over the language consisting of the constant symbol 0, the unary successor function symbol S, and the binary addition symbol +. The standard model is the structure \mathcal{N} = (\mathbb{N}, 0, S, +), where the domain \mathbb{N} is the set of non-negative integers \{[0](/page/0), 1, 2, \dots \}, the constant 0 is interpreted as the number zero, the successor function S satisfies S(n) = n + 1 for each n \in \mathbb{N}, and the addition operation + satisfies +(m, n) = m + n for all m, n \in \mathbb{N}.^[9] This model captures the intended semantics of natural numbers under successor and addition, providing a concrete realization where formulas are evaluated using the usual arithmetic operations. The satisfaction relation for a formula \phi in a structure T, denoted T \models \phi, holds if \phi is true when variables are assigned elements from the domain of T and non-logical symbols are interpreted according to T's functions and constants. In the standard model \mathcal{N}, for instance, the universal formula \forall x \exists y (x + y = S(x)) is satisfied, as for any x \in \mathbb{N}, setting y = 1 ensures x + 1 = S(x).^[2] More generally, satisfaction in \mathcal{N} aligns with the truth of arithmetic statements over the non-negative integers, such as the existence of solutions to linear equations defined by the formula. Non-standard models of Presburger arithmetic exist beyond the structure \mathcal{N}, as demonstrated by the compactness theorem applied to the theory's axioms. For example, one can construct a non-standard model by considering an infinite set of sentences asserting the existence of distinct elements c_1, c_2, \dots satisfying S^{n}(0) \neq c_i for all standard n and i, along with the axioms; compactness ensures a model containing these elements, which cannot embed \mathbb{N} standardly.^[10] All such models, standard or non-standard, satisfy the complete set of axioms defining the theory, preserving properties like the order type extensions such as \mathbb{N} + \mathbb{Z} \cdot A for some dense linear order A without endpoints.^[9] For quantifier-free formulas in Presburger arithmetic, interpretations are defined over the Herbrand universe, which comprises all ground terms constructed from 0 using S and +, effectively yielding the standard numerals S^k(0) for k \geq 0. Satisfaction of a quantifier-free formula under such an interpretation reduces to evaluating atomic equations and inequalities on these ground terms, corresponding to linear Diophantine conditions that hold or fail based on integer solutions.^[10] This approach leverages the theory's structure to assess truth without quantifiers, aligning with the decidability of quantifier-free fragments via periodic sets.^[9]

Axioms and Proof System

Presburger arithmetic is formalized within a first-order language consisting of the constant symbol 0, unary function symbol S (successor), binary function symbol + (addition), and the equality predicate =. The proof system is a standard Hilbert-style calculus for first-order logic, augmented with non-logical axioms specific to the structure of the natural numbers under successor and addition.^[1]^[2] The logical axioms include all instances of propositional tautologies, such as \phi \lor \lnot \phi and (\phi \to \psi) \to (\lnot \psi \to \lnot \phi), where \phi, \psi are any formulas in the language. Additionally, there are axiom schemas for quantifiers, including \forall x \, \phi(x) \to \phi(t) for any term t free for x in \phi(x), and \phi(t) \to \exists x \, \phi(x) under similar conditions. These ensure the standard treatment of first-order quantification and propositional connectives.^[1] Equality is governed by the standard axioms: reflexivity x = x; symmetry x = y \to y = x; transitivity (x = y \land y = z) \to x = z; and congruence axioms x = y \to S(x) = S(y) and (x = y \land z = w) \to x + z = y + w. These axioms capture the reflexive, symmetric, transitive, and substitutive properties of equality with respect to the successor and addition functions.^[2] The addition operation is axiomatized by the following schemas, which define it recursively via the successor:

\forall x \, (x + 0 = x)

\forall x \forall y \, (x + S(y) = S(x + y))

These ensure that addition behaves as repeated application of the successor starting from the first argument.^[1] The successor function is implicitly defined through these addition axioms and the constant 0, with 1 defined as S(0). To enable proofs by induction, the system includes the induction axiom schema: for any formula \phi(x) in the language,

[\phi(0) \land \forall x \, (\phi(x) \to \phi(S(x)))] \to \forall x \, \phi(x).

This schema allows deriving universal statements over all natural numbers by base case and inductive step.^[2] The inference rules are modus ponens—if \vdash \phi and \vdash \phi \to \psi, then \vdash \psi—and universal generalization—if \vdash \phi and x does not occur free in any undischarged assumptions, then \vdash \forall x \, \phi. Additionally, substitution of terms for free variables (avoiding capture) is permitted. These rules, combined with the axioms, form a sound and complete proof system relative to the standard model of natural numbers (\mathbb{N}, 0, S, +), meaning every semantically valid sentence is provable, as established by Presburger using a quantifier elimination procedure.^[1]

Core Properties

Decidability and Completeness

In 1929, Mojżesz Presburger proved that the first-order theory of the natural numbers with addition, now known as Presburger arithmetic, is decidable, meaning there exists an algorithm to determine the validity of any sentence in its language.^[1] This result established that the set of valid sentences is recursive, allowing for a mechanical procedure to check truth in all models of the theory.^[1] The decidability follows from Presburger's quantifier elimination procedure, which shows that every formula in the language is equivalent to a quantifier-free formula in an expanded language, and this equivalence can be computed algorithmically.^[2] To apply the procedure, a given formula is first transformed into prenex normal form, where all quantifiers appear at the front, followed by a quantifier-free matrix consisting of linear inequalities and congruences.^[2] Quantifiers are then eliminated block by block, starting from the innermost. A key step in the elimination process involves removing an existential quantifier from a formula of the form \forall x \, \exists y \, \phi(x,y), where \phi(x,y) is quantifier-free and consists of linear Diophantine inequalities over the integers.^[2] This is achieved by solving for the conditions on x under which there exists an integer y satisfying \phi(x,y), which reduces to determining the solvability of a system of linear Diophantine equations and inequalities; such solvability can be decided using properties of greatest common divisors and periodic conditions modulo relevant coefficients.^[2] The resulting equivalent formula without the existential quantifier is again quantifier-free in an expanded language that includes additional predicates for divisibility, enabling iterative elimination until no quantifiers remain.^[2] Presburger arithmetic is a complete theory: for every sentence, either it or its negation is provable from the axioms. This follows from the quantifier elimination theorem and the fact that the axioms, including those defining addition and the induction schema over quantifier-free formulas, fully capture the semantics of the natural numbers with addition.

Computational Complexity

Presburger arithmetic is decidable in primitive recursive time, but the general decision procedure exhibits triply exponential time complexity with respect to the size n of the input sentence. Fischer and Rabin (1974) demonstrated that any algorithm requires at least $2^{2^{2^{\Theta(n)}}} time in the worst case, establishing a tight lower bound that matches known upper bounds from quantifier elimination procedures.^[11] The space complexity of deciding Presburger sentences is doubly exponential. Berman (1980) showed that the problem is complete for alternating Turing machines with polynomial time and doubly exponential space, providing precise bounds that capture the inherent difficulty beyond mere time measures.^[12] For restricted fragments, significant complexity improvements exist. The quantifier-free fragment admits linear-time decision procedures when coefficients are encoded in unary, though in general it is NP-complete; formulas with a fixed quantifier prefix and bounded alternations can be decided in polynomial time.^[2] Practical implementations of Presburger decision procedures commonly employ Fourier-Motzkin elimination for successive quantifier removal, which, while theoretically exponential, performs well on small instances, or automata-based methods that translate formulas into finite automata over strings representing numbers in base k.^[2] In the 2020s, advancements in satisfiability modulo theories (SMT) solvers, such as optimized handling of linear integer arithmetic in tools like Z3, have enabled efficient solving of many practical Presburger instances through bit-vector encodings and heuristic quantifier instantiation, though the underlying triply exponential worst-case bound renders the full theory impractical for large-scale inputs.^[13]

Expressiveness and Limitations

Definable Sets and Relations

In Presburger arithmetic, the definable sets are precisely the semilinear sets. A linear set is defined as the set of all vectors x \in \mathbb{N}^k such that there exists a vector y \in \mathbb{N}^m satisfying x = b + A y, where A is an integer matrix and b is an integer vector.^[14] A semilinear set is a finite union of linear sets.^[14] The Ginsburg-Spanier theorem establishes that the subsets of \mathbb{N}^k definable by Presburger formulas are exactly these semilinear sets.^[14] Notable relations that cannot be defined in Presburger arithmetic include multiplication, as the set \{ (x, y, z) \in \mathbb{N}^3 \mid z = x \cdot y \} is not semilinear.^[15] Similarly, exponentiation is undefinable, since the graph \{ (x, y, z) \in \mathbb{N}^3 \mid z = x^y \} fails to be semilinear.^[16] The set of prime numbers is also not Presburger-definable, as it is not a semilinear subset of \mathbb{N}.^[17] When interpreted over the integers \mathbb{Z} rather than the natural numbers, Presburger arithmetic defines sets that are semilinear subsets of \mathbb{Z}^k.^[2] In the unary case (k=1), these coincide with the ultimately periodic sets possessing a finite basis, meaning finite unions of arithmetic progressions.^[2] Muchnik provided a characterization in 1991 (preprint) of certain higher-level definable sets, identifying them as recursively enumerable sets whose indices are Presburger-definable.^[17] This result extends the understanding of definability beyond first-order formulas by incorporating computability constraints aligned with Presburger's structure.^[17]

Comparison to Peano Arithmetic

Peano arithmetic (PA) is a first-order axiomatic system for the natural numbers that extends the language of Presburger arithmetic by including multiplication as a primitive operation, along with axioms defining its recursive behavior. Specifically, PA incorporates the multiplication axioms \forall x (x \cdot 0 = 0) and \forall x \forall y (x \cdot S(y) = x \cdot y + x), where S denotes the successor function, in addition to the axioms for addition and the induction schema. These axioms enable PA to formalize a broader class of arithmetic statements, but they also render the theory undecidable, as demonstrated by Gödel's first incompleteness theorem, which shows that PA cannot prove all true statements in its language due to the ability to encode syntactic structures via Gödel numbering using both addition and multiplication.^[2] Presburger arithmetic serves as a proper subtheory of PA, meaning that every theorem provable in Presburger arithmetic is also provable in PA, since PA includes all the axioms and inference rules of Presburger arithmetic for addition and order. However, the converse does not hold: PA proves statements that involve multiplication, such as the totality axiom \forall x \forall y \exists z (x \cdot y = z), which cannot even be expressed in the language of Presburger arithmetic, let alone proved. This asymmetry highlights the increased expressive power of PA, which allows it to capture the full structure of natural number arithmetic but at the cost of losing decidability.^[2]^[18] In terms of interpretability, Presburger arithmetic is straightforwardly interpretable within PA, as PA's models satisfy all Presburger sentences due to their shared additive structure. The reverse is impossible: PA is not interpretable in Presburger arithmetic because multiplication is not definable within the additive language of Presburger arithmetic, preventing the encoding of Gödel numbers necessary to replicate PA's syntactic capabilities. Even weaker systems like Robinson arithmetic Q, which omits the full induction schema of PA but retains basic axioms for both addition and multiplication, remain undecidable, underscoring that the inclusion of multiplication—even in a minimal form—is sufficient to introduce undecidability, in stark contrast to the "tame" decidability of Presburger arithmetic.^[2] Philosophically, Presburger arithmetic represents a decidable fragment of arithmetic that aligns with aspects of Hilbert's program for formalizing mathematics through finitary methods, offering a complete and consistent system without the pitfalls exposed by Gödel's theorems for stronger theories like PA. While PA's undecidability dashed hopes for a fully mechanical proof verification in full arithmetic, Presburger arithmetic provides a viable, automated alternative for additive number theory, influencing subsequent work in logic and computability.^[2]

Applications and Extensions

In Automated Verification

Presburger arithmetic serves as a foundational decidable theory for automated verification, particularly in handling linear constraints over integer counters that model unbounded resources in software and hardware systems. Its quantifier-free fragment, linear integer arithmetic, enables symbolic representation of infinite state spaces, supporting techniques like model checking and satisfiability modulo theories (SMT) solving without the undecidability introduced by multiplication. This makes it ideal for verifying properties such as safety and liveness in concurrent systems where states can be encoded as vectors satisfying linear inequalities.^[2] In model checking, Presburger arithmetic encodes linear constraints over counters in formalisms like Petri nets and pushdown automata, facilitating analysis of reachability and temporal properties. For Petri nets, the mutual reachability relation between configurations with d counters compiles into a quantifier-free Presburger formula as a doubly exponential disjunction of O(d) linear constraints, each of exponential size, enabling exponential-space complete decision procedures for verification.^[19] Vector addition systems with states (VASS), equivalent to unbounded counter systems, model transitions as Presburger formulas in Kripke structures, supporting symbolic techniques such as global model checking via fixpoint iteration over automata-translated representations and local model checking via decomposition rules that focus on reachable states, for which the local model checking procedure terminates in 79% of cases in practice.^[20] For pushdown automata, one-counter processes reduce verification problems like reachability to specialized Presburger fragments, allowing decidable complexity analysis that avoids full pushdown complexity blowups.^[21] SMT solvers integrate Presburger arithmetic solvers for bounded model checking of integer variables in verification tasks. Z3 employs an efficient arithmetic solver for quantifier-free linear integer arithmetic, using simplex-based methods to decide constraints in bounded model checking, which unrolls transition relations up to a fixed depth to detect violations in systems like concurrent programs. CVC5 builds on this with enhanced linear integer arithmetic support, incorporating Fourier-Motzkin elimination and cutting-plane methods for faster resolution of Presburger queries, applied in bounded checks for hardware designs with counters. Presburger arithmetic applies to protocol verification by modeling linear aspects like buffer sizes and sequence numbers, where multiplication is absent. In resource protocols, buffer management invariants—such as size bounds expressed as linear inequalities like |B| \leq N—are verified using Presburger formulas in type systems, ensuring safety properties like non-overflow without full arithmetic. For sequence number protocols, stop-and-wait mechanisms are encoded as counter systems where transitions update sequence counters linearly, allowing Presburger-based model checking to confirm deadlock freedom and progress in colored Petri net models. Case studies from the 2000s to 2020s highlight its impact. Techniques for checking temporal properties of Presburger counter systems via reachability analysis have been applied to benchmarks, employing iterative approximation for liveness and CTL formulas, with experimental validation showing practical scalability.^[22] A key limitation in automated verification is Presburger arithmetic's exclusion of multiplication, necessitating approximations for non-linear operations. Bit-blasting techniques translate multiplication in bit-vector models to propositional clauses for SAT solving, often combined with abstraction-refinement: multiplications wider than 4 bits are initially abstracted as uninterpreted functions handling base cases (e.g., x \cdot 0 = 0), refining via bit-level expansion only when conflicts arise, thus extending Presburger decidability to practical verification of arithmetic-heavy systems.^[23]

In Integer Programming and Optimization

Presburger arithmetic plays a foundational role in integer linear programming (ILP), where the feasibility of systems of linear inequalities over integers, such as \{ \mathbf{x} \in \mathbb{Z}^n \mid A \mathbf{x} \geq \mathbf{b} \}, can be directly encoded as existential sentences in the theory.^[24] These encodings leverage the fact that linear constraints with integer coefficients and variables form quantifier-free Presburger formulas, and the existence of solutions corresponds to satisfiability in the theory.^[25] Quantifier elimination procedures, such as those based on Fourier-Motzkin elimination adapted for integers or automata-theoretic methods, allow reduction to quantifier-free forms to determine feasibility or derive bounds, enabling exact solving despite the inherent complexity.^[25] For instance, the subset sum problem, a canonical ILP, is expressed as \exists x_1 \dots \exists x_n \, ( \bigwedge_i (x_i = 0 \lor x_i = 1) \land \sum_i a_i x_i = t ), highlighting the tight integration.^[25] In branch-and-bound methods for ILP, Presburger arithmetic serves as an oracle for generating cutting planes—valid linear inequalities that tighten relaxations by excluding fractional solutions while preserving integer feasibility.^[26] Interpolants computed via Presburger decision procedures provide such cuts, as they separate infeasible regions in a way compatible with the theory's linear structure; for example, Craig interpolants from unsatisfiable Presburger formulas yield inequalities derivable solely from the input constraints.^[27] This augmentation enhances pruning in the search tree, particularly for problems with sparse or structured coefficients, by leveraging the decidability of Presburger to validate or derive cuts efficiently.^[26] Presburger arithmetic connects deeply to integer lattices, where solution sets to ILPs are semilinear—unions of finitely many linear sets defined by periodic lattices—and thus fully describable within the theory.^[25] For totally unimodular matrices, where every square submatrix has determinant 0, ±1, the integer hull of the polyhedron coincides with the LP relaxation, rendering ILP feasibility polynomial-time decidable via Presburger methods, as the problem reduces to linear programming over rationals with integral guarantees.^[28] This property is exploited in lattice-based reformulations, where unimodular transformations preserve integrality and allow Presburger encodings to certify solutions in domains like network flows.^[29] Practical tools for ILP often incorporate Presburger techniques in preprocessing to detect infeasibility, tighten bounds, or simplify constraints; for example, SMT solvers like Z3 and cvc5 embed Presburger decision procedures for handling integer linear constraints in optimization contexts.^[25] Commercial MIP solvers such as CPLEX and Gurobi, while primarily relying on LP-based relaxations, have been integrated into Presburger solvers for exact arithmetic solving, and their presolve routines perform operations akin to Presburger simplification, such as implied bound propagation from linear inequalities.^[30] These capabilities find application in scheduling and logistics, notably airline crew rostering, where ILPs model duty assignments under linear constraints on flight coverage, rest periods, and crew limits, solvable via Presburger-encoded feasibility checks to ensure operational efficiency.^[31] Recent advances in the 2020s include hybrid solvers that combine Presburger arithmetic with SAT techniques for mixed-integer programming, enhancing scalability by using bit-blasting for nonlinear or boolean aspects alongside linear arithmetic engines for constraints; for instance, integrations in SMT frameworks leverage MIP solvers like SCIP alongside Presburger oracles to optimize over integer linear-exponential objectives.^[32] Such approaches, building on automata and interpolation, have improved performance on large-scale MIPs in [operations research](/page/operations research), with [quantifier elimination](/page/quantifier elimination) optimizations reducing exponential blowups in practice.^[25]

Decidable Extensions

Extensions of Presburger arithmetic that incorporate multiplication by constants or limited powers, such as x \cdot c for fixed integer c or polynomials of bounded degree, remain decidable, though with increased computational complexity. For example, the theory with multiplication by 2 allows encoding of parity but preserves quantifier elimination via automata constructions. These extensions expand expressiveness for applications like modular arithmetic in verification while avoiding the undecidability of full multiplication.^[2]

References

[1]
[PDF] Presburger's Article on Integer Arithmetic: Remarks and Translation
The book was compiled by Presburger from oral lectures given by Lukasiewicz at the University of Warsaw. This era of Polish mathematical activity is fast ...
[2]
[PDF] A Survival Guide to Presburger Arithmetic
In formal verification, Presburger arithmetic is the first-choice logic to represent and rea- son about systems with infinitely many states.Missing: sources | Show results with:sources
[3]
(PDF) Mojżesz presburger: Life and work - ResearchGate
Aug 10, 2025 · The life and work of Mojżesz Presburger (1904–1943?) are summarised in this article. Although his production in logic was small, it had considerable impact.Missing: Lwów dissertation
[4]
[PDF] Presburger's Article on Integer Arithmetic: Remarks and Translation
The article was written by Mojżesz Presburger, a Polish student of mathematics, and presented at a conference in Warsaw in 1929. In it Presburger showed ...
[5]
Gödel’s Incompleteness Theorems (Stanford Encyclopedia of Philosophy)
Summary of each segment:
[6]
A survival guide to presburger arithmetic | ACM SIGLOG News
This article provides a broad yet concise overview over the history, decision procedures, extensions and geometric properties of Presburger arithmetic.Missing: original | Show results with:original<|control11|><|separator|>
[7]
The Rise and Fall of the Entscheidungsproblem
Hilbert believed that, following the discovery of the decision method, arithmetic and analysis would be proved consistent, thereby “establish[ing] that ...
[8]
[PDF] A Complete Proof of Incompleteness
Dec 3, 2014 · 0 is a symbol for a constant, S a unary function symbol and + and · are binary function ... to define multiplication using addition and the ...<|control11|><|separator|>
[9]
[PDF] Interpretations in Presburger Arithmetic
Feb 1, 2015 · The general goal of this thesis is to obtain a better understanding of the relations between various weak systems of arithmetic.
[10]
[PDF] Herbrand Theorem, Equality, and Compactness
compactness theorem (page 15, Form 3) that the entire set Φ0 is ... The result is a nonstandard model for Presburger Arithmetic. (All sentences ...
[11]
[PDF] super-exponential complexity of pres burger arithmetic
Let AX satisfy the condition that to decide for a sentence F whether F € AX, i.e. whether. F is an axiom, requires a number of computational steps which is ...
[12]
The complexity of logical theories - ScienceDirect.com
In this paper we introduce a method of encoding the computation of an alternating TM into a logical theory. The efficiency of the embedding we give together ...
[13]
[PDF] arXiv:2403.18995v2 [cs.LO] 18 May 2024
May 18, 2024 · Linear integer arithmetic (LIA), also known as Presburger arithmetic, is the first-order theory of integers with addition. Its applications ...Missing: 2020s | Show results with:2020s
[14]
Semigroups, Presburger formulas, and languages - MSP
The problem of finding a decision procedure for determining of an arbitrary semilinear set L whether τ~\L) is a language is open. BIBLIOGRAPHY. 1. S. Ginsburg ...
[15]
[PDF] arXiv:2209.11858v1 [math.LO] 23 Sep 2022
Sep 23, 2022 · 4The set kN is not semilinear and thus cannot be Presburger-definable by Ginsburg and Spanier [7]. 1. Page 2. UNDEFINABILITY OF MULTIPLICATION ...<|control11|><|separator|>
[16]
UNDEFINABILITY OF MULTIPLICATION IN PRESBURGER ...
Oct 10, 2023 · We begin by proving that any Presburger-definable image of one or more sets of powers has zero natural density. Then, by adapting the proof ...
[17]
The definable criterion for definability in Presburger arithmetic and ...
A. Muchnik, The definable criterion for definability in Presburger arithmetic and its application, preprint, Institute of New Technologies, Moscow, 1991 (in ...
[18]
[PDF] Decidability of extensions of Presburger arithmetic by ... - arXiv
Oct 3, 2025 · Background. Presburger arithmetic, that is, the first-order theory of natural numbers with addition Th(N;+), is well-known to be decidable.
[19]
[2210.09931] Compiling Petri Net Mutual Reachability in Presburger
Oct 18, 2022 · In this paper we provide a way to compile the mutual reachability relation of a Petri net with d counters into a quantifier-free Presburger formula.
[20]
[PDF] Verification of Infinite State Systems Using Presburger Arithmetic
This work deals with the verification of computer systems that continuously interact with the environment. Such systems are frequently encountered in ...<|control11|><|separator|>
[21]
[PDF] On the Computational Complexity of Verifying One-Counter Processes
Abstract—One-counter processes are pushdown systems over a singleton stack alphabet (plus a stack-bottom symbol). We study the complexity of two closely ...
[22]
Checking Temporal Properties of Presburger Counter Systems using Reachability Analysis
### Summary of Cache Coherence Verification Using Presburger Counter Systems
[23]
[PDF] Deciding Bit-Vector Arithmetic with Abstraction? - People @EECS
Abstract. We present a new decision procedure for finite-precision bit- vector arithmetic with arbitrary bit-vector operations. Our procedure.
[24]
[PDF] Deciding Quantifier-Free Presburger Formulas using Finite ...
Given a formula Φ in quantifier-free Presburger arithmetic, it is well known that, if there is a satisfying solution to Φ, there is one whose size, ...Missing: Herbrand | Show results with:Herbrand<|control11|><|separator|>
[25]
[PDF] An Introduction to the Theory of Linear Integer Arithmetic - DROPS
Thus, one says that (the theory of) Presburger arithmetic is decidable. This statement requires proof, because quantifiers in φ range over an infinite set, Z.
[26]
Interpolating Quantifier-Free Presburger Arithmetic - SpringerLink
In this paper, we focus on an interpolating decision procedure for the full quantifier-free fragment of Presburger Arithmetic, i.e., linear arithmetic over the ...
[27]
[PDF] Interpolating Quantifier-Free Presburger Arithmetic
For the full QFPA fragment, the algorithm is exponential in the worst case. This complexity is proved tight since we exhibit formulas such that every ...
[28]
Tractable Fragments of Presburger Arithmetic | Theory of Computing ...
Dec 20, 2004 · We show that if the constraint matrix is totally unimodular, the problem of deciding a QIP can be solved in polynomial time. We also ...
[29]
[PDF] The Computational Complexity of Presburger Arithmetic
The main question addressed in Part I of the dissertation is: By restricting the number of variables and inequalities in PA, do we obtain polynomial complexity?
[30]
[PDF] Abstraction-based Satisfiability Solving of Presburger Arithmetic*
We present a new abstraction-based framework for deciding satisfiability of quantifier-free Presburger arithmetic formulas. Given a. Presburger formula φ, our ...Missing: SMT 2020s<|control11|><|separator|>
[31]
Airline Crew Rostering: Problem Types, Modeling, and Optimization
Aug 9, 2025 · Airline crew rostering is an important part of airline operations and an interesting problem for the application of operations research.
[32]
Leveraging linear and mixed integer programming for SMT
In this paper, we describe a technique for integrating LP solvers that improves the performance of SMT solvers without compromising correctness. These ...