Complexity of Subcases of Presburger Arithmetic

DOI10.2307/1999283zbMath0548.03018OpenAlexW4249272358MaRDI QIDQ3340842

Bruno Scarpellini

Publication date: 1984

Full work available at URL: https://doi.org/10.2307/1999283

zbMATH Keywords

Presburger arithmeticcomplexity of decidable theorieslower bounds for lengths of formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Quantifier elimination, model completeness, and related topics (03C10)

Related Items

A formal derivation of the decidability of the theory SA, Complexity of Presburger arithmetic with fixed quantifier dimension, Short Presburger Arithmetic Is Hard, Subclasses of Presburger arithmetic and the polynomial-time hierarchy, Dominoes and the complexity of subclasses of logical theories, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, A uniform method for proving lower bounds on the computational complexity of logical theories, On the virtue of categoricity, Proof synthesis and reflection for linear arithmetic, Target counting with Presburger constraints and its application in sensor networks, Decidable models of integer-manipulating programs with recursive parallelism, Decidable weighted expressions with Presburger combinators, Unnamed Item, The complexity of almost linear diophantine problems, Unnamed Item, Sentences over integral domains and their computational complexities, Unnamed Item, Unnamed Item, A Pattern Logic for Automata with Outputs, Simple sentences that are hard to decide, Lower bound results on lengths of second-order formulas

Cites Work

• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• NP-complete decision problems for binary quadratics
• The computational complexity of logical theories
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Presburger arithmetic with bounded quantifier alternation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item