Quasi-polynomials, linear Diophantine equations and semi-linear sets

DOI10.1016/j.tcs.2011.10.014zbMath1253.11042OpenAlexW2089841370MaRDI QIDQ764313

Stefano Varricchio, Flavio D'Alessandro, Benedetto Intrigila

Publication date: 13 March 2012

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.10.014

zbMATH Keywords

semi-linear setsquasi-polynomialssystems of linear Diophantine equations

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Algebraic theory of languages and automata (68Q70) Linear Diophantine equations (11D04)

Related Items

Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials ⋮ D-finite multivariate series with arithmetic restrictions on their coefficients ⋮ On the Commutative Equivalence of Algebraic Formal Series and Languages ⋮ On bounded linear codes and the commutative equivalence ⋮ On the commutative equivalence of bounded context-free and regular languages: the code case ⋮ On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\) ⋮ On the commutative equivalence of bounded context-free and regular languages: the semi-linear case

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vector partition functions and generalized Dahmen and Micchelli spaces
• Topics in hyperplane arrangements, polytopes and box-splines
• The Parikh counting functions of sparse context-free languages are quasi-polynomials
• Remarks on piecewise-linear algebra
• Residue formulae for vector partitions and Euler-Maclaurin sums.
• Counting integer flows in networks
• On vector partition functions
• On the structure of the counting function of sparse context-free languages.
• The many aspects of counting lattice points in polytopes
• Semigroups, Presburger formulas, and languages
• Every semilinear set is a finite union of disjoint linear sets
• Rational sets in commutative monoids
• Computing the Continuous Discretely
• The Number of Solutions to Linear Diophantine Equations and Multivariate Splines
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• Convex Analysis
• Interpolated Denumerants and Lambert Series