Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials

DOI10.1007/978-3-642-39212-2_37zbMath1335.03062arXiv1211.0020OpenAlexW1932285788MaRDI QIDQ5327451

Kevin M. Woods

Publication date: 7 August 2013

Published in: The Journal of Symbolic Logic, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.0020

zbMATH Keywords

computational complexitygenerating functionsPresburger arithmeticEhrhart polynomialsquasi-polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) First-order arithmetic and fragments (03F30)

Related Items (17)

Counting essential surfaces in \(3\)-manifolds ⋮ Period collapse in Ehrhart quasi-polynomials of \(\{1,3\}\)-graphs ⋮ Epsilon multiplicity for Noetherian graded algebras ⋮ A Plethora of Polynomials: A Toolbox for Counting Problems ⋮ Short Presburger Arithmetic Is Hard ⋮ The unreasonable ubiquitousness of quasi-polynomials ⋮ The Computational Complexity of Integer Programming with Alternations ⋮ Parametric Presburger arithmetic: complexity of counting and quantifier elimination ⋮ Quantifier elimination for counting extensions of Presburger arithmetic ⋮ Finitely generated saturated multi-Rees algebras ⋮ Enumerating Projections of Integer Points in Unbounded Polyhedra ⋮ Length of local cohomology of powers of ideals ⋮ Target counting with Presburger constraints and its application in sensor networks ⋮ COMPLEXITY OF SHORT GENERATING FUNCTIONS ⋮ Parametrizing an Integer Linear Program by an Integer ⋮ The parametric Frobenius problem ⋮ Sparse representation of vectors in lattices and semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lattice point methods for combinatorial games
• Quasi-polynomials, linear Diophantine equations and semi-linear sets
• On formally undecidable propositions of \textit{Principia Mathematica} and related systems. I. With an introductory comment by Sy-David Friedman
• Subclasses of Presburger arithmetic and the polynomial-time hierarchy
• Dominoes and the complexity of subclasses of logical theories
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• The computational complexity of logical theories
• Complexity of Presburger arithmetic with fixed quantifier dimension
• The partial-fractions method for counting solutions to integral linear systems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On vector partition functions
• Counting with rational generating functions
• Semigroups, Presburger formulas, and languages
• Short rational functions for toric algebra and applications
• Integer Programming with a Fixed Number of Variables
• COUNTING NUMERICAL SEMIGROUPS WITH SHORT GENERATING FUNCTIONS
• Weak Second‐Order Arithmetic and Finite Automata
• On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
• Decompositions of Rational Convex Polytopes
• Hilbert's Tenth Problem is Unsolvable
• Short rational generating functions for lattice point problems
• Subclasses of presburger arithmetic and the weak EXP hierarchy
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• A Geometric Buchberger Algorithm for Integer Programming
• On the base-dependence of sets of numbers recognizable by finite automata

This page was built for publication: Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials