Mellin transforms and asymptotics: Harmonic sums
Ph. Flajolet, X. Gourdon, P. Dumas 3--58
Constructible differentially finite algebraic series in
several variables
F. Bergeron, U. Sattler 59--65
Marking in combinatorial constructions: Generating functions
and limiting distributions
M. Drmota, M. Soria 67--99
Mellin transforms and asymptotics: Finite differences and
Rice's integrals
Ph. Flajolet, R. Sedgewick 101--124
Dynamic analysis of some relational databases parameters
D. Gardy, G. Louchard 125--159
Asymptotic behavior of the Lempel--Ziv parsing scheme and
digital search trees
P. Jacquet, W. Szpankowski 161--197
Analysis of an optimized search algorithm for skip lists
P. Kirschenhofer, C. Mart\'{\i }nez, H. Prodinger 199--220
Probabilistic analysis of bucket recursive trees
H.M. Mahmoud, R.T. Smythe 221--249
On the variance of a class of inductive valuations of data
structures for digital search
W. Schachinger 251--275
Random trees in queueing systems with deadlines
U. Schmid 277--314
Forword from H. Prodinger and W. Szpankowski
This special issue is devoted to
the it Mathematical Analysis of Algorithms. This area
was started by D.E. Knuth almost 30 years ago
in his series of books it The Art of Computer Programming in order
to understand behaviors of algorithms from a quantitative point of view
(i.e., on average, in probability, etc.).
Unfortunately, this area of research and scientific activity
never had a "home".
Only in July 1993, the first seminar entirely
devoted to it took place in Dagstuhl, Germany.
The next seminar will be again in 1995.
The present special issue is an attempt to have a representative
collection of relevant research papers in one volume. In our Call for
Papers we have asked for articles
"in any area of theoretical computer science that
is using analytical, probabilistic or combinatorial methods".
Our goal was to prepare a volume containing research papers
having a reasonable amount of
generality in order to serve as an introduction and motivation for
an "average" reader. We have received more excellent
papers than we could include
in this issue, and some of them had to be re-directed
to regular issues of this journal.
Philippe Flajolet has kindly agreed to write an Invited Paper
surveying the applications of the Mellin transform in the analysis
of algorithms. This topic was started by D.E. Knuth (inspired by N.G. de Bruijn)
and proved to be extremely useful and important. Thanks to Flajolet
and his coauthors this method has become an essential and widely
used tool for researchers in this area.
We are very grateful to M. Nivat, the Editor-in-Chief of
Theoretical Computer Science for having given us the opportunity
to be Guest Editors of this special issue. Thanks are also due to Philippe
Flajolet for his assistance during the preparation of this issue,
as well as to the contributors and the referees
for their dedicated efforts. Finally, we appreciate
the help we have received from the staff of Elsevier,
especially Dr. J.-W.M. Kok.
We hope that the readers find this issue interesting and
useful in their scientific endeavors.
We dedicate this issue to D.E. Knuth, the founding father of the analytical (precise) analysis of algorithms.
(Back to List of Papers)