The complexity of Presburger arithmetic with bounded quantifier alternation depth

DOI10.1016/0304-3975(82)90115-3MaRDI QIDQ1163534zbMATH OpenOpenAlexFDO

Authors Martin Fürer

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)

Cites work

• A Bound on Solutions of Linear Integer Equalities and Inequalities
• A Decision Procedure for the First Order Theory of Real Addition with Order
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• scientific article; zbMATH DE number 3685448 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3534486 (Why is no real title available?)
• scientific article; zbMATH DE number 3032896 (Why is no real title available?)
• Presburger arithmetic with bounded quantifier alternation
• The complexity of logical theories
• Theory of Formal Systems. (AM-47)

Cited in

(18)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1163534)