Publications by Bruno Salvy

@article{BardetFaugereSalvySpaenlehauer2013,
    author      = {Bardet, Magali and Faug{\`e}re, Jean-Charles and Salvy,
  Bruno and Spaenlehauer, Pierre-Jean},
    title       = {On the Complexity of Solving Quadratic Boolean Systems},
    journal     = {Journal of Complexity},
    number      = {1},
    year        = {2013},
    month       = {February},
    volume      = {29},
    pages       = {53--75},
    doi         = {10.1016/j.jco.2012.07.001},
    arxiv       = {abs/1112.6263},
    abstract    = {A fundamental problem in computer science is to find all
  the common zeroes of $m$ quadratic polynomials in $n$ unknowns over ${F}_2$.
  The cryptanalysis of several modern ciphers reduces to this problem. Up to
  now, the best complexity bound was reached by an exhaustive search in
  $4\log_2 n\,2^n$ operations. We give an algorithm that reduces the problem to
  a combination of exhaustive search and sparse linear algebra. This algorithm
  has several variants depending on the method used for the linear algebra
  step. Under precise algebraic assumptions, we show that the deterministic
  variant of our algorithm has complexity bounded by $O(2^{0.841n})$ when
  $m=n$, while a probabilistic variant of the Las Vegas type has expected
  complexity $O(2^{0.792n})$. Experiments on random systems show that the
  algebraic assumptions are satisfied with probability very close to~1. We also
  give a rough estimate for the actual threshold between our method and
  exhaustive search, which is as low as~200, and thus very relevant for
  cryptographic applications.},
}

@inproceedings{BostanChowdhuryLebretonSalvySchost2012,
    author      = {Bostan, Alin and Chowdhury, Muhammad F. I. and Lebreton,
  Romain and Salvy, Bruno and Schost, {\'E}ric},
    title       = {Power Series Solutions of Singular (q)-Differential
  Equations},
    booktitle   = {ISSAC '12: Proceedings of the twenty-fifth International
  Symposium on Symbolic and Algebraic Computation},
    year        = {2012},
    editor      = {van Hoeij, Mark and Van der Hoeven, Joris},
    pages       = {107--114},
    arxiv       = {abs/1205.3414},
    abstract    = {We provide algorithms computing power series solutions of a
  large class of differential or $q$-differential equations or systems. Their
  number of arithmetic operations grows linearly with the precision, up to
  logarithmic terms.},
}

@inproceedings{BostanChyzakLiSalvy2012,
    author      = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Li, Ziming
  and Salvy, Bruno},
    title       = {Fast Computation of Common Left Multiples of Linear
  Ordinary Differential Operators},
    booktitle   = {ISSAC '12: Proceedings of the twenty-fifth International
  Symposium on Symbolic and Algebraic Computation},
    year        = {2012},
    editor      = {van Hoeij, Mark and van der Hoeven, Joris},
    pages       = {99--106},
    arxiv       = {abs/1205.0879},
    abstract    = {We study tight bounds and fast algorithms for LCLMs of
  several linear differential operators with polynomial coefficients. We
  analyze the arithmetic complexity of existing algorithms for LCLMs, as well
  as the size of their outputs. We propose a new algorithm that recasts the
  LCLM computation in a linear algebra problem on a polynomial matrix. This
  algorithm yields sharp bounds on the coefficient degrees of the LCLM,
  improving by one order of magnitude the best bounds obtained using previous
  algorithms. The complexity of the new algorithm is almost optimal, in the
  sense that it nearly matches the arithmetic size of the output.},
}

@techreport{BostanRaschelSalvy2012,
    author      = {Bostan, Alin and Raschel, Kilian and Salvy, Bruno},
    title       = {Non-{D}-finite excursions in the quarter plane},
    number      = {1205.3300},
    year        = {2012},
    institution = {arXiv},
    arxiv       = {abs/1205.3300},
    abstract    = {We prove that the sequence $(e^{\mathfrak{S}}_n)_{n\geq 0}$
  of excursions in the quarter plane corresponding to a nonsingular step set
  $\mathfrak{S}\subseteq{0,\pm 1}^2$ with infinite group does not satisfy any
  nontrivial linear recurrence with polynomial coefficients. Accordingly, in
  those cases, the trivariate generating function of the numbers of walks with
  given length and prescribed ending point is not D-finite. Moreover, we
  display the asymptotics of $e^{\mathfrak{S}}_n$.},
}

@article{PivoteauSalvySoria2012,
    author      = {Pivoteau, Carine and Salvy, Bruno and Soria, Mich{\`e}le},
    title       = {Algorithms for Combinatorial Structures: Well-founded
  systems and {N}ewton iterations},
    journal     = {Journal of Combinatorial Theory, Series A},
    year        = {2012},
    volume      = {119},
    institution = {arXiv},
    pages       = {1711--1773},
    keywords    = {Species theory; analytic combinatorics; generating series;
  complexity.},
    note        = {62 pages},
    doi         = {10.1016/j.jcta.2012.05.007},
    arxiv       = {abs/1109.2688},
    abstract    = {We consider systems of recursively defined combinatorial
  structures. We give algorithms checking that these systems are well founded,
  computing generating series and providing numerical values. Our framework is
  an articulation of the constructible classes of Flajolet and Sedgewick with
  Joyal's species theory. We extend the implicit species theorem to structures
  of size zero. A quadratic iterative Newton method is shown to solve
  well-founded systems combinatorially. From there, truncations of the
  corresponding generating series are obtained in quasi-optimal complexity.
  This iteration transfers to a numerical scheme that converges unconditionally
  to the values of the generating series inside their disk of convergence.
  These results provide important subroutines in random generation. Finally,
  the approach is extended to combinatorial differential systems.},
}

@misc{BoChLiSa11,
    author      = {Bostan, Alin and Chyzak, Frédéric and Li, Ziming
  and Salvy, Bruno},
    title       = {Fast computation of common left multiples of linear
  ordinary differential operators},
    journal     = {ACM Commun. Comput. Algebra},
    year        = {2011},
    month       = {July},
    publisher   = {ACM},
    volume      = {45},
    address     = {New York, NY, USA},
    howpublished= {Poster at ISSAC 2011},
    pages       = {111–112},
    doi         = {http://doi.acm.org/10.1145/2016567.2016581},
    url         = {http://doi.acm.org/10.1145/2016567.2016581},
}

@inproceedings{ChyzakDavenportKoutschanSalvy2011,
    author      = {Chyzak, Frédéric and Davenport, James H. and
  Koutschan, Christoph and Salvy, Bruno},
    title       = {On Kahan's Rules for Determining Branch Cuts},
    booktitle   = {SYNASC},
    year        = {2011},
    month       = {September},
    pages       = {47–51},
    note        = {13th International Symposium on Symbolic and Numeric
  Algorithms for Scientific Computing. September 26-29, 2011. Timisoara,
  Romania},
    arxiv       = {abs/1109.2809},
    url         = {http://arxiv.org/abs/1109.2809},
    abstract    = {In computer algebra there are different ways of approaching
  the mathematical concept of functions, one of which is by defining them as
  solutions of differential equations. We compare different such approaches and
  discuss the occurring problems. The main focus is on the question of
  determining possible branch cuts. We explore the extent to which the
  treatment of branch cuts can be rendered (more) algorithmic, by adapting
  Kahan's rules to the differential equation setting.},
}

@article{DumasFousseSalvy2011,
    author      = {Dumas, Jean-Guillaume and Fousse, Laurent and Salvy,
  Bruno},
    title       = {Simultaneous modular reduction and {K}ronecker substitution
  for small finite fields},
    journal     = {Journal of Symbolic Computation},
    number      = {7},
    year        = {2011},
    month       = {July},
    volume      = {46},
    pages       = {823--840},
    keywords    = {Compressed matrix multiplication},
    doi         = {10.1016/j.jsc.2010.08.015},
    abstract    = {We present algorithms to perform modular polynomial
  multiplication or a modular dot product efficiently in a single machine word.
  We use a combination of techniques. Polynomials are packed into integers by
  Kronecker substitution; several modular operations are performed at once with
  machine integer or floating point arithmetic; normalization of modular images
  is avoided when possible; some conversions back to polynomial coefficients
  are avoided; the coefficients are recovered efficiently by preparing them
  before conversion. We discuss precisely the required control on sizes and
  degrees. We then present applications to polynomial multiplication, prime
  field linear algebra and small extension field arithmetic, where these
  techniques lead to practical gains of quite large constant factors.},
}

@inproceedings{BenoitChyzakDarrasseGerholdMezzarobbaSalvy2010,
    author      = {Benoit, Alexandre and Chyzak, Fr{\'e}d{\'e}ric and
  Darrasse, Alexis and Gerhold, Stefan and Mezzarobba, Marc and Salvy, Bruno},
    title       = {The Dynamic Dictionary of Mathematical Functions
  ({DDMF})},
    booktitle   = {The Third International Congress on Mathematical Software
  (ICMS 2010)},
    year        = {2010},
    editor      = {Fukuda, Komei and van der Hoeven, Joris and Joswig, Michael
  and Takayama, Nobuki},
    volume      = {6327},
    series      = {Lecture Notes in Computer Science},
    pages       = {35--41},
    doi         = {10.1007/978-3-642-15582-6_7},
    abstract    = {We describe the main features of the Dynamic Dictionary of
  Mathematical Functions (version 1.5). It is a website consisting of
  interactive tables of mathematical formulas on elementary and special
  functions. The formulas are automatically generated by computer algebra
  routines. The user can ask for more terms of the expansions, more digits of
  the numerical values, or proofs of some of the formulas.},
}

@article{BostanSalvySchost2010,
    author      = {Bostan, Alin and Salvy, Bruno and Schost, {\'E}ric},
    title       = {Fast conversion algorithms for orthogonal polynomials},
    journal     = {Linear Algebra and its Applications},
    number      = {1},
    year        = {2010},
    month       = {January},
    volume      = {432},
    pages       = {249--258},
    doi         = {10.1016/j.laa.2009.08.002},
    arxiv       = {abs/0804.2373},
    abstract    = {We discuss efficient conversion algorithms for orthogonal
  polynomials. We describe a known conversion algorithm from an arbitrary
  orthogonal basis to the monomial basis, and deduce a new algorithm of the
  same complexity for the converse operation.},
}

@article{BostanSalvyTran2010,
    author      = {Bostan, Alin and Salvy, Bruno and Tran, Khang},
    title       = {Generating functions of {C}hebyshev-like polynomials},
    journal     = {International Journal of Number Theory},
    number      = {7},
    year        = {2010},
    volume      = {6},
    pages       = {1659--1667},
    doi         = {10.1142/S1793042110003691},
    arxiv       = {abs/0907.0291},
    abstract    = {In this short note, we give simple proofs of several
  results and conjectures formulated by Stolarsky and Tran concerning
  generating functions of some families of Chebyshev-like polynomials.},
}

@article{FlajoletGerholdSalvy2010,
    author      = {Flajolet, Philippe and Gerhold, Stefan and Salvy, Bruno},
    title       = {Lindelöf Representations and (Non-)Holonomic
  Sequences},
    journal     = {The Electronic Journal of Combinatorics},
    number      = {1},
    year        = {2010},
    volume      = {17},
    pages       = {1–28},
    arxiv       = {abs/0906.1957},
    url         = {http://www.combinatorics.org/Volume_17/PDF/v17i1r3.pdf},
    abstract    = {Various sequences that possess explicit analytic
  expressions can be analysed asymptotically through integral representations
  due to Lindelöf, which belong to an attractive but largely forgotten
  chapter of complex analysis. One of the outcomes of such analyses concerns
  the non-existence of linear recurrences with polynomial coefficients
  annihilating these sequences, and, accordingly, the non-existence of linear
  differential equations with polynomial coefficients annihilating their
  generating functions. In particular, the corresponding generating functions
  are transcendental. Asymptotics of certain finite difference sequences come
  out as a byproduct of our approach.},
}

@article{MezzarobbaSalvy2010,
    author      = {Mezzarobba, Marc and Salvy, Bruno},
    title       = {Effective Bounds for {P}-Recursive Sequences},
    journal     = {Journal of Symbolic Computation},
    number      = {10},
    year        = {2010},
    month       = {October},
    volume      = {45},
    pages       = {1075--1096},
    doi         = {10.1016/j.jsc.2010.06.024},
    arxiv       = {abs/0904.2452},
    abstract    = {We describe an algorithm that takes as input a complex
  sequence $(u_n)$ given by a linear recurrence relation with polynomial
  coefficients along with initial values, and outputs a simple explicit upper
  bound $(v_n)$ such that $|u_n| \leq v_n$ for all $n$. Generically, the bound
  is tight, in the sense that its asymptotic behaviour matches that of $u_n$.
  We discuss applications to the evaluation of power series with guaranteed
  precision.},
}

@article{SalvyShackell2010,
    author      = {Salvy, Bruno and Shackell, John},
    title       = {Measured limits and multiseries},
    journal     = {Journal of the London Mathematical Society},
    number      = {3},
    year        = {2010},
    volume      = {82},
    pages       = {747–762},
    doi         = {10.1112/jlms/jdq057},
    url         = {http://jlms.oxfordjournals.org/content/82/3/747},
    abstract    = {We introduce the notion of a measured limit and show how it
  can give meaning to asymptotic expansions in which the coefficients are
  variable and may even have poles. We give an algorithm for computing the
  measured multiseries of a large class of elementary functions.},
}

@inproceedings{BenoitSalvy2009,
    author      = {Benoit, Alexandre and Salvy, Bruno},
    title       = {Chebyshev Expansions for Solutions of Linear Differential
  Equations},
    booktitle   = {ISSAC '09: Proceedings of the twenty-second international
  symposium on Symbolic and algebraic computation},
    year        = {2009},
    editor      = {May, John},
    pages       = {23--30},
    doi         = {10.1145/1576702.1576709},
    arxiv       = {abs/0906.2888},
    abstract    = {A Chebyshev expansion is a series in the basis of Chebyshev
  polynomials of the first kind. When such a series solves a linear
  differential equation, its coefficients satisfy a linear recurrence equation.
  We interpret this equation as the numerator of a fraction of linear
  recurrence operators. This interpretation lets us give a simple view of
  previous algorithms, analyze their complexity, and design a faster one for
  large orders.},
}

@inproceedings{ChyzakKauersSalvy2009,
    author      = {Chyzak, Fr{\'e}d{\'e}ric and Kauers, Manuel and Salvy,
  Bruno},
    title       = {A Non-Holonomic Systems Approach to Special Function
  Identities},
    booktitle   = {ISSAC '09: Proceedings of the twenty-second international
  symposium on Symbolic and algebraic computation},
    year        = {2009},
    editor      = {May, John},
    pages       = {111--118},
    doi         = {10.1145/1576702.1576720},
    arxiv       = {abs/0904.2761},
    abstract    = {We extend Zeilberger's approach to special function
  identities to cases that are not holonomic. The method of creative
  telescoping is thus applied to definite sums or integrals involving Stirling
  or Bernoulli numbers, incomplete Gamma function or polylogarithms, which are
  not covered by the holonomic framework. The basic idea is to take into
  account the dimension of appropriate ideals in Ore algebras. This unifies
  several earlier extensions and provides algorithms for summation and
  integration in classes that had not been accessible to computer algebra
  before.},
}

@article{CloteKranakisKrizancSalvy2009,
    author      = {Clote, Peter and Kranakis, Evangelos and Krizanc, Danny and
  Salvy, Bruno},
    title       = {Asymptotics of Canonical and Saturated RNA Secondary
  Structures},
    journal     = {Journal of Bioinformatics and Computational Biology},
    number      = {5},
    year        = {2009},
    month       = {October},
    volume      = {7},
    pages       = {869–893},
    doi         = {10.1142/S0219720009004333},
    arxiv       = {abs/0908.4003},
    url         = {http://www.worldscinet.com/jbcb/07/0705/S0219720009004333.html},
    abstract    = {It is a classical result of Stein and Waterman that the
  asymptotic number of RNA secondary structures is 1.104366 ⋅
  n-3/2⋅ 2.618034n. In this paper, we study combinatorial asymptotics
  for two special subclasses of RNA secondary structures — canonical and
  saturated structures. Canonical secondary structures are defined to have no
  lonely (isolated) base pairs. This class of secondary structures was
  introduced by Bompfünewerer et al., who noted that the run time of Vienna
  RNA Package is substantially reduced when restricting computations to
  canonical structures. Here we provide an explanation for the speed-up, by
  proving that the asymptotic number of canonical RNA secondary structures is
  2.1614 ⋅ n-3/2 ⋅ 1.96798n and that the expected number of base
  pairs in a canonical secondary structure is 0.31724 ⋅ n. The asymptotic
  number of canonical secondary structures was obtained much earlier by
  Hofacker, Schuster and Stadler using a different method. Saturated secondary
  structures have the property that no base pairs can be added without
  violating the definition of secondary structure (i.e. introducing a
  pseudoknot or base triple). Here we show that the asymptotic number of
  saturated structures is 1.07427 ⋅ n-3/2⋅ 2.35467n, the
  asymptotic expected number of base pairs is 0.337361⋅ n, and the
  asymptotic number of saturated stem-loop structures is 0.323954 ⋅
  1.69562n, in contrast to the number 2n - 2 of (arbitrary) stem-loop
  structures as classically computed by Stein and Waterman. Finally, we apply
  the work of Drmota to show that the density of states for [all resp.
  canonical resp. saturated] secondary structures is asymptotically Gaussian.
  We introduce a stochastic greedy method to sample random saturated
  structures, called quasi-random saturated structures, and show that the
  expected number of base pairs is 0.340633 ⋅ n.},
}

@article{BorweinSalvy2008,
    author      = {Borwein, Jonathan M. and Salvy, Bruno},
    title       = {A proof of a recursion for {B}essel moments},
    journal     = {Experimental Mathematics},
    number      = {2},
    year        = {2008},
    volume      = {17},
    pages       = {223--230},
    arxiv       = {abs/0706.1409},
    abstract    = {We provide a proof of a conjecture in (Bailey, Borwein,
  Borwein, Crandall 2007) on the existence and form of linear recursions for
  moments of powers of the Bessel function $K_0$.},
}

@article{BoMoSaSc08,
    author      = {Bostan, Alin and Morain, Fran\c{c}ois and Salvy, Bruno and
  Schost, {\'E}ric},
    title       = {Fast algorithms for computing isogenies between elliptic
  curves},
    journal     = {Mathematics of Computation},
    number      = {263},
    year        = {2008},
    month       = {July},
    volume      = {77},
    pages       = {1755--1778},
    doi         = {10.1090/S0025-5718-08-02066-8},
    arxiv       = {abs/cs/0609020},
    abstract    = {We survey algorithms for computing isogenies between
  elliptic curves defined over a field of characteristic either 0 or a large
  prime. We introduce a new algorithm that computes an isogeny of degree $\ell$
  ($\ell$ different from the characteristic) in time quasi-linear with respect
  to $\ell$. This is based in particular on fast algorithms for power series
  expansion of the Weierstrass $\wp$-function and related functions.},
}

@inproceedings{BostanSalvySchost2008,
    author      = {Bostan, Alin and Salvy, Bruno and Schost, {\'E}ric},
    title       = {Power Series Composition and Change of Basis},
    booktitle   = {ISSAC'08: Proceedings of the twenty-first international
  symposium on Symbolic and algebraic computation},
    year        = {2008},
    editor      = {Jeffrey, David J.},
    publisher   = {ACM Press},
    pages       = {269--276},
    doi         = {10.1145/1390768.1390806},
    arxiv       = {abs/0804.2337},
    abstract    = {Efficient algorithms are known for many operations on
  truncated power series (multiplication, powering, exponential,...).
  Composition is a more complex task. We isolate a large class of power series
  for which composition can be performed efficiently. We deduce fast algorithms
  for converting polynomials between various bases, including Euler, Bernoulli,
  Fibonacci, and the orthogonal Laguerre, Hermite, Jacobi, Krawtchouk, Meixner
  and Meixner-Pollaczek.},
}

@inproceedings{DuFoSa08,
    author      = {Dumas, Jean-Guillaume and Fousse, Laurent and Salvy,
  Bruno},
    title       = {Compressed Modular Matrix Multiplication},
    booktitle   = {Milestones in Computer Algebra (MICA 2008)},
    year        = {2008},
    month       = {May},
    editor      = {Moreno Maza, Marc and Watt, Stephen M.},
    note        = {Proceedings of a conference in honour of Keith Geddes' 60th
  birthday. Stonehaven Bay, Trinidad and Tobago, 1-3 May 2008},
    arxiv       = {abs/0803.1975},
    url         = {http://algo.inria.fr/papers/pdf/DumasFousseSalvy2008.pdf},
    abstract    = {Matrices of integers modulo a small prime can be compressed
  by storing several entries into a single machine word. Modular addition is
  performed by addition and possibly subtraction of a word containing several
  times the modulo. We show how modular multiplication can also be performed.
  In terms of arithmetic operations, the gain over classical matrix
  multiplication is equal to the number of integers that are stored inside a
  machine word. The gain in actual speed is also close to that number. First,
  modular dot product can be performed via an integer multiplication by the
  reverse integer. Modular multiplication by a word containing a single residue
  is also possible. We give bounds on the sizes of primes and matrices for
  which such a compression is possible. We also make explicit the details of
  the required compressed arithmetic routines and show some practical
  performance.},
}

@article{GoSa08,
    author      = {Gomez, Claude and Salvy, Bruno},
    title       = {Calcul Formel},
    journal     = {Les Techniques de l'Ing{\'e}nieur},
    year        = {2008},
    volume      = {Dossier AF1460},
    pages       = {1--20},
}

@inproceedings{PivoteauSalvySoria2008,
    author      = {Pivoteau, Carine and Salvy, Bruno and Soria, Michèle},
    title       = {Boltzmann Oracle for Combinatorial Systems},
    booktitle   = {Algorithms, Trees, Combinatorics and Probabilities},
    year        = {2008},
    publisher   = {Discrete Mathematics and Theoretical Computer Science},
    pages       = {475–488},
    note        = {Proceedings of the Fifth Colloquium on Mathematics and
  Computer Science. Blaubeuren, Germany. September 22-26, 2008},
    url         = {http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAI0132},
    abstract    = {Boltzmann random generation applies to well-defined systems
  of recursive combinatorial equations. It relies on oracles giving values of
  the enumeration generating series inside their disk of convergence. We show
  that the combinatorial systems translate into numerical iteration schemes
  that provide such oracles. In particular, we give a fast oracle based on
  Newton iteration.},
}

@inproceedings{BostanChyzakLecerfSalvySchost2007,
    author      = {Bostan, Alin and Chyzak, Fr\'ed\'eric and Lecerf,
  Gr\'egoire and Salvy, Bruno and Schost, \'Eric},
    title       = {Differential equations for algebraic functions},
    booktitle   = {ISSAC'07: Proceedings of the 2007 international symposium
  on Symbolic and algebraic computation},
    year        = {2007},
    editor      = {Brown, C. W.},
    publisher   = {ACM Press},
    pages       = {25--32},
    doi         = {10.1145/1277548.1277553},
    arxiv       = {cs.SC/0703121},
    abstract    = {It is classical that univariate algebraic functions satisfy
  linear differential equations with polynomial coefficients. Linear
  recurrences follow for the coefficients of their power series expansions. We
  show that the linear differential equation of minimal order has coefficients
  whose degree is cubic in the degree of the function. We also show that there
  exists a linear differential equation of order linear in the degree whose
  coefficients are only of quadratic degree. Furthermore, we prove the
  existence of recurrences of order and degree close to optimal. We study the
  complexity of computing these differential equations and recurrences. We
  deduce a fast algorithm for the expansion of algebraic series.},
}

@inproceedings{BoChOlSaScSe07,
    author      = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Ollivier,
  Fran{\c c}ois and Salvy, Bruno and Schost, {\'E}ric and Sedoglavic,
  Alexandre},
    title       = {Fast computation of power series solutions of systems of
  differential equations},
    booktitle   = {SODA'07},
    year        = {2007},
    month       = {January},
    publisher   = {Society for Industrial and Applied Mathematics},
    pages       = {1012--1021},
    note        = {Proceedings of the eighteenth annual ACM-SIAM symposium on
  Discrete algorithms, New Orleans, Louisiana},
    arxiv       = {abs/cs/0604101},
    abstract    = {We propose new algorithms for the computation of the
  first~$N$ terms of a vector (resp. a basis) of power series solutions of a
  linear system of differential equations at an ordinary point, using a number
  of arithmetic operations which is quasi-linear with respect to~$N$. Similar
  results are also given in the non-linear case. This extends previous results
  obtained by Brent and Kung for scalar differential equations of order one and
  two.},
}

@article{GiLeSaYa07,
    author      = {Giusti, Marc and Lecerf, Gr{\'e}goire and Salvy, Bruno and
  Yakoubsohn, Jean-Claude},
    title       = {On Location and Approximation of Clusters of Zeroes: Case
  of Embedding Dimension One},
    journal     = {Foundations of Computational Mathematics},
    number      = {1},
    year        = {2007},
    month       = {February},
    volume      = {7},
    pages       = {1--58},
    doi         = {10.1007/s10208-004-0159-5},
    abstract    = {Isolated multiple zeros or clusters of zeros of analytic
  maps with several variables are known to be difficult to locate and
  approximate. This article is in the vein of the $\alpha$-theory, initiated by
  M.~Shub and S.~Smale in the beginning of the eighties. This theory restricts
  to simple zeros, i.e., where the map has corank zero. In this article we deal
  with situations where the analytic map has corank one at the multiple
  isolated zero, which has embedding dimension one in the frame of deformation
  theory. These situations are the least degenerate ones and therefore most
  likely to be of practical significance. More generally, we define clusters of
  embedding dimension one. We provide a criterion for locating such clusters of
  zeros and a fast algorithm for approximating them, with quadratic
  convergence. In case of a cluster with positive diameter our algorithm stops
  at a distance of the cluster which is about its diameter.},
}

@inproceedings{BoChClSa06,
    author      = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Cluzeau,
  Thomas and Salvy, Bruno},
    title       = {Low Complexity Algorithms for Linear Recurrences},
    booktitle   = {ISSAC'06},
    year        = {2006},
    editor      = {Dumas, Jean-Guillaume},
    publisher   = {ACM Press},
    pages       = {31--38},
    doi         = {10.1145/1145768.1145781},
    arxiv       = {abs/cs/0605068},
    abstract    = {We consider two kinds of problems: the computation of
  polynomial and rational solutions of linear recurrences with coefficients
  that are polynomials with integer coefficients; indefinite and definite
  summation of sequences that are hypergeometric over the rational numbers. The
  algorithms for these tasks all involve as an intermediate quantity an
  integer~$N$ (dispersion or root of an indicial polynomial) that is
  potentially exponential in the bit size of their input. Previous algorithms
  have a bit complexity that is at least quadratic in~$N$. We revisit them and
  propose variants that exploit the structure of solutions and avoid expanding
  polynomials of degree~$N$. We give two algorithms: a probabilistic one that
  detects the existence or absence of nonzero polynomial and rational solutions
  in~$O(\sqrt{N}\log^{2}N)$ bit operations; a deterministic one that computes a
  compact representation of the solution in~$O(N\log^{3}N)$ bit operations.
  Similar speed-ups are obtained in indefinite and definite hypergeometric
  summation. We describe the results of an implementation.},
}

@article{BoFlSaSc06,
    author      = {Bostan, Alin and Flajolet, Philippe and Salvy, Bruno and
  Schost, {\'E}ric},
    title       = {Fast Computation of Special Resultants},
    journal     = {Journal of Symbolic Computation},
    number      = {1},
    year        = {2006},
    month       = {January},
    volume      = {41},
    pages       = {1--29},
    doi         = {10.1016/j.jsc.2005.07.001},
    abstract    = {We propose fast algorithms for computing composed products
  and composed sums, as well as diamond products of univariate polynomials.
  These operations correspond to special multivariate resultants, that we
  compute using power sums of roots of polynomials, by means of their
  generating series.},
}

@inproceedings{BaFaSaYa05,
    author      = {Bardet, M. and Faug{\`e}re, J.-C. and Salvy, B. and Yang,
  B.-Y.},
    title       = {Asymptotic Behaviour of the Degree of Regularity of
  Semi-Regular Polynomial Systems},
    booktitle   = {MEGA'05},
    year        = {2005},
    note        = {Eighth International Symposium on Effective Methods in
  Algebraic Geometry, Porto Conte, Alghero, Sardinia (Italy), May 27th -- June
  1st},
    abstract    = {We compute the asymptotic expansion of the degree of
  regularity for overdetermined semi-regular sequences of algebraic equations.
  This degree implies bounds for the generic complexity of Gr{\"o}bner bases
  algorithms, in particular Faug{\`e}re's $F_5$ algorithm. Bounds can also be
  derived for the XL family of algorithms used by the cryptographic
  community.},
}

@inproceedings{BoClSa05,
    author      = {Bostan, Alin and Cluzeau, Thomas and Salvy, Bruno},
    title       = {Fast Algorithms for Polynomial Solutions of Linear
  Differential Equations},
    booktitle   = {ISSAC'05},
    year        = {2005},
    editor      = {Kauers, Manuel},
    publisher   = {ACM Press},
    address     = {New York},
    pages       = {45--52},
    note        = {Proceedings of the 2005 International Symposium on Symbolic
  and Algebraic Computation, July 2005, Beijing, China.},
    doi         = {10.1145/1073884.1073893},
    abstract    = {We investigate polynomial solutions of homogeneous linear
  differential equations with coefficients that are polynomials with integer
  coefficients. The problems we consider are the existence of nonzero
  polynomial solutions, the determination of the dimension of the vector space
  of polynomial solutions, the computation of a basis of this space. Previous
  algorithms have a bit complexity that is at least quadratic in the largest
  integer valuation $N$ of formal Laurent series solutions at infinity, even
  for merely detecting the existence of nonzero polynomial solutions. We give a
  deterministic algorithm that computes a compact representation of a basis of
  polynomial solutions in $O(N\log^3N)$ bit operations. We also give a
  probabilistic algorithm that computes the dimension of the space of
  polynomial solutions in $O(N\log^2N)$ bit operations. In general, the integer
  $N$ is not polynomially bounded in the bit size of the input differential
  equation. We isolate a class of equations for which detecting nonzero
  polynomial solutions can be performed in polynomial complexity. We discuss
  implementation issues and possible extensions.},
}

@article{ChMiSa05,
    author      = {Chyzak, Fr\'ed\'eric and Mishna, Marni and Salvy, Bruno},
    title       = {Effective Scalar Products of {D}-finite Symmetric
  Functions},
    journal     = {Journal of Combinatorial Theory, Series A},
    number      = {1},
    year        = {2005},
    month       = {October},
    volume      = {112},
    pages       = {1--43},
    note        = {Extended version of an article published in the proceedings
  of the 14th Conference of Formal Power Series and Algebraic Combinatorics
  FPSAC'02, Melbourne, July 2002},
    doi         = {10.1016/j.jcta.2005.01.001},
    arxiv       = {abs/math/0310132},
    abstract    = {Many combinatorial generating functions can be expressed as
  combinations of symmetric functions, or extracted as sub-series and
  specializations from such combinations. Gessel has outlined a large class of
  symmetric functions for which the resulting generating functions are
  D-finite. We extend Gessel's work by providing algorithms that compute
  differential equations, these generating functions satisfy in the case they
  are given as a scalar product of symmetric functions in Gessel's class.
  Examples of applications to k-regular graphs and Young tableaux with repeated
  entries are given. Asymptotic estimates are a natural application of our
  method, which we illustrate on the same model of Young tableaux. We also
  derive a seemingly new formula for the Kronecker product of the sum of Schur
  functions with itself.},
}

@article{FlGeSa05,
    author      = {Flajolet, Philippe and Gerhold, Stefan and Salvy, Bruno},
    title       = {On the non-holonomic character of logarithms, powers, and
  the nth prime function},
    journal     = {The Electronic Journal of Combinatorics},
    number      = {2},
    year        = {2005},
    month       = {April},
    volume      = {11},
    note        = {A2, 16 pages},
    arxiv       = {abs/math/0501379},
    url         = {http://www.combinatorics.org/Volume_11/PDF/v11i2a2.pdf},
    abstract    = {We establish that the sequences formed by logarithms and by
  ``fractional'' powers of integers, as well as the sequence of prime numbers,
  are non-holonomic, thereby answering three open problems of Gerhold
  [El. J. Comb. 11 (2004), R87]. Our proofs depend on basic
  complex analysis, namely a conjunction of the Structure Theorem for
  singularities of solutions to linear differential equations and of an Abelian
  theorem. A brief discussion is offered regarding the scope of
  singularity-based methods and several naturally occurring sequences are
  proved to be non-holonomic.},
}

@article{GiLeSaYa05,
    author      = {Giusti, Marc and Lecerf, Gr{\'e}goire and Salvy, Bruno and
  Yakoubsohn, Jean-Claude},
    title       = {On Location and Approximation of Clusters of Zeroes of
  Analytic Functions},
    journal     = {Foundations of Computational Mathematics},
    number      = {3},
    year        = {2005},
    month       = {July},
    volume      = {5},
    pages       = {257--311},
    doi         = {10.1007/s10208-004-0144-z},
    abstract    = {At the beginning of the 1980s, M. Shub and S. Smale
  developed a quantitative analysis of Newton's method for multivariate
  analytic maps. In particular, their $\alpha$-theory gives an effective
  criterion that ensures safe convergence to a simple isolated zero. This
  criterion requires only information concerning the map at the initial point
  of the iteration. Generalizing this theory to multiple zeros and clusters of
  zeros is still a challenging problem. In this paper we focus on one complex
  variable function. We study general criteria for detecting clusters and
  analyze the convergence of Schr{\"o}der's iteration to a cluster. In the case
  of a multiple root, it is well known that this convergence is quadratic. In
  the case of a cluster with positive diameter, the convergence is still
  quadratic provided the iteration is stopped sufficiently early. We propose a
  criterion for stopping this iteration at a distance from the cluster which is
  of the order of its diameter.},
}

@inproceedings{Salvy05,
    author      = {Salvy, Bruno},
    title       = {D-Finiteness: Algorithms and Applications},
    booktitle   = {ISSAC'05},
    year        = {2005},
    editor      = {Kauers, Manuel},
    publisher   = {ACM Press},
    pages       = {2--3},
    note        = {Abstract for an invited talk. Proceedings of the 2005
  International Symposium on Symbolic and Algebraic Computation, Beijing, July
  2005.},
    doi         = {10.1145/1073884.1073886},
}

@inproceedings{BaFaSa04,
    author      = {Bardet, Magali and Faugère, Jean-Charles and Salvy,
  Bruno},
    title       = {On the Complexity of Gröbner basis computation of
  Semi-regular Overdetermined algebraic equations},
    booktitle   = {International Conference on Polynomial System Solving},
    year        = {2004},
    month       = {November},
    pages       = {71–74},
    note        = {Proceedings of a conference held in Paris, France in honor
  of Daniel Lazard},
    url         = {http://www-calfor.lip6.fr/ICPSS/papers/43BF/43bf.htm},
    abstract    = {We extend Macaulay's notion of regular sequence to
  overdetermined system of algebraic equations. We study generic properties of
  Gröbner bases and analyse precisely the behavior of Faugère's F5
  algorithm. Sharp asymptotic estimates of the degree of regularity are
  given.},
}

@inproceedings{BoLeSaScWi04,
    author      = {Bostan, Alin and Lecerf, Gr{\'e}goire and Salvy, Bruno and
  Schost, {\'E}ric and Wiebelt, Bernd},
    title       = {Complexity Issues in Bivariate Polynomial Factorization},
    booktitle   = {Symbolic and Algebraic Computation},
    year        = {2004},
    editor      = {Gutierrez, J.},
    publisher   = {ACM Press},
    pages       = {42--49},
    note        = {Proceedings of ISSAC'04, Santander, July 2004},
    doi         = {10.1145/1005285.1005294},
    abstract    = {Many polynomial factorization algorithms rely on Hensel
  lifting and factor recombination. For bivariate polynomials we show that
  lifting the factors up to a precision linear in the total degree of the
  polynomial to be factored is sufficient to deduce the recombination by linear
  algebra, using trace recombination. Then, the total cost of the lifting and
  the recombination stage is subquadratic in the size of the dense
  representation of the input polynomial. Lifting is often the practical
  bottleneck of this method: we propose an algorithm based on a faster
  multi-moduli computation for univariate polynomials and show that it saves a
  constant factor compared to the classical multifactor lifting algorithm.},
}

@article{FlSaSc04,
    author      = {Flajolet, Philippe and Salvy, Bruno and Schaeffer,
  Gilles},
    title       = {Airy Phenomena and Analytic Combinatorics of Connected
  Graphs},
    journal     = {The Electronic Journal of Combinatorics},
    number      = {1},
    year        = {2004},
    month       = {May},
    volume      = {11},
    pages       = {R34},
    note        = {30 pages},
    url         = {http://www.combinatorics.org/Volume_11/PDF/v11i1r34.pdf},
    abstract    = {Until now, the enumeration of connected graphs has been
  dealt with by probabilistic methods, by special combinatorial decompositions
  or by somewhat indirect formal series manipulations. We show here that it is
  possible to make analytic sense of the divergent series that expresses the
  generating function of connected graphs. As a consequence, it becomes
  possible to derive analytically known enumeration results using only first
  principles of combinatorial analysis and straight asymptotic
  analysis—specifically, the saddle-point method. In this perspective, the
  enumeration of connected graphs by excess (of number of edges over number of
  vertices) derives from a simple saddle-point analysis. Furthermore, a refined
  analysis based on coalescent saddle points yields complete asymptotic
  expansions for the number of graphs of fixed excess, through an explicit
  connection with Airy functions.},
}

@article{BoSaSc03,
    author      = {Bostan, Alin and Salvy, Bruno and Schost, {\'E}ric},
    title       = {Fast Algorithms for Zero-Dimensional Polynomial Systems
  Using Duality},
    journal     = {Applicable Algebra in Engineering, Communication and
  Computing},
    number      = {4},
    year        = {2003},
    volume      = {14},
    pages       = {239--272},
    doi         = {10.1007/s00200-003-0133-5},
    abstract    = {Many questions concerning a zero-dimensional polynomial
  system can be reduced to linear algebra operations in the quotient
  algebra~$A=k[X_1,\dots,X_n]/I$, where~$I$ is the ideal generated by the input
  system. Assuming that the multiplicative structure of the algebra $A$ is
  (partly) known, we address the question of speeding up the linear algebra
  phase for the computation of minimal polynomials and rational
  parametrizations in $A$. We present new formul{\ae}\ for the rational
  parametrizations, extending those of Rouillier, and algorithms extending
  ideas introduced by Shoup in the univariate case. Our approach is based on
  the~$A$-module structure of the dual space~$\widehat{A}$. An important
  feature of our algorithms is that we do not require~$\widehat{A}$ to be free
  and of rank~1. The complexity of our algorithms for computing the minimal
  polynomial and the rational parametrizations are~$O(2^nD^{5/2})$
  and~$O(n2^nD^{5/2})$ respectively, where~$D$ is the dimension of~$A$. For
  fixed~$n$, this is better than algorithms based on linear algebra except when
  the complexity of the available matrix product has exponent less than~5/2.},
}

@inproceedings{MeSa03,
    author      = {Meunier, Ludovic and Salvy, Bruno},
    title       = {{ESF}: An Automatically Generated Encyclopedia of Special
  Functions},
    booktitle   = {Symbolic and Algebraic Computation},
    year        = {2003},
    editor      = {Sendra, J. R.},
    publisher   = {ACM Press},
    pages       = {199--205},
    note        = {Proceedings of ISSAC'03, Philadelphia, August 2003.},
    doi         = {10.1145/860854.860898},
    abstract    = {We present our on-going work on the automatic generation of
  an encyclopedia of special functions on the web, called The Encyclopedia of
  Special Functions (ESF) http://algo.inria.fr/esf. All mathematical
  formul{\ae} in the ESF are computed, typeset and displayed without any human
  intervention. This is achieved by exploiting a collection of computer algebra
  algorithms in a systematic way, on top of a specially designed data structure
  for a class of special functions.},
}

@inproceedings{ChMiSa02,
    author      = {Chyzak, Frédéric and Mishna, Marni and Salvy, Bruno},
    title       = {Effective D-finite Symmetric Functions},
    booktitle   = {14th Conference of Formal Power Series and Algebraic
  Combinatorics},
    year        = {2002},
    month       = {July},
    publisher   = {University of Melbourne},
    address     = {Melbourne, Australia},
    pages       = {19.1–19.12},
    note        = {Extended abstract. Proceedings FPSAC'02. An extended
  version has appeared in [Chyzak et al., 2005a]},
    web-comment = {Preliminary
  version.},
    abstract    = {Many combinatorial generating functions can be extracted
  from symmetric functions. Gessel has outlined a large class of symmetric
  functions for which the resulting generating functions are D-finite. We
  extend Gessel's work by providing algorithms that compute differential
  equations these generating functions satisfy. Examples of applications to
  k-regular graphs and Young tableaux with repeated entries are given.},
}

@article{CoRoSa02,
    author      = {Cori, Robert and Rossin, Dominique and Salvy, Bruno},
    title       = {Polynomial Ideals for Sandpiles and their {G}r{\"o}bner
  Bases},
    journal     = {Theoretical Computer Science},
    number      = {1},
    year        = {2002},
    volume      = {276},
    pages       = {1--15},
    doi         = {10.1016/S0304-3975(00)00397-2},
    abstract    = {A polynomial ideal encoding topplings in the abelian
  sandpile model on a graph is introduced. A Gr{\"o}bner basis of this ideal is
  interpreted combinatorially in terms of well-connected subgraphs. This gives
  rise to algorithms to determine the identity and the operation in the group
  of recurrent configurations.},
}

@article{NiSaFl02,
    author      = {Nicod{\`e}me, Pierre and Salvy, Bruno and Flajolet,
  Philippe},
    title       = {Motif Statistics},
    journal     = {Theoretical Computer Science},
    number      = {2},
    year        = {2002},
    volume      = {287},
    pages       = {593--618},
    note        = {Extended version of an article published in the proceedings
  of 7th Annual European Symposium on Algorithms ESA'99, Prague, July 1999},
    doi         = {10.1016/S0304-3975(01)00264-X},
    abstract    = {We present a complete analysis of the statistics of number
  of occurrences of a regular expression pattern in a random text. This covers
  ``motifs'' widely used in computational biology. Our approach is based on:
  (i) classical constructive results in automata and formal language theory;
  (ii) analytic combinatorics that is used for deriving asymptotic properties
  from generating functions; (iii) computer algebra in order to determine
  generating functions explicitly, analyse generating functions and extract
  coefficients efficiently. We provide constructions for overlapping or
  non-overlapping matches of a regular expression. A companion implementation
  produces: multivariate generating functions for the statistics under study; a
  fast computation of their Taylor coefficients which yields exact values of
  the moments with typical application to random texts of size 30,000; precise
  asymptotic formul{\ae} that allow predictions in texts of arbitrarily large
  sizes. Our implementation was tested by comparing predictions of the number
  of occurrences of motifs against the 7 megabytes amino acid database Procite.
  We handled more than 88% of the standard collection of Prodom motifs with our
  programs. Such comparisons help detect which motifs are observed in real
  biological data more or less frequently than theoretically predicted.},
}

@techreport{SaSh02,
    author      = {Salvy, Bruno and Shackell, John},
    title       = {Asymptotic Expansions with Oscillating Coefficients},
    number      = {UKC/IMS/02/33},
    year        = {2002},
    month       = {October},
    institution = {University of Kent, Canterbury},
}

@article{GiLeSa01,
    author      = {Giusti, Marc and Lecerf, Gr{\'e}goire and Salvy, Bruno},
    title       = {A {G}r{\"o}bner Free Alternative for Polynomial System
  Solving},
    journal     = {Journal of Complexity},
    number      = {1},
    year        = {2001},
    month       = {March},
    volume      = {17},
    pages       = {154--211},
    doi         = {10.1006/jcom.2000.0571},
    abstract    = {Given a system of polynomial equations and inequations with
  coefficients in the field of rational numbers, we show how to compute a
  geometric resolution of the set of common roots of the system over the field
  of complex numbers. A geometric resolution consists of a primitive element of
  the algebraic extension defined by the set of roots, its minimal polynomial,
  and the parametrizations of the coordinates. Such a representation of the
  solutions has a long history which goes back to Leopold Kronecker and has
  been revisited many times in computer algebra. We introduce a new generation
  of probabilistic algorithms where all the computations use only univariate or
  bivariate polynomials. We give a new codification of the set of solutions of
  a positive dimensional algebraic variety relying on a new global version of
  Newton's iterator. Roughly speaking the complexity of our algorithm is
  polynomial in some kind of degree of the system, in its height, and linear in
  the complexity of evaluation of the system. We present our implementation in
  the Magma system which is called Kronecker in homage to his method for
  solving systems of polynomial equations. We show that the theoretical
  complexity of our algorithm is well reflected in practice and we exhibit some
  cases for which our program is more efficient than the other available
  software.},
}

@inproceedings{MeunierSalvy2001,
    author      = {Meunier, Ludovic and Salvy, Bruno},
    title       = {Automatically Generated Encyclopedia of Special
  Functions},
    booktitle   = {Mathematical Knowledge Management},
    year        = {2001},
    note        = {Proceedings MKM'01, Linz, September 2001. A more advanced
  version has appeared in [Meunier and Salvy, 2003]},
    url         = {http://www.risc.uni-linz.ac.at/about/conferences/MKM2001/Proceedings/printed/meunier.ps},
    abstract    = {We present our on-going work on creating an automatically
  generated encyclopedia of special functions. The aim is to exploit recent
  progress in computer algebra in order to synthesize web pages on special
  functions and provide some level of interactivity.},
}

@techreport{Salvy01,
    author      = {Salvy, Bruno},
    title       = {Even-Odd Set Partitions, Saddle-Point Method and Wyman
  Admissibility},
    number      = {4201},
    year        = {2001},
    institution = {Institut National de Recherche en Informatique et en
  Automatique},
    note        = {14 pages},
    url         = {http://www.inria.fr/rrrt/rr-4201.html},
    abstract    = {The reciprocal of the generating function of the Bell
  numbers enumerates the difference between numbers of set partitions with even
  and odd number of blocks. The asymptotic behaviour of this oscillatory
  sequence is obtained by a saddle-point analysis involving two conjugate
  saddle points. Technical details of the analysis are dealt with by appealing
  to Wyman's class of admissible functions.},
}

@article{GiHaLeMaSa00,
    author      = {Giusti, Marc and H{\"a}gele, Klemens and Lecerf,
  Gr{\'e}goire and Marchand, Jo{\"e}l and Salvy, Bruno},
    title       = {Computing the Dimension of a Projective Variety: the
  Projective {N}oether {M}aple Package},
    journal     = {Journal of Symbolic Computation},
    number      = {3},
    year        = {2000},
    month       = {September},
    volume      = {30},
    pages       = {291--307},
    doi         = {10.1006/jsco.2000.0369},
    abstract    = {Recent theoretical advances in elimination theory use
  straight-line programs as a data structure to represent multivariate
  polynomials. We present here the Projective Noether Package which is a Maple
  implementation of one of these new algorithms, yielding as a byproduct a
  computation of the dimension of a projective variety. Comparative results on
  benchmarks for time and space of several families of multivariate polynomial
  equation systems are given and we point out both weaknesses and advantages of
  different approaches.},
}

@inproceedings{NicodemeSalvyFlajolet1999,
    author      = {Nicodème, Pierre and Salvy, Bruno and Flajolet,
  Philippe},
    title       = {Motif Statistics},
    booktitle   = {Algorithms – ESA'99},
    number      = {1643},
    year        = {1999},
    editor      = {Nesetril, Jaroslav},
    series      = {Lecture Notes in Computer Science},
    pages       = {194–211},
    note        = {Proceedings 7th Annual European Symposium on Algorithms,
  Prague, July 99. An extended version appeared
  in [NicodemeSalvyFlajolet02].},
    doi         = {10.1007/3-540-48481-7_18},
    url         = {http://www.springerlink.com/link.asp?id=kn33ur4g65qcgyhg},
    abstract    = {We present a complete analysis of the statistics of number
  of occurrences of a regular expression pattern in a random text. This covers
  ``motifs'' widely used in computational biology. Our approach is based on:
  (i) a constructive approach to classical results in theoretical
  computer science (automata and formal language theory), in particular, the
  rationality of generating functions of regular languages; (ii)
  analytic combinatorics that is used for deriving asymptotic properties from
  generating functions; (iii) computer algebra for determining
  generating functions explicitly, analysing generating functions and
  extracting coefficients efficiently. We provide constructions for overlapping
  or non-overlapping matches of a regular expression. A companion
  implementation produces multivariate generating functions for the statistics
  under study. A fast computation of Taylor coefficients of the generating
  functions then yields exact values of the moments with typical application to
  random texts of size 30,000 while precise symptotic formulæ allow
  predictions in texts of arbitrarily large sizes. Our implementation was
  tested by comparing predictions of the number of occurrences of motifs
  against the 7 megabytes amino acid database  sc  Prodom. % consensus. We
  handled more than 88% of the standard collection of  sc  Prosite motifs
  with our programs. Such comparisons help detect which motifs are observed in
  real biological data more or less frequently than theoretically predicted.},
}

@proceedings{Salvy99,
    title       = {Algorithms Seminar, 1998–1999},
    year        = {1999},
    month       = {September},
    editor      = {Bruno Salvy},
    volume      = {3830},
    series      = {Research Report},
    organization= {Institut National de Recherche en Informatique et en
  Automatique},
    url         = {http://www.inria.fr/rrrt/rr-3830.html},
    abstract    = {These seminar notes represent the proceedings of a seminar
  devoted to the analysis of algorithms and related topics. The subjects
  covered include combinatorics, symbolic computation, asymptotic analysis and
  average-case analysis of algorithms and data structures.},
}

@article{SaSh99,
    author      = {Salvy, Bruno and Shackell, John},
    title       = {Symbolic Asymptotics: Multiseries of Inverse Functions},
    journal     = {Journal of Symbolic Computation},
    number      = {6},
    year        = {1999},
    month       = {June},
    volume      = {27},
    pages       = {543--563},
    doi         = {10.1006/jsco.1999.0281},
    abstract    = {We give an algorithm to compute an asymptotic expansion of
  multiseries type for the inverse of any given exp-log function. An example of
  the use of this algorithm to compute asymptotic expansions in combinatorics
  via the saddle-point method is then treated in detail.},
}

@article{ChSa98,
    author      = {Chyzak, Frédéric and Salvy, Bruno},
    title       = {Non-commutative Elimination in Ore Algebras Proves
  Multivariate Holonomic Identities},
    journal     = {Journal of Symbolic Computation},
    number      = {2},
    year        = {1998},
    month       = {August},
    volume      = {26},
    pages       = {187–227},
    doi         = {10.1006/jsco.1998.0207},
    web-comment = {See the accompanying Maple session and the errata.},
    abstract    = {Many computations involving special functions,
  combinatorial sequences or theirq-analogues can be performed using linear
  operators and simple arguments on the dimension of related vector spaces. In
  this article, we develop a theory of -finite sequences and functions which
  provides a unified framework to express algorithms for computing sums and
  integrals and for the proof or discovery of multivariate identities. This
  approach is vindicated by an implementation.},
}

@article{FlSa98,
    author      = {Flajolet, Philippe and Salvy, Bruno},
    title       = {Euler Sums and Contour Integral Representations},
    journal     = {Experimental Mathematics},
    number      = {1},
    year        = {1998},
    volume      = {7},
    pages       = {15–35},
    url         = {http://www.math.ethz.ch/EMIS/journals/EM/restricted/7/7.1/flajolet.ps},
    abstract    = {This paper develops an approach to the evaluation of Euler
  sums that involve harmonic numbers, either linearly or nonlinearly. We give
  explicit formulæ for several classes of Euler sums in terms of Riemann
  zeta values. The approach is based on simple contour integral representations
  and residue computations.},
}

@proceedings{Salvy98,
    title       = {Algorithms Seminar, 1997–1998},
    year        = {1998},
    month       = {September},
    editor      = {Bruno Salvy},
    volume      = {3504},
    series      = {Research Report},
    organization= {Institut National de Recherche en Informatique et en
  Automatique},
    url         = {http://www.inria.fr/rrrt/rr-3504.html},
    abstract    = {These seminar notes represent the proceedings of a seminar
  devoted to the analysis of algorithms and related topics. The subjects
  covered include combinatorics, symbolic computation, asymptotic analysis and
  average-case analysis of algorithms and data structures.},
}

@article{SaSh98,
    author      = {Salvy, Bruno and Shackell, John},
    title       = {Symbolic Asymptotics: Functions of Two Variables, Implicit
  Functions},
    journal     = {Journal of Symbolic Computation},
    number      = {3},
    year        = {1998},
    month       = {March},
    volume      = {25},
    pages       = {329--349},
    doi         = {10.1006/jsco.1997.0179},
    abstract    = {A number of recent papers have been concerned with
  algorithms to decide the limiting behaviour of functions of a single
  variable. Here we make a corresponding study of a class of functions of two
  variables, namely the exp-log functions. As in the one-variable case, we need
  to make certain assumptions regarding the handling of constants. Two of the
  main tools in the one-variable case are Hardy fields and nested forms. Here,
  we show how to compute some asymptotic estimates for two-variable exp-log
  functions. This method is then used to give an algorithm for computing the
  nested forms of real implicit functions.},
}

@article{FlSa97,
    author      = {Flajolet, Philippe and Salvy, Bruno},
    title       = {The {S}IGSAM Challenges: Symbolic Asymptotics in
  Practice},
    journal     = {SIGSAM Bulletin},
    number      = {4},
    year        = {1997},
    month       = {December},
    volume      = {31},
    pages       = {36--47},
    doi         = {10.1145/274888.274890},
    abstract    = {We present answers to 5 out of 10 of the ``Problems,
  Puzzles, Challenges'' proposed by G. J. Fee and M. B. Monagan in the March
  1997 issue of the Sigsam Bulletin. In all cases, the answer to a seemingly
  numerical problem is obtained via series expansions and asymptotic methods.
  This illustrates more generally the crucial role played in the presence of
  singular behaviours by symbolic asymptotics as a bridge between symbolic
  computation and numerical computations. All our computations have been
  performed using MapleV.4 on a Dec Alpha (255/233). The timings indicated
  correspond to executions on this machine.},
}

@article{HaSa97,
    author      = {Habsieger, Laurent and Salvy, Bruno},
    title       = {On Integer Chebyshev Polynomials},
    journal     = {Mathematics of Computation},
    number      = {218},
    year        = {1997},
    month       = {April},
    volume      = {66},
    pages       = {763–770},
    doi         = {10.1090/S0025-5718-97-00829-6},
    url         = {http://www.ams.org/mcom/1997-66-218/S0025-5718-97-00829-6/S0025-5718-97-00829-6.pdf},
    abstract    = {We are concerned with the problem of minimizing the
  supremum norm on [0,1] of a nonzero polynomial of degree at most n with
  integer coefficients. We use the structure of such polynomials to derive an
  efficient algorithm for computing them. We give a table of these polynomials
  for degree up to 75 and use a value from this table to answer an open
  problem and improve a lower bound due to Borwein and Erdelyi (1995).},
}

@proceedings{Salvy97,
    title       = {Algorithms Seminar, 1996–1997},
    year        = {1997},
    month       = {September},
    editor      = {Bruno Salvy},
    volume      = {3267},
    series      = {Research Report},
    organization= {Institut National de Recherche en Informatique et en
  Automatique},
    url         = {http://www.inria.fr/rrrt/rr-3267.html},
    abstract    = {These seminar notes represent the proceedings of a seminar
  devoted to the analysis of algorithms and related topics. The subjects
  covered include combinatorics, symbolic computation, asymptotic analysis and
  average-case analysis of algorithms and data structures.},
}

@article{GoSa96,
    author      = {Gourdon, Xavier and Salvy, Bruno},
    title       = {Effective asymptotics of linear recurrences with rational
  coefficients},
    journal     = {Discrete Mathematics},
    number      = {1--3},
    year        = {1996},
    volume      = {153},
    pages       = {145--163},
    doi         = {10.1016/0012-365X(95)00133-H},
    abstract    = {We give algorithms to compute the asymptotic expansion of
  solutions of linear recurrences with rational coefficients and rational
  initial conditions in polynomial time in the order of the recurrence.},
}

@inproceedings{RiSaShVH96,
    author      = {Richardson, Dan and Salvy, Bruno and Shackell, John and Van
  der Hoeven, Joris},
    title       = {Asymptotic Expansions of exp-log Functions},
    booktitle   = {Symbolic and Algebraic Computation},
    year        = {1996},
    editor      = {Lakshman, Y. N.},
    publisher   = {ACM Press},
    address     = {New York},
    pages       = {309--313},
    note        = {Proceedings ISSAC'96, Z{\"u}rich, July 1996},
    doi         = {10.1145/236869.237089},
    abstract    = {We give an algorithm to compute asymptotic expansions of
  exp-log functions. This algorithm automatically computes the necessary
  asymptotic scale and does not suffer from problems of indefinite
  cancellation. In particular, an asymptotic equivalent can always be computed
  for a given exp-log function.},
}

@proceedings{Salvy96,
    title       = {Algorithms Seminar, 1995–1996},
    year        = {1996},
    month       = {September},
    editor      = {Bruno Salvy},
    volume      = {2992},
    series      = {Research Report},
    organization= {Institut National de Recherche en Informatique et en
  Automatique},
    url         = {http://www.inria.fr/rrrt/rr-2992.html},
}

@article{DuSa95,
    author      = {Dumas, Philippe and Salvy, Bruno},
    title       = {Maple and the {P}utnam Competition},
    journal     = {Maple Technical Newsletter},
    number      = {2},
    year        = {1995},
    volume      = {2},
    pages       = {63--68},
}

@article{FlSa95,
    author      = {Flajolet, Philippe and Salvy, Bruno},
    title       = {Computer Algebra Libraries for Combinatorial Structures},
    journal     = {Journal of Symbolic Computation},
    number      = {5-6},
    year        = {1995},
    volume      = {20},
    pages       = {653--671},
    doi         = {10.1006/jsco.1995.1070},
    abstract    = {This paper introduces the framework of decomposable
  combinatorial structures and their traversal algorithms. A combinatorial type
  is decomposable if it admits a specification in terms of unions, products,
  sequences, sets, and cycles, either in the labelled or in the unlabelled
  context. Many properties of decomposable structures are decidable. Generating
  function equations, counting sequences, and random generation algorithms can
  be compiled from specifications. Asymptotic properties can be determined
  automatically for a reasonably large subclass. Maple libraries that implement
  such decision procedures are briefly surveyed (LUO, combstruct, equivalent).
  In addition, libraries for manipulating holonomic sequences and functions are
  presented (gfun, Mgfun).},
}

@article{FlLaLaSa95,
    author      = {Flajolet, Philippe and Labelle, Gilbert and Laforest,
  Louise and Salvy, Bruno},
    title       = {Hypergeometrics and the cost structure of quadtrees},
    journal     = {Random Structures \& Algorithms},
    number      = {2},
    year        = {1995},
    volume      = {7},
    pages       = {117--144},
    doi         = {10.1002/rsa.3240070203},
    abstract    = {Several characteristic parameters of randomly grown
  quadtrees of any dimension are analysed. Additive parameters have
  expectations whose generating functions are expressible in terms of
  generalized hypergeometric functions. A complex asymptotic process based on
  singularity analysis and integral representations akin to Mellin transforms
  leads to explicit values for various structure constants related to path
  length, retrieval costs, and storage occupation.},
}

@book{GoSaZi95,
    author      = {Gomez, Claude and Salvy, Bruno and Zimmermann, Paul},
    title       = {Calcul formel : mode d'emploi. {E}xemples en {M}aple},
    year        = {1995},
    publisher   = {Masson},
    note        = {ISBN 2-225-84780-0. 328 pages},
}

@article{LipshitzScottSalvy1995,
    author      = {Lipshitz, Stanley P. and Scott, Tony C. and Salvy, Bruno},
    title       = {On the Acoustic Impedance of Baffled Strip Radiators},
    journal     = {Journal of the Audio Engineering Society},
    number      = {7/8},
    year        = {1995},
    month       = {July/August},
    volume      = {43},
    pages       = {573--580},
    abstract    = {There appears to be no available expression for the
  reactive (mass) term in the acoustic impedance of long baffled strip
  radiators, and the literature contains contradictory graphical data on both
  the real and the imaginary parts. Reliable data are important for the proper
  electroacoustic design of ribbon transducers, and also potentially for other
  long, narrow, low-mass planar radiators, both electrostatic and
  electrqmagnetic. Analytical expressions and graphical data are presented for
  the resistive and reactive parts of the acoustic load on an infinite baffled
  strip radiator.},
}

@proceedings{Salvy95,
    title       = {Algorithms Seminar, 1994–1995},
    year        = {1995},
    month       = {October},
    editor      = {Bruno Salvy},
    volume      = {2669},
    series      = {Research Report},
    organization= {Institut National de Recherche en Informatique et en
  Automatique},
    url         = {http://www.inria.fr/rrrt/rr-2669.html},
    abstract    = {These seminar notes represent the proceedings of a seminar
  devoted to the analysis of algorithms and related topics. The subjects
  covered include combinatorial models and random generation, symbolic
  computation, asymptotic analysis, average-case analysis of algorithms and
  data structures, and computational number theory.},
}

@techreport{SaSl95,
    author      = {Salvy, Bruno and Slavyanov, Sergey Yu.},
    title       = {A Combinatorial Problem in the Classification of
  Second-Order Linear ODE's},
    number      = {2600},
    year        = {1995},
    institution = {Institut National de Recherche en Informatique et en
  Automatique},
    url         = {http://www.inria.fr/rrrt/rr-2600.html},
    abstract    = {We study a problem of classification of linear homogeneous
  second-order ODE's with polynomial coefficients based on qualitative
  properties of singularities. The corresponding combinatorial problem of
  counting the number of classes is then solved in terms of the initial number
  of singularities.},
}

@article{SaSh95,
    author      = {Shackell, John and Salvy, Bruno},
    title       = {Asymptotic Forms and Algebraic Differential Equations},
    journal     = {Journal of Symbolic Computation},
    number      = {2},
    year        = {1995},
    volume      = {20},
    pages       = {169--177},
    doi         = {10.1006/jsco.1995.1044},
    abstract    = {We analyse the complexity of a simple algorithm for
  computing asymptotic solutions of algebraic differential equations. This
  analysis is based on a computation of the number of possible asymptotic
  monomials of a certain order, and on the study of the growth of this number
  as the order of the equation grows.},
}

@proceedings{Salvy94b,
    title       = {Algorithms Seminar, 1993–1994},
    year        = {1994},
    month       = {October},
    editor      = {Bruno Salvy},
    volume      = {2381},
    series      = {Research Report},
    organization= {Institut National de Recherche en Informatique et en
  Automatique},
    url         = {http://www.inria.fr/rrrt/rr-2381.html},
    abstract    = {These seminar notes represent the proceedings of a seminar
  devoted to the analysis of algorithms and related topics. The subjects
  covered include combinatorial models and random generation, symbolic
  computation, asymptotic analysis, average-case analysis of algorithms and
  data structures, and computational number theory.},
}

@article{Salvy94,
    author      = {Salvy, Bruno},
    title       = {Fast Computation of Some Asymptotic Functional Inverses},
    journal     = {Journal of Symbolic Computation},
    number      = {3},
    year        = {1994},
    volume      = {17},
    pages       = {227--236},
    doi         = {10.1006/jsco.1994.1014},
    abstract    = {G.~Robin showed that in several naturally occurring
  asymptotic expansions of the form \[y(x)\approx\sum_{n\ge0}{P_n(\log\log
  x)\over\log^n\!x},\] the polynomials~$P_n$ satisfy a simple relation
  \[P'_{n+1}=aP'_n+(bn+c)P_n.\] These results do not give a way to compute
  these polynomials, since the constant term remains undetermined by this
  equation. In this note, we give a new derivation of some of Robin's results,
  and show how the constant terms can be computed with only manipulations of
  one-variable formal power series. From there, all the~$P_n$ can be computed
  efficiently.},
}

@article{SaZi94,
    author      = {Salvy, Bruno and Zimmermann, Paul},
    title       = {Gfun: a {M}aple package for the manipulation of generating
  and holonomic functions in one variable},
    journal     = {ACM Transactions on Mathematical Software},
    number      = {2},
    year        = {1994},
    volume      = {20},
    pages       = {163--177},
    doi         = {10.1145/178365.178368},
    abstract    = {We describe the GFUN package which contains functions for
  manipulating sequences, linear recurrences, or differential equations and
  generating functions of various types. This article is intended both as an
  elementary introduction to the subject and as a reference manual for the
  package.},
}

@inproceedings{BrSa93,
    author      = {Bronstein, Manuel and Salvy, Bruno},
    title       = {Full Partial Fraction Decomposition of Rational
  Functions},
    booktitle   = {ISSAC'93},
    year        = {1993},
    month       = {July},
    editor      = {Bronstein, Manuel},
    publisher   = {ACM Press},
    address     = {New York},
    pages       = {157--160},
    doi         = {10.1145/164081.164114},
    abstract    = {We describe a rational algorithm that computes the full
  partial fraction expansion of a rational function over the algebraic closure
  of its field of definition. The algorithm uses only gcd operations over the
  initial field but the resulting decomposition is expressed with linear
  denominators. We give examples from its Axiom and Maple implementations.},
}

@techreport{Salvy93b,
    author      = {(editor), Bruno Salvy},
    title       = {Algorithms Seminar, 1992–1993},
    number      = {2130},
    year        = {1993},
    month       = {December},
    institution = {Institut National de Recherche en Informatique et en
  Automatique},
    url         = {http://www.inria.fr/rrrt/rr-2130.html},
    abstract    = {These seminar notes represent the proceedings (some in
  French) of a seminar devoted to the analysis of algorithms and related
  topics. The subjects covered include combinatorial models and random
  generation, symbolic computati- on, asymptotic analysis, average-case
  analysis of algorithms and data structures and some computational number
  theory.},
}

@article{FlSa93,
    author      = {Flajolet, Philippe and Salvy, Bruno},
    title       = {A Finite Sum of Products of Binomial Coefficients},
    journal     = {SIAM Review},
    number      = {4},
    year        = {1993},
    volume      = {35},
    pages       = {645–646},
    keywords    = {holonomic functions},
    note        = {Solution to Problem 92–18 by C. C. Grosjean},
    doi         = {10.1137/1035147},
    url         = {http://locus.siam.org/fulltext/SIREV/volume-35/1035147.pdf},
}

@article{FlGoSa93,
    author      = {Flajolet, Philippe and Gourdon, Xavier and Salvy, Bruno},
    title       = {Sur une famille de polyn{\^o}mes issus de l'analyse
  num{\'e}rique},
    journal     = {Gazette des Math{\'e}maticiens},
    year        = {1993},
    month       = {January},
    volume      = {55},
    pages       = {67--78},
    keywords    = {polynomials, special functions, asymptotics, zeros},
}

@inproceedings{GourdonSalvy1993,
    author      = {Gourdon, Xavier and Salvy, Bruno},
    title       = {Asymptotics of linear recurrences with rational
  coefficients},
    booktitle   = {Formal Power Series and Algebraic Combinatorics},
    year        = {1993},
    editor      = {Barlotti, A. and Delest, M. and Pinzani, R.},
    pages       = {253--266},
    note        = {Proceedings of FPSAC'5, Florence (Italy). An extended
  version appeared in Discrete Mathematics, 1996.},
    abstract    = {We give algorithms to compute the asymptotic expansion of
  solutions of linear recurrences with rational coefficients and initial
  conditions in polynomial time in the order of the recurrence.},
}

@article{GourdonSalvy1993a,
    author      = {Gourdon, Xavier and Salvy, Bruno},
    title       = {Computing one million digits of $\sqrt{2}$},
    journal     = {The Maple Technical Newsletter},
    year        = {1993},
    volume      = {10},
    pages       = {66--71},
    abstract    = {We describe how the knowledge of Maple's internal data
  structure can be used to compute the first million digits of $\sqrt{2}$
  efficiently.},
}

@inproceedings{PeSa93,
    author      = {Petkov{\v s}ek, Marko and Salvy, Bruno},
    title       = {Finding all hypergeometric solutions of linear differential
  equations},
    booktitle   = {ISSAC'93},
    year        = {1993},
    month       = {July},
    editor      = {Bronstein, Manuel},
    publisher   = {ACM Press},
    address     = {New York},
    pages       = {27--33},
    doi         = {10.1145/164081.164087},
    abstract    = {Hypergeometric sequences are such that the quotient of two
  successive terms is a fixed rational function of the index. We give a
  generalization of M.~Petkov{\v s}ek's algorithm to find all hypergeometric
  sequence solutions of linear recurrences, and we describe a program to find
  all hypergeometric functions that solve a linear differential equation.},
}

@article{Salvy93,
    author      = {Salvy, Bruno},
    title       = {Efficient programming in {M}aple: a case study},
    journal     = {SIGSAM Bulletin},
    number      = {2},
    year        = {1993},
    month       = {April},
    volume      = {27},
    pages       = {1--12},
    doi         = {10.1145/165474.165477},
    abstract    = {Studying the computation of orbits of some given group
  acting on a set, we show how successive refinements of a simple program
  provide a speedup factor of up to 200. The initial program cannot solve the
  problem at all, it is first converted into a program which needs one c.p.u.
  week and after all the optimizations have been performed, the computation
  takes only four hours. Although the problem is specific, we shall show that
  many of the optimizations we use are of interest for other problems as
  well.},
}

@inproceedings{BergeronFlajoletSalvy1992,
    author      = {Bergeron, Fran{\c c}ois and Flajolet, Philippe and Salvy,
  Bruno},
    title       = {Varieties of Increasing Trees},
    booktitle   = {CAAP'92},
    year        = {1992},
    editor      = {Raoult, J.-C.},
    volume      = {581},
    series      = {Lecture Notes in Computer Science},
    pages       = {24--48},
    note        = {Proceedings of the 17th Colloquium on Trees in Algebra and
  Programming, Rennes, France, February 1992.},
    doi         = {10.1007/3-540-55251-0_2},
    abstract    = {An increasing tree is a labelled rooted tree in which
  labels along any branch from the root go in increasing order. Under various
  guises, such trees have surfaced as tree representations of permutations, as
  data structures in computer science, and as probabilistic models in diverse
  applications. We present a unified generating function approach to the
  enumeration of parameters on such trees. The counting generating functions
  for several basic parameters are shown to be related to a simple ordinary
  differential equation $$ {d\over dz}Y(z)=\phi(Y(z)),$$ which is non linear
  and autonomous. Singularity analysis applied to the intervening generating
  functions then permits to analyze asymptotically a number of parameters of
  the trees, like: root degree, number of leaves, path length, and level of
  nodes. In this way it is found that various models share common features:
  path length is $O(n\log n)$, the distributions of node levels and number of
  leaves are asymptotically normal, etc.},
}

@inproceedings{Salvy1992,
    author      = {Salvy, Bruno},
    title       = {General Asymptotic Scales and Computer Algebra},
    booktitle   = {Asymptotic and Numerical Methods for Partial Differential
  Equations, Critical Parameters and Domain Decomposition},
    year        = {1992},
    editor      = {Kaper, H. and Garbey, M.},
    publisher   = {Kluwer Academic Publishers},
    note        = {Proceedings of a NATO Advanced Research Workshop, Beaune,
  France, May 1992.},
    abstract    = {In many natural applications, one encounters asymptotic
  expansions of a form more complicated than mere Puiseux series. Existing
  computer algebra systems lack good algorithms for handling such asymptotic
  expansions. We present tools that permit the representation and automatic
  handling of general exp-log asymptotic expansions.},
}

@inproceedings{SaSh92,
    author      = {Salvy, Bruno and Shackell, John},
    title       = {Asymptotic expansions of functional inverses},
    booktitle   = {Symbolic and Algebraic Computation},
    year        = {1992},
    editor      = {Wang, Paul S.},
    publisher   = {ACM Press},
    address     = {New York},
    pages       = {130--137},
    note        = {Proceedings of ISSAC'92, Berkeley, July 1992.},
    doi         = {10.1145/143242.143292},
    abstract    = {We study the automatic computation of asymptotic expansions
  of functional inverses. Based on previous work on asymptotic expansions, we
  give an algorithm which computes Hardy-field solutions of equations~$f(y)=x$,
  with~$f$ belonging to a large class of functions.},
}

@article{FlajoletSalvyZimmermann1991,
    author      = {Flajolet, Philippe and Salvy, Bruno and Zimmermann, Paul},
    title       = {Automatic Average-case Analysis of Algorithms},
    journal     = {Theoretical Computer Science, Series A},
    number      = {1},
    year        = {1991},
    month       = {February},
    volume      = {79},
    pages       = {37--109},
    doi         = {10.1016/0304-3975(91)90145-R},
    abstract    = {Many probabilistic properties of elementary discrete
  combinatorial structures of interest for the average-case analysis of
  algorithms prove to be decidable. This paper presents a general framework in
  which such decision procedures can be developed. It is based on a combination
  of generating function techniques for counting, and complex analysis
  techniques for asymptotic estimations. We expose here the theory of exact
  analysis in terms of generating functions for four different domains: the
  iterative/recursive and unlabelled/labelled data type domains. We then
  present some major components of the associated asymptotic theory and exhibit
  a class of naturally arising functions that can be automatically analyzed. A
  fair fragment of this theory is also incorporated into a system called
  Lambda-Upsilon-Omega. In this way, using computer algebra, one can produce
  automatically non-trivial average-case analyses of algorithms operating over
  a variety of ``decomposable'' combinatorial structures. At a fundamental
  level, this paper is part of a global attempt at understanding why so many
  elementary combinatorial problems tend to have elementary asymptotic
  solutions. In several cases, it proves possible to relate entire classes of
  elementary combinatorial problems whose structure is well defined with
  classes of elementary ``special'' functions and classes of asymptotic forms
  relative to counting, probabilities, or average-case complexity.},
}

@article{Salvy91b,
    author      = {Salvy, B.},
    title       = {Examples of automatic asymptotic expansions},
    journal     = {SIGSAM Bulletin},
    number      = {2},
    year        = {1991},
    month       = {April},
    volume      = {25},
    pages       = {4--17},
    doi         = {10.1145/122520.122521},
    abstract    = {We describe the current state of a Maple library, gdev,
  designed to perform asymptotic expansions for a large class of expressions.
  Many examples are provided, along with a short sketch of the underlying
  principles. At the time when this report is written, a striking feature of
  these examples is that none of them can be computed directly with any of
  today's most widespread symbolic computation systems (Macsyma (Sun Release
  309.6), Mathematica (Version 1.2, beta test), Maple (Version 4.3) or
  Scratchpad~II (Version 4J)).},
}

@phdthesis{Salvy1991b,
    author      = {Salvy, Bruno},
    title       = {Asymptotique automatique et fonctions
  g{\'e}n{\'e}ratrices},
    year        = {1991},
    school      = {{\'E}cole polytechnique},
    keywords    = {asymptotic analysis, automatic asymptotics, computer
  algebra},
    abstract    = {The purpose of this thesis is to partially automate
  asymptotic analysis. We first describe the mathematical objects that underlie
  asymptotic expansions, and then introduce the data structures and algorithms
  that correspond to them. With these tools, the second chapter shows the
  automation of the asymptotic expansion of integrals, for a wide class of
  integrands. The second part of this thesis is devoted to the analysis of
  integral variables. We recall the main properties of generating functions,
  and present in detail the automatic extraction of asymptotic information
  about their coefficients by purely syntactical operations. This constitutes
  the analytical part of the~LUO system. This system, developed with
  P.~Zimmermann, is capable of producing non-trivial average-case analyses of
  algorithms and parameters of combinatorial structures. In our last chapter,
  we describe its principles and scrutinize a variety of examples to explain
  its use and working.},
}

@article{Salvy91c,
    author      = {Salvy, Bruno},
    title       = {Three ways to get {S}tirling's formula in {M}aple},
    journal     = {The Maple Technical Newsletter},
    year        = {1991},
    volume      = {5},
    pages       = {32--42},
}

@inproceedings{FlajoletSalvyZimmermann1989,
    author      = {Flajolet, P. and Salvy, B. and Zimmermann, P.},
    title       = {{L}ambda-{U}psilon-{O}mega: An Assistant Algorithms
  Analyzer},
    booktitle   = {Applied Algebra, Algebraic Algorithms and Error-Correcting
  Codes},
    year        = {1989},
    editor      = {Mora, T.},
    volume      = {357},
    series      = {Lecture Notes in Computer Science},
    pages       = {201--212},
    note        = {Proceedings AAECC'6, Rome, July 1988},
    doi         = {10.1007/3-540-51083-4_60},
    abstract    = {Lambda-Upsilon-Omega, LUO, is a system designed to perform
  automatic analysis of well-defined classes of algorithms operating over
  decomposable data structures. It consists of an Algebraic Analyzer System
  that compiles algorithms specifications into generating functions of average
  costs, and an Analytic Analyzer System that extracts asymptotic informations
  on coefficients of generating functions. The algebraic part relies on recent
  methodologies in combinatorial analysis based on systematic correspondences
  between structural type definitions and counting generating functions. The
  analytic part makes use of partly classical and partly new correspondences
  between singularities of analytic functions and the growth of their Taylor
  coefficients. The current version LUO0 of LUO implements as basic data types,
  term trees as encountered in symbolic algebra systems. The analytic analyzer
  can treat large classes of functions with explicit expressions. In this way,
  LUO0 can generate in the current stage about a dozen non-trivial average case
  analyses of algorithms like: formal differentiation, some algebraic
  simplification and matching algorithms. Its analytic analyzer can determine
  asymptotic expansions for large classes of generating functions arising in
  the analysis of algorithms. The outline of a design for a full system is also
  discussed here. The long term goal is to include a fairly rich set of data
  structuring mechanisms including some general recursive type definitions, and
  have the analytic analyzer treat wide classes of functional equations as may
  be encountered in combinatorial analysis and the analysis of algorithms.},
}

@techreport{FlajoletSalvyZimmermann1989a,
    author      = {Flajolet, P. and Salvy, B. and Zimmermann, P.},
    title       = {Lambda-Upsilon-Omega: The 1989 CookBook},
    number      = {1073},
    year        = {1989},
    month       = {August},
    institution = {Institut National de Recherche en Informatique et en
  Automatique},
    note        = {116 pages},
    url         = {http://www.inria.fr/rrrt/rr-1073.html},
    abstract    = {Lambda-Upsilon-Omega (LUO) is a research tool designed to
  assist the average case analysis of some well defined classes of algorithms
  and data structures. This cookbook consists of an informal introduction to
  the system together with eighteen examples of programmes that are
  automatically analyzed. Amongst the applications treated here, we find:
  addition chains, quantitative concurrency analysis of simple systems,
  symbolic manipulation algorithms such as formal differentiation,
  simplification and rewriting systems, as well as combinatorial models
  including various tree and permutation statistics and functional graphs with
  applications to integer factorisation.},
}

@techreport{Salvy88,
    author      = {Salvy, B.},
    title       = {Fonctions génératrices et asymptotique
  automatique},
    year        = {1988},
    institution = {Université Paris XI},
    note        = {Also available as INRIA Research Report 967 (1989)},
    url         = {http://www.inria.fr/rrrt/rr-0967.html},
}