Rational generating functions and lattice point sets.
Rational generating functions and lattice point sets.
复制标题
有理生成函数和格点集。
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Kevin M. Woods
中科院分区：
文献类型：
--
作者：
Kevin M. Woods
有理生成函数和格点集作者：Alexander Barvinok我们证明，对于任何固定的d，存在一个多项式时间算法来计算d维多面体中的整点集的任何投影的生成函数。这意味着许多有趣的整点集可以被编码为短的有理生成函数，例如由给定的正整数、仿射半群、邻域和邻域复形(也称为围巾复形或极大无格体的复形)、Hilbert基和来自代数整数规划的集合组成的所有非负整数组合的Frobenius半群。我们还展示了如何使用母函数在多项式时间内解决计算问题(如求集合的基数或求其最大元素)。我们还可以利用这个定理来计算由单项式生成的环的希尔伯特级数，作为一个短的有理函数。我们研究了生成函数和邻域复形之间的联系，并考虑了改进主要定理的算法的可能性。最后，我们考察了有理生成函数与Presburger算法的复杂性之间的关系。
Rational Generating Functions and Lattice Point Sets by Kevin M. Woods Chair: Alexander Barvinok We prove that, for any fixed d, there is a polynomial time algorithm for computing the generating function of any projection of the set of integer points in a d-dimensional polytope. This implies that many interesting sets of integer points can be encoded as short rational generating functions, such as the Frobenius semigroup of all nonnega- tive integer combinations of given positive integers, affine semigroups, neighbors and the neighborhood complex (also known as the Scarf complex or complex of maximal lattice-free bodies), Hilbert bases, and sets from algebraic integer programming. We also show how to use the generating functions to solve computational problems (such as finding the cardinality of the set or finding its maximum element) in polynomial time. We may also use this theorem to compute, as a short rational function, the Hilbert series of rings generated by monomials. We examine the connection between generating functions and the neighborhood complex, and we consider possibilities for improving the algorithm for the main theorem. Finally, we examine the relationship between rational generating functions and the complexity of Presburger arithmetic.