Parametric Presburger arithmetic: complexity of counting and quantifier elimination

DOI10.1002/MALQ.201800068MaRDI QIDQ5108860zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 6 May 2020

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.00974, http://hdl.handle.net/2027.42/151911

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
• Bounding quantification in parametric expansions of Presburger arithmetic
• Complexity of Subcases of Presburger Arithmetic

Cites work

• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• A wild model of linear arithmetic and discretely ordered modules
• Geometry of continued fractions
• Hilbert's Tenth Problem is Unsolvable
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
• Quantifier elimination for modules with scalar variables
• Short rational generating functions for lattice point problems
• Subclasses of Presburger arithmetic and the polynomial-time hierarchy
• The unreasonable ubiquitousness of quasi-polynomials

Cited in

(7)

• Bounding quantification in parametric expansions of Presburger arithmetic
• scientific article; zbMATH DE number 1253963 (Why is no real title available?)
• Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
• A plethora of polynomials: a toolbox for counting problems
• Quantifier elimination for counting extensions of Presburger arithmetic
• Parametric Presburger Arithmetic: Complexity of Counting and Quantifier Elimination
• One-parametric Presburger arithmetic has quantifier elimination

This page was built for publication: Parametric Presburger arithmetic: complexity of counting and quantifier elimination

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