Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials
From MaRDI portal
Publication:5327451
DOI10.1007/978-3-642-39212-2_37zbMath1335.03062arXiv1211.0020OpenAlexW1932285788MaRDI QIDQ5327451
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
computational complexitygenerating functionsPresburger arithmeticEhrhart polynomialsquasi-polynomials
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
