Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T00:58:29.031Z Has data issue: false hasContentIssue false

PRESBURGER ARITHMETIC, RATIONAL GENERATING FUNCTIONS, AND QUASI-POLYNOMIALS

Published online by Cambridge University Press:  22 April 2015

KEVIN WOODS*
Affiliation:
DEPARTMENT OF MATHEMATICS OBERLIN COLLEGE OBERLIN, OHIO 44074, USAE-mail: Kevin.Woods@oberlin.eduURL: http://www.oberlin.edu/faculty/kwoods/
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2015