PURRS

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:699709, 1983.

[Apo75]

T. M. Apostol.
Introduction to Analytic Number Theory.
SpringerVerlag, Berlin, 1975.

[BP^{+}05]

R. Bagnara, , A. Pescetti, A. Zaccagnini, and E. Zaffanella.
Purrs: Towards computer algebra support for fully automatic
worstcase complexity analysis.
Technical report, 2005.
Fully automatic worstcase complexity analysis has a
number of applications in computerassisted 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 worstcase complexity
analyses. The capabilities of the system are
illustrated by means of examples derived from the
analysis of programs written in a domainspecific
functional programming language for realtime 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
selfcontained, 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
closedform 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 orderofmagnitude speedups over the
more traditional methods.

[Ben01]

R. Benzinger.
Automated complexity analysis of Nuprl extracted programs.
Journal of Functional Programming, 11(1):331, 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 callbyname evaluator. The framework uses
abstract functions and abstract lists to facilitate
reasoning about primitive recursive programs with
firstorder functions, lazy lists, and a subclass of
higherorder 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 multivariable 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 callbyname to
callbyvalue evaluation.

[Ben04]

R. Benzinger.
Automated higherorder complexity analysis.
Theoretical Computer Science, 318(12):79103, 2004.
This paper describes the automated complexity
analysis (ACA) system for automated higherorder
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 higherorder terms. Symbolic
interpretation of open terms automates complexity
analysis, which involves generating and solving
higherorder 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):394403, 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):477478,
1984.
See [Ivi78].

[Cha68]

K. Chandrasekharan.
Introduction to Analytic Number Theory.
SpringerVerlag, Berlin, 1968.

[Chi79]

L. Childs.
A Concrete Introduction to Higher Algebra.
SpringerVerlag, Berlin, 1979.

[CK77]

J. Cohen and J. Katcoff.
Symbolic solution of finitedifference equations.
ACM Transactions on Mathematical Software, 3(3):261271, 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):451455, 1986.

[GKP89]

R. L. Graham, D. E. Knuth, and O. Patashnik.
Concrete Mathematics. A Foundation for Computer Science.
AddisonWesley, 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.
SpringerVerlag, Berlin, 1984.

[Ivi78]

J. Ivie.
Some MACSYMA programs for solving recurrence relations.
ACM Transactions on Mathematical Software, 4(1):2433, 1978.
See also [Cel84].
A set of programs to find closedform solutions to
recurrence relations is described. These programs
are written in the MACSYMA programming language,
a LISPbased system implemented at the Massachusetts
Institute of Technology on the PDP10 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):515534, 1982.

[Lev70]

L. S. Levy.
Summation of the series 1^{n}+2^{n}+...+x^{n} using elementary
calculus.
American Mathematical Monthly, 77:840847, 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):419436, 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.
SpringerVerlag, 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 divideandconquer recurrences.
Journal of the ACM, 48(2):170205, 2001.
This paper presents new theorems to analyze
divideandconquer 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 online 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 higherorder
functional programs.
In P. Trinder, G. Michaelson, and R. Peña, editors,
Implementation of Functional Languages: 15th International Workshop, IFL
2003, Edinburgh, UK, September 811, 2003. Revised Papers, volume 3145 of
Lecture Notes in Computer Science, pages 86101. SpringerVerlag,
Berlin, 2004.
This paper presents a typebased analysis for inferring
size and costequations for recursive, higherorder and
polymorphic functional programs without requiring user
annotations or unusual syntax. Our type reconstruction
algorithm is capable of inferring firstorder cost
equations for a nontrivial subset of higherorder,
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.]
