PURRS

Home

Documentation

Download

Credits

Mailing Lists

Links

Bibliography

Here are some fundamental papers you may want to read.
The corresponding BibTeX source is also available.

[AO83] L. M. Adelman and A. M. Odlyzko. Irreducibility testing and factorization of polynomials. Mathematics of Computation, 41:699-709, 1983.
[Apo75] T. M. Apostol. Introduction to Analytic Number Theory. Springer-Verlag, Berlin, 1975.
[BP+05] R. Bagnara, , A. Pescetti, A. Zaccagnini, and E. Zaffanella. Purrs: Towards computer algebra support for fully automatic worst-case complexity analysis. Technical report, 2005.
Fully automatic worst-case complexity analysis has a number of applications in computer-assisted program manipulation. A classical and powerful approach to complexity analysis consists in formally deriving, from the program syntax, a set of constraints expressing bounds on the resources required by the program, which are then solved, possibly applying safe approximations. In several interesting cases, these constraints take the form of recurrence relations. While techniques for solving recurrences are known and implemented in several computer algebra systems, these do not completely fulfill the needs of fully automatic complexity analysis: they only deal with a somewhat restricted class of recurrence relations, or sometimes require user intervention, or they are restricted to the computation of exact solutions that are often so complex to be unmanageable, and thus useless in practice. In this paper we briefly describe PURRS, a system and software library aimed at providing all the computer algebra services needed by applications performing or exploiting the results of worst-case complexity analyses. The capabilities of the system are illustrated by means of examples derived from the analysis of programs written in a domain-specific functional programming language for real-time embedded systems.

[BZZ03] R. Bagnara, A. Zaccagnini, and T. Zolo. The automatic solution of recurrence relations. I. Linear recurrences of finite order with constant coefficients. Quaderno 334, Dipartimento di Matematica, Università di Parma, Italy, 2003. Available at http://www.cs.unipr.it/Publications/.
We describe algorithmic techniques for the efficient solution of a wide class of linear recurrences of finite order with constant coefficients. We give an outline of the underlying theory both from an abstract and a more concrete point of view, in an attempt to convey the general principles as clearly as possible yet providing a well marked path for the implementation. In particular, the presentation is thorough and reasonably self-contained, covering topics such as the automatic solution of polynomial equations and efficient, exact symbolic summation of some special functions.

[BZZ07a] R. Bagnara, A. Zaccagnini, and T. Zolo. The automatic solution of recurrence relations. II. “Divide et Impera” recurrences. Quaderno, Dipartimento di Matematica, Università di Parma, Italy, 2007. To appear.
[BZZ07b] R. Bagnara, A. Zaccagnini, and T. Zolo. The automatic solution of recurrence relations. III. Approximate solutions. Quaderno, Dipartimento di Matematica, Università di Parma, Italy, 2007. To appear.
[BZZ07c] R. Bagnara, A. Zaccagnini, and T. Zolo. The automatic solution of recurrence relations. IV. Linear recurrences of finite order with variable coefficients. Quaderno, Dipartimento di Matematica, Università di Parma, Italy, 2007. In preparation.
[BZ04] R. Bagnara and A. Zaccagnini. Checking and bounding the solutions of some recurrence relations. Quaderno 344, Dipartimento di Matematica, Università di Parma, Italy, 2004. Available at http://www.cs.unipr.it/Publications/.
Recurrence relations play an important role in the field of complexity analysis since complexity measures can often be elegantly expressed by systems of such relations. This justifies the interest in automatic, precise, efficient and correct systems able to solve or to approximate the solution of systems of recurrence relations. Assume such a system is built. Since closed-form solutions for recurrences of even modest complexity can be so big and complex to be unmanageable, how can confidence on such a system be gained? How can we quickly validate or perhaps disprove its results? And, in those cases where the exact solution is too complex to be of practical use, how can we trade precision for efficiency by approximating them from below and from above? We also concern ourselves with a problem related to the handling of sets of solutions of recurrence relations: how can we confine by means of a lower bound and an upper bound a set of such solutions? We provide some solutions to these problems where we are careful to rely, whenever possible, on fast integer computations and/or conditions that are easy to check in a completely automatic way. The ongoing experimental evaluation of these ideas is giving very promising results, showing order-of-magnitude speedups over the more traditional methods.

[Ben01] R. Benzinger. Automated complexity analysis of Nuprl extracted programs. Journal of Functional Programming, 11(1):3-31, 2001.
This paper describes the Automated Complexity Analysis Prototype (ACAp) system for automated complexity analysis of functional programs synthesized with the Nuprl proof development system. We define a simple abstract cost model for Nuprl's term language based on the current call-by-name evaluator. The framework uses abstract functions and abstract lists to facilitate reasoning about primitive recursive programs with first-order functions, lazy lists, and a subclass of higher-order functions. The ACAp system automatically derives upper bounds on the time complexity of Nuprl extracts relative to a given profiling semantics. Analysis proceeds by abstract interpretation of the extract, where symbolic evaluation rules extend standard evaluation to terms with free variables. Symbolic evaluation of recursive programs generates systems of multi-variable difference equations, which are solved using the Mathematica computer algebra system. The use of the system is exemplified by analyzing a proof extract that computes the maximum segment sum of a list and a functional program that determines the minimum of a list via sorting. For both results, we compare call-by-name to call-by-value evaluation.

[Ben04] R. Benzinger. Automated higher-order complexity analysis. Theoretical Computer Science, 318(1-2):79-103, 2004.
This paper describes the automated complexity analysis (ACA) system for automated higher-order complexity analysis of functional programs synthesized with the NImage proof development system. We introduce a general framework for defining models of computational complexity for functional programs based on an annotation of a given operational language semantics. Within this framework, we use type decomposition and polynomialization to express the complexity of higher-order terms. Symbolic interpretation of open terms automates complexity analysis, which involves generating and solving higher-order recurrence equations. Finally, the use of the ACA system is demonstrated by analyzing three different implementations of the pigeonhole principle.

[BT84] B. L. Burrows and R. F. Talbot. Sums of powers of integers. American Mathematical Monthly, 91(7):394-403, 1984.
[Cas57] J. W. S. Cassels. An Introduction to Diophantine Approximation. Cambridge University Press, Cambridge, UK, 1957.
[Cel84] P. Celis. Remark: Corrections and errors in John Ivie's some MACSYMA programs for solving recurrence relations. ACM Transactions on Mathematical Software, 10(4):477-478, 1984. See [Ivi78].
[Cha68] K. Chandrasekharan. Introduction to Analytic Number Theory. Springer-Verlag, Berlin, 1968.
[Chi79] L. Childs. A Concrete Introduction to Higher Algebra. Springer-Verlag, Berlin, 1979.
[CK77] J. Cohen and J. Katcoff. Symbolic solution of finite-difference equations. ACM Transactions on Mathematical Software, 3(3):261-271, 1977.
An interactive computer program which has some capability for solving systems of finite difference equations is described. Although this capability is limited to linear systems, a knowledgeable user can, with the help of the program, solve a wider class of equations. Over 100 examples, covering a variety of cases, have been solved by using the program. Some representative examples are presented. Additional features which would improve the versatility of the program are also discussed.

[Edw86] A. W. F. Edwards. A quick route to sums of powers. American Mathematical Monthly, 93(6):451-455, 1986.
[GKP89] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. A Foundation for Computer Science. Addison-Wesley, Reading, MA, 1989.
[HW79] G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Oxford University Press, London, UK, 1979. Fifth Edition.
[Imm84] G. K. Immink. Asymptotics of Analytic Difference Equations, volume 1085 of Lecture Notes in Computer Mathematics. Springer-Verlag, Berlin, 1984.
[Ivi78] J. Ivie. Some MACSYMA programs for solving recurrence relations. ACM Transactions on Mathematical Software, 4(1):24-33, 1978. See also [Cel84].
A set of programs to find closed-form solutions to recurrence relations is described. These programs are written in the MACSYMA programming language, a LISP-based system implemented at the Massachusetts Institute of Technology on the PDP-10 mc computer. Single variable recurrence relations with constant coefficients are solved as well as some variable coefficient recurrences. The use of these programs is illustrated with several examples taken from textbooks.

[KP91] W. G. Kelley and A. C. Peterson. Difference Equations. An Introduction with Applications. Academic Press, New York, 1991.
[LJL82] A. Lenstra, H. Lenstra Jr., and L. Lovasz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515-534, 1982.
[Lev70] L. S. Levy. Summation of the series 1n+2n+...+xn using elementary calculus. American Mathematical Monthly, 77:840-847, 1970. See also [Lev71].
[Lev71] L. S. Levy. Corrigendum. American Mathematical Monthly, 78:987, 1971. See also [Lev70].
[Lue80] G. S. Lueker. Some techniques for solving recurrences. ACM Computing Surveys, 12(4):419-436, 1980.
Some techniques for solving recurrences are presented, along with examples of how these recurrences arise in the analysis of algorithms. In addition, probability generating functions are discussed and used to analyze problems in computer science.

[MS99] M. Mignotte and D. Stefānescu. Polynomials. An Algorithmic Approach. Springer-Verlag, Berlin, 1999.
[Pes04] A. Pescetti. L'algoritmo di Zeilberger per la risoluzione automatica di ricorrenze. M.Sc. dissertation, University of Parma, October 2004. In Italian.
[PWZ96] M. Petkovšek, H. S. Wilf, and D. Zeilberger. A=B. A. K. Peters, Natick, MA, 1996.
[Rou01] S. Roura. Improved master theorems for divide-and-conquer recurrences. Journal of the ACM, 48(2):170-205, 2001.
This paper presents new theorems to analyze divide-and-conquer recurrences, which improve other similar ones in several aspects. In particular, these theorems provide more information, free us almost completely from technicalities like floors and ceilings, and cover a wider set of toll functions and weight distributions, stochastic recurrences included.

[SP95] N. J. A. Sloane and S. Plouffe. The Encyclopedia of Integer Sequences. Academic Press, New York, 1995.
[OEI10] The on-line encyclopedia of integer sequences. Published electronically at http://oeis.org, 2010.
[Tit88] E. C. Titchmarsh. The Theory of Functions. Oxford University Press, London, UK, 1988.
[VH04] P. B. Vasconcelos and K. Hammond. Inferring cost equations for recursive, polymorphic and higher-order functional programs. In P. Trinder, G. Michaelson, and R. Peña, editors, Implementation of Functional Languages: 15th International Workshop, IFL 2003, Edinburgh, UK, September 8-11, 2003. Revised Papers, volume 3145 of Lecture Notes in Computer Science, pages 86-101. Springer-Verlag, Berlin, 2004.
This paper presents a type-based analysis for inferring size- and cost-equations for recursive, higher-order and polymorphic functional programs without requiring user annotations or unusual syntax. Our type reconstruction algorithm is capable of inferring first-order cost equations for a non-trivial subset of higher-order, recursive and polymorphic functions. We illustrate the approach with reference to some standard examples of recursive programs.

[Wei] E. W. Weisstein. The world of mathematics. http://mathworld.wolfram.com/.
[Wil94] H. S. Wilf. Generatingfunctionology. Academic Press, New York, 1994.

This file was generated by

[Page last updated on December 03, 2012, 08:34:47.]

© Roberto Bagnara

Home | Documentation | Download | Credits | Mailing Lists | Links