The complexity of Presburger arithmetic with bounded quantifier alternation depth

DOI10.1016/0304-3975(82)90115-3zbMath0484.03003OpenAlexW1992963060MaRDI QIDQ1163534

Martin Fuerer

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90115-3

zbMATH Keywords

decision problem for first order theories

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (18)

Complexity of Subcases of Presburger Arithmetic ⋮ The complexity of linear problems in fields ⋮ Complexity of Presburger arithmetic with fixed quantifier dimension ⋮ Short Presburger Arithmetic Is Hard ⋮ The complexity of query evaluation in indefinite temporal constraint databases ⋮ Subclasses of Presburger arithmetic and the polynomial-time hierarchy ⋮ Dominoes and the complexity of subclasses of logical theories ⋮ Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials ⋮ Automatic verification of recursive procedures with one integer parameter. ⋮ Classifying the computational complexity of problems ⋮ A uniform method for proving lower bounds on the computational complexity of logical theories ⋮ Proof synthesis and reflection for linear arithmetic ⋮ Limit, logic, and computation ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ The complexity of almost linear diophantine problems ⋮ A complete and terminating approach to linear integer solving ⋮ Sentences over integral domains and their computational complexities ⋮ Simple sentences that are hard to decide

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of logical theories
• Theory of Formal Systems. (AM-47)
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• A Decision Procedure for the First Order Theory of Real Addition with Order
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Presburger arithmetic with bounded quantifier alternation

This page was built for publication: The complexity of Presburger arithmetic with bounded quantifier alternation depth