Subclasses of Presburger arithmetic and the polynomial-time hierarchy

DOI10.1016/0304-3975(88)90136-3zbMath0665.03026OpenAlexW2082494602MaRDI QIDQ1115858

Erich Grädel

Publication date: 1988

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

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

zbMATH Keywords

NP-completecomplexity of subclasses of Presburger arithmetic

Mathematics Subject Classification ID

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

Related Items (12)

Dominoes and the complexity of subclasses of logical theories ⋮ Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials ⋮ The Computational Complexity of Integer Programming with Alternations ⋮ Parametric Presburger arithmetic: complexity of counting and quantifier elimination ⋮ State-based opacity of labeled real-time automata ⋮ Automatic verification of recursive procedures with one integer parameter. ⋮ On Presburger arithmetic extended with non-unary counting quantifiers ⋮ Model checking parameterized asynchronous shared-memory systems ⋮ Proof synthesis and reflection for linear arithmetic ⋮ Towards efficient verification of population protocols ⋮ Detectability of labeled weighted automata over monoids ⋮ Decision problems among the main subfamilies of rational relations

Cites Work

• The complexity of logical theories
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• The computational complexity of logical theories
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Integer Programming with a Fixed Number of Variables
• Complexity of Subcases of Presburger Arithmetic
• Alternation
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Presburger arithmetic with bounded quantifier alternation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Subclasses of Presburger arithmetic and the polynomial-time hierarchy