PRESBURGER ARITHMETIC, RATIONAL GENERATING FUNCTIONS, AND QUASI-POLYNOMIALS
PRESBURGER ARITHMETIC, RATIONAL GENERATING FUNCTIONS, AND QUASI-POLYNOMIALS
复制标题
预汉堡算术、有理生成函数和拟多项式
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Kevin M. Woods
中科院分区：
文献类型：
--
作者：
Kevin M. Woods
Presburger算术是自然数的一阶加法理论（但没有乘法）。我们的特点集，可以定义的Presburger公式，正是集的特征函数可以表示的有理生成函数，这样的集的几何特征也给出了。此外，如果p =（p1，. . .，pn）是Presburger公式中自由变量的一个子集，我们可以定义一个计数函数g（p）为该公式的解的个数，对于给定的p，我们证明了这样得到的每一个计数函数都可以等价地表示为分段拟多项式或有理母函数.最后，我们将已知的计算复杂性结果转化为这种设置，并讨论开放的方向。
Abstract Presburger arithmetic is the first-order theory of the natural numbers with addition (but no multiplication). We characterize sets that can be defined by a Presburger formula as exactly the sets whose characteristic functions can be represented by rational generating functions; a geometric characterization of such sets is also given. In addition, if p = (p1, . . . , pn) are a subset of the free variables in a Presburger formula, we can define a counting function g(p) to be the number of solutions to the formula, for a given p. We show that every counting function obtained in this way may be represented as, equivalently, either a piecewise quasi-polynomial or a rational generating function. Finally, we translate known computational complexity results into this setting and discuss open directions.