The Automatic Solution of Recurrence Relations. I. Linear Recurrences of Finite Order with Constant Coefficients (TR)

Roberto Bagnara, Alessandro Zaccagnini, and Tatiana Zolo


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.

Available: PDF, 300 DPI, 600 DPI, and 1200 DPI PostScript, DVI, and BibTeX entry.

Series Foreword:

Complexity analysis aims at the derivation of upper and lower bounds to the complexity of algorithms, processes and data structures. The results of such analyses, which may be part or wholly automated, can be used, say, to decide whether mobile agents should be allowed to run in a given context, assist programmers in reasoning about the behavior of programs, guide applications of optimized program transformations, and discover efficiency bugs that are otherwise very difficult to detect.

Recurrence relations play an important role in the field of complexity analysis since complexity measures of, e.g., programs, can usually be very elegantly expressed by means of such relations. Therefore there is significant demand for efficient software systems capable of solving, with a high degree of precision, systems of recurrence relations. Moreover, to be really useful, the solvers need to be fully automatic, obtaining such solutions without human intervention.

Although the mathematical and computing literature describes several techniques and software for solving recurrences, these do not fulfill all of the above requirements; on the one hand, many of the methods assume interaction with a human operator and only deal with a rather restricted range of cases, while, on the other hand, the fully automated tools that are available only provide quite crude approximations of the exact solutions.

The PURRS project (Parma University's Recurrence Relation Solver, see http://www.cs.unipr.it/purrs/) is working at improving the state of the art in this field. The aim of the project is to create a software library that provides the services needed for efficiently computing the solution or an approximation of the solution of a system of recurrence relations that arise in performing fully automated complexity analysis.

Finding exact solutions and/or tight approximations in closed form in an acceptable timescale for a large class of recurrence relations is a challenging task; such an objective requires solutions to a host of unresolved theoretical and practical problems. The current series of papers is devoted to the presentation of all the mathematics behind the PURRS project. As our aim is to provide both rigor and thoroughness, the series will not only include original work but also accounts of known results, describing any useful extensions or modifications.

[Page last updated on August 18, 2003, 12:19:53.]

Page maintained by
Enea Zaffanella

Home | People | Projects | Publications | Seminars | Software | Links