Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-20T01:26:19.130Z Has data issue: false hasContentIssue false
  • English
  • Français

PRESBURGER ARITHMETIC, RATIONAL GENERATING FUNCTIONS, AND QUASI-POLYNOMIALS

Published online by Cambridge University Press:  22 April 2015

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

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.

Keywords

Ehrhart polynomialsgenerating functionsPresburger arithmeticquasi-polynomialscomputational complexity
Type
Articles
Information
The Journal of Symbolic Logic , Volume 80 , Issue 2 , June 2015 , pp. 433 - 449
Copyright
Copyright © The Association for Symbolic Logic 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Barvinok, Alexander, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Mathematics of Operations Research, vol. 19 (1994), no. 4, pp. 769–779.CrossRefGoogle Scholar
Barvinok, Alexander, A Course in Convexity, Graduate Studies in Mathematics, vol. 54, American Mathematical Society, Providence, RI, 2002.Google Scholar
Barvinok, Alexander, The complexity of generating functions for integer points in polyhedra and beyond, International Congress of Mathematicians. Vol. III, European Mathematical Society, Zürich, 2006, pp. 763–787.Google Scholar
Barvinok, Alexander and Pommersheim, James, An algorithmic theory of lattice points in polyhedra, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97), Mathematical Sciences Research Institute Publications, vol. 38, Cambridge University Press, Cambridge, 1999, pp. 91–147.Google Scholar
Barvinok, Alexander and Woods, Kevin, Short rational generating functions for lattice point problems. Journal of the American Mathematical Society, vol. 16 (2003), no. 4, pp. 957–979.CrossRefGoogle Scholar
Beck, Matthias, The partial-fractions method for counting solutions to integral linear systems. Discrete & Computational Geometry, vol. 32 (2004), no. 4, pp. 437–446.Google Scholar
Beck, Matthias and Robins, Sinai, Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, New York, 2007.Google Scholar
Berman, Leonard, The complexity of logical theories. Theoretical Computer Science, vol. 11 (1980), no. 1, pp. 57, 71–77.CrossRefGoogle Scholar
Blanco, Víctor, García-Sánchez, Pedro A., and Puerto, Justo, Counting numerical semigroups with short generating functions. International Journal of Algebra and Computation, vol. 21 (2011), no. 7, pp. 1217–1235.CrossRefGoogle Scholar
Boudet, Alexandre and Comon, Hubert, Diophantine equations, Presburger arithmetic and finite automata, Trees in algebra and programming—CAAP ’96 (Linköping, 1996), Lecture Notes in Computer Science, vol. 1059, Springer, Berlin, 1996, pp. 30–43.CrossRefGoogle Scholar
Brion, Michel, Points entiers dans les polyèdres convexes. Annales scientifiques de l’École Normale Supérieure, vol. 4 (1988), pp. 653–663.Google Scholar
Richard Büchi, J., Weak second-order arithmetic and finite automata. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
Cassels, J. W. S., An introduction to the geometry of numbers, Classics in Mathematics, Springer-Verlag, Berlin, 1997. Corrected reprint of the 1971 edition.Google Scholar
Clauss, Phillipe and Loechner, Vincent, Parametric analysis of polyhedral iteration spaces. Journal of VLSI Signal Processing, vol. 19 (1998), no. 2, pp. 179–194.Google Scholar
Cobham, Alan, On the base-dependence of sets of numbers recognizable by finite automata. Mathematical Systems Theory, vol. 3 (1969), pp. 186–192.CrossRefGoogle Scholar
Comon, Hubert and Jurski, Yan, Multiple counters automata, safety analysis and Presburger arithmetic, Computer aided verification (Vancouver, BC, 1998), Lecture Notes in Computer Science, vol. 1427, Springer, Berlin, 1998, pp. 268–279.CrossRefGoogle Scholar
Cooper, D.C., Theorem proving in arithmetic without multiplication. Machine Intelligence, vol. 7 (1972), pp. 91–99.Google Scholar
D’alessandro, Flavio, Intrigila, Benedetto, and Varricchio, Stefano, Quasi-polynomials, linear Diophantine equations and semi-linear sets. Theoretical Computer Science, vol. 416 (2012), pp. 1–16.CrossRefGoogle Scholar
Davis, Martin, Hilbert’s tenth problem is unsolvable. American Mathematical Monthly, vol. 80 (1973), pp. 233–269.Google Scholar
De Loera, Jesus, Haws, David, Hemmecke, Raymond, Huggins, Peter, Sturmfels, Bernd, and Yoshida, Ruriko, Short rational functions for toric algebra and applications. Journal of Symbolic Computation, vol. 38 (2004), no. 2, pp. 959–973.Google Scholar
Ehrhart, Eugène, Sur les polyèdres rationnels homothétiques à n dimensions. Comptes rendus de l’Académie des sciences Paris, vol. 254 (1962), pp. 616–618.Google Scholar
Ferrante, Jeanne and Rackoff, Charles W., The computational complexity of logical theories, Lecture Notes in Mathematics, vol. 718, Springer, Berlin, 1979.Google Scholar
Fischer, Michael and Rabin, Michael, Super-exponential complexity of Presburger arithmetic, Complexity of computation (Proceedings of SIAM-AMS symposium, New York, 1973), American Mathematical Society, Providence, R.I, 1974, pp. 27–41. SIAM-AMS Proceedings, Vol. VII.Google Scholar
Fulton, William, Introduction to Toric Varieties, Annals of Mathematics Studies, vol. 131, Princeton University Press, Princeton, NJ, 1993.Google Scholar
Fürer, Martin, The complexity of Presburger arithmetic with bounded quantifier alternation depth. Theoretical Computer Science, vol. 18 (1982), no. 1, pp. 105–111.Google Scholar
Ginsburg, Seymour and Spanier, Edwin, Semigroups, Presburger formulas and languages. Pacific Journal of Mathematics, vol. 16 (1966), no. 2, pp. 285–296.Google Scholar
Gödel, Kurt, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I. Monatshefte für Mathematik, vol. 149 (2006), no. 1, pp. 1–30. Reprinted from Monatshefte für Mathematik und Physik. 38(1931), 173–198. With an introduction by Sy-David Friedman.Google Scholar
Grädel, Erich, Subclasses of Presburger arithmetic and the polynomial-time hierarchy. Theoretical Computer Science, vol. 56 (1988), no. 3, pp. 289–301.Google Scholar
Grädel, Erich, Dominoes and the complexity of subclasses of logical theories. Annals of Pure and Applied Logic, vol. 43 (1989), no. 1, pp. 1–30.Google Scholar
Guo, Alan and Miller, Ezra, Lattice point methods for combinatorial games. Advances in Applied Mathematics, vol. 46 (2011), no. 1–4, pp. 363–378.CrossRefGoogle Scholar
Haase, Christoph, Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy, Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (CSL/LICS’14), ACM Press, Vienna, Austria, 2014.Google Scholar
Hoşten, Serkan and Sturmfels, Bernd, Computing the integer programming gap. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, vol. 27 (2007), no. 3, pp. 367–382.Google Scholar
Kannan, Ravi, Test sets for integer programs, ∀∃ sentences, Polyhedral combinatorics (Morristown, NJ, 1989), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 1, American Mathematical Society, Providence, RI, 1990, pp. 39–47.Google Scholar
Klaedtke, Felix, Bounds on the automata size for Presburger arithmetic. ACM Transactions on Computational Logic, vol. 9 (2008), no. 2, pp. Art. 11, 34.Google Scholar
Lenstra, Hendrik Jr., Integer programming with a fixed number of variables. Mathematics of Operations Research, vol. 8 (1983), no. 4, pp. 538–548.Google Scholar
Matousek, Jiri, Lectures on Discrete Geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002.Google Scholar
Miller, Ezra and Sturmfels, Bernd, Combinatorial commutative algebra, Graduate Texts in Mathematics, vol. 227, Springer-Verlag, New York, 2005.Google Scholar
Oppen, Derek, A superexponential upper bound on the complexity of Presburger arithmetic. Journal of Computer and System Sciences, vol. 16 (1978), no. 3, pp. 323–332.Google Scholar
Parker, Erin and Chatterjee, Siddhartha, An automata-theoretic algorithm for counting solutions to Presburger formulas, Compiler construction, Springer, 2004, pp. 104–119.Google Scholar
Presburger, Mojżesz, On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation, History and Philosophy of Logic, vol. 12 (1991), no. 2, pp. 225–233. Translated from the German and with commentaries by Dale Jacquette.CrossRefGoogle Scholar
Pugh, William, Counting solutions to Presburger formulas: how and why. SIGPLAN Notices, vol. 29 (1994), no. 6, pp. 121–134.CrossRefGoogle Scholar
Ramírez Alfonsín, J. L., The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications, vol. 30, Oxford University Press, Oxford, 2005.Google Scholar
Reddy, Cattamanchi R and Loveland, Donald W, Presburger arithmetic with bounded quantifier alternation, Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, ACM, 1978, pp. 320–325.Google Scholar
Scarf, Herbert, Test sets for integer programs. Mathematical Programming, vol. 79 (1997), no. 1–3, Series B, pp. 355–368.Google Scholar
Scarpellini, Bruno, Complexity of subcases of Presburger arithmetic. Transactions of the American Mathematical Society, vol. 284 (1984), no. 1, pp. 203–218.Google Scholar
Schöning, Uwe, Complexity of Presburger arithmetic with fixed quantifier dimension. Theory of Computing Systems, vol. 30 (1997), no. 4, pp. 423–428.Google Scholar
Schrijver, Alexander, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons Ltd., Chichester, 1986.Google Scholar
Schrijver, Alexander, Combinatorial optimization. Polyhedra and efficiency, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003.Google Scholar
Stanley, Richard P., Decompositions of rational convex polytopes, Annals of Discrete Mathematics, vol. 6 (1980), pp. 333–342.CrossRefGoogle Scholar
Sturmfels, Bernd, On vector partition functions. Journal of Combinatorial Theory, Series A, vol. 72 (1995), no. 2, pp. 302–309.Google Scholar
Sturmfels, Bernd, Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996.Google Scholar
Thomas, Rekha, A geometric Buchberger algorithm for integer programming. Mathematics of Operations Research, vol. 20 (1995), no. 4, pp. 864–884.CrossRefGoogle Scholar
Thomas, Rekha, The structure of group relaxations, Handbooks in Operations Research and Management Science, vol. 12, Elsevier, Amsterdam, 2005, pp. 123–170.Google Scholar
Verdoolaege, Sven and Woods, Kevin, Counting with rational generating functions. Journal of Symbolic Computation, vol. 43 (2008), no. 2, pp. 75–91.Google Scholar
Wolper, Pierre and Boigelot, Bernard, An automata-theoretic approach to Presburger arithmetic constraints, Static analysis, 2nd international symposium, Lecture Notes in Computer Science, vol. 983, Springer, Berlin, 1995, pp. 21–32.Google Scholar
Woods, Kevin, Rational generating functions and lattice point sets, Ph.D. thesis, University of Michigan, Ann Arbor, 2004.Google Scholar