|
|
Publications by the Algorithms Project |
| Welcome! | Research Topics | People | Publications | Seminars | Software | On-Line Applications | Jobs & Internships |
| Algo's Publication List | Books | Case Studies |
Beside the publication list below, you can also access the publications by the project's permanent members author by author:
| Alin Bostan | Nicolas Broutin |
| Frédéric Chyzak | Philippe Flajolet |
| Bruno Salvy |
Here is also a list of theses prepared, defended, directed or co-directed in the project.
@article{BrFa2011a,
author = {Broutin, N. and Fawzi, O.},
title = {{Longest distance in random circuits}},
journal = {Combinatorics, Probability and Computing},
year = {To appear},
arxiv = {abs/1101.5547},
}
@article{BrHo2011a,
author = {Broutin, N. and Holmgren, C.},
title = {{The total path length of split trees}},
journal = {The Annals of Applied Probability},
year = {To appear},
keywords = {path length, random tree},
arxiv = {abs/1102.2541},
}
@article{BrMa2012a,
author = {Broutin, N. and Marckert, J.-F.},
title = {{Asymptotics of trees with a prescribed degree sequence and
applications}},
journal = {Random Structures and Algorithms},
year = {To appear},
keywords = {CRT, random tree},
arxiv = {abs/1110.5203},
}
@article{BrDeFrLu2011a,
author = {Broutin, N. and Devroye, L. and Fraiman, N. and Lugosi,
G.},
title = {{Connectivity threshold for Bluetooth graphs}},
journal = {Random Structures and Algorithms},
year = {To appear},
keywords = {geometric graph, network, Bluetooth},
arxiv = {abs/1103.0351},
}
@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.},
}
@article{AdBrGo2012a,
author = {Addario-Berry, L. and Broutin, N. and Goldschmidt, C.},
title = {{The continuum limit of critical random graphs}},
journal = {Probability Theory and Related Fields},
year = {2012},
volume = {152},
pages = {367--406},
keywords = {scaling limit, CRT, Brownian, random graph, diameter},
doi = {10.1007/s00440-010-0325-4},
arxiv = {abs/0903.4730},
}
@inproceedings{BeBoHo12,
author = {Benoit, Alexandre and Bostan, Alin and van der Hoeven,
Joris},
title = {Quasi-optimal multiplication of linear differential
operators},
booktitle = {FOCS'12 (53rd Annual Symposium on Foundations of Computer
Science)},
year = {2012},
publisher = {IEEE},
pages = {524--530},
arxiv = {abs/1205.3414},
abstract = {We show that linear differential operators with polynomial
coefficients over a field of characteristic zero can be multiplied in
quasi-optimal time. This answers an open question raised by van der
Hoeven.},
}
@article{BoCo12,
author = {Bostan, Alin and Combot, Thierry},
title = {A binomial-like matrix equation},
journal = {American Mathematical Monthly},
number = {7},
year = {2012},
volume = {119},
pages = {593--597},
abstract = {We show that a pair of matrices satisfying a certain
algebraic identity, reminiscent of the binomial theorem, must have the same
characteristic polynomial. This is a generalization of Problem 4 (11th grade)
from the Romanian National Mathematical Olympiad 2011.},
}
@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{BrFl2012a,
author = {Broutin, N. and Flajolet, P.},
title = {The distribution of the height and diameter in random
non-plane binary trees},
journal = {Random Structures \& Algorithms},
year = {2012},
volume = {41},
pages = {215--252},
keywords = {height, diameter, limiting distribution},
arxiv = {abs/1009.1515},
}
@unpublished{BrNeSu2012b,
author = {Broutin, N. and Neininger, R. and Sulzbach, H.},
title = {{A limit process for partial match queries in random
quadtrees}},
year = {2012},
keywords = {partial match},
note = {Submitted},
arxiv = {abs/1202.1342},
}
@inproceedings{BrNeSu2012a,
author = {Broutin, N. and Neininger, R. and Sulzbach, H.},
title = {{Partial match queries in random quadtrees}},
booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete
Algorithms (SODA)},
year = {2012},
editor = {Rabani, Y.},
pages = {1056--1065},
keywords = {partial match},
arxiv = {abs/1107.2231},
}
@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.},
}
@article{AdBr2011a,
author = {Addario-Berry, L. and Broutin, N.},
title = {Total progeny in killed branching random walk},
journal = {Probability Theory and Related Fields},
year = {2011},
volume = {151},
pages = {265--295},
keywords = {branching random walk, large deviation},
arxiv = {abs/0908.1083},
}
@unpublished{AdBrHo2011a,
author = {Addario-Berry, L. and Broutin, N. and Holmgren, C.},
title = {{Cutting down trees with a Markov chainsaw}},
year = {2011},
note = {Submitted},
arxiv = {abs/1110.6455},
}
@article{BlasiakFlajolet2011,
author = {Blasiak, Pawel and Flajolet, Philippe},
title = {Combinatorial models of creation-annihilation},
journal = {Séminaire Lotharingien de Combinatoire},
number = {B65c},
year = {2011},
volume = {65},
pages = {1–78},
url = {http://www.emis.de/journals/SLC/wpapers/s65blafla.pdf},
abstract = {Quantum physics has revealed many interesting formal
properties associated with the algebra of two operators, A and B, satisfying
the partial commutation relation AB-BA=1. This study surveys the
relationships between classical combinatorial structures and the reduction to
normal form of operator polynomials in such an algebra. The connection is
achieved through suitable labelled graphs, or "diagrams", that are composed
of elementary "gates". In this way, many normal form evaluations can be
systematically obtained, thanks to models that involve set partitions,
permutations, increasing trees, as well as weighted lattice paths. Extensions
to q-analogues, multivariate frameworks, and urn models are also briefly
discussed.},
}
@article{BBHHMWZ10,
author = {Bostan, A. and Boukraa, S. and Hassani, S. and van Hoeij,
M. and Maillard, J.-M. and Weil, J.-A. and Zenine, N.},
title = {The {I}sing model: from elliptic curves to modular forms
and {C}alabi-{Y}au equations},
journal = {Journal of Physics A: Mathematical and Theoretical},
number = {4},
year = {2011},
volume = {44},
pages = {44pp},
doi = {10.1088/1751-8113/44/4/045204},
arxiv = {abs/1007.0535},
abstract = {We show that almost all the linear differential operators
factors obtained in the analysis of the $\, n$-particle contributions $\,
{\tilde \chi}^{(n)}$'s of the susceptibility of the Ising model for $\, n \le
6$, are linear differential operators ``{\em associated with elliptic
curves}''. Beyond the simplest differential operators factors which are
homomorphic to symmetric powers of the second order operator associated with
the complete elliptic integral $\, E$, the second and third order
differential operators $\, Z_2$, $\, F_2$, $\, F_3$, $\, {\tilde L}_3$ can
actually be interpreted as {\em modular forms} of the elliptic curve of the
Ising model. A last order-four globally nilpotent linear differential
operator is not reducible to this elliptic curve, modular forms scheme. This
operator is shown to actually correspond to a natural generalization of this
elliptic curve, modular forms scheme, with the emergence of a Calabi-Yau
equation, corresponding to a selected $_4F_3$ hypergeometric function. This
hypergeometric function can also be seen as a Hadamard product of the
complete elliptic integral $\, K$, with a remarkably simple algebraic
pull-back (square root extension), the corresponding Calabi-Yau fourth-order
differential operator having a symplectic differential Galois group $\, SP(4,
\, \mathbb{C})$. The mirror maps and higher order Schwarzian ODEs, associated
with this Calabi-Yau ODE, present all the nice physical and mathematical
ingredients we had with elliptic curves and modular forms, in particular an
exact (isogenies) representation of the generators of the renormalization
group, extending the modular group $SL(2, \, \mathbb{Z})$ to a $GL(2, \,
\mathbb{Z})$ symmetry group.},
}
@article{BoChHoSc10,
author = {A. Bostan and M.F.I. Chowdhury and J. van der Hoeven and
{\'E}. Schost},
title = {Homotopy methods for multiplication modulo triangular
sets},
journal = {Journal of Symbolic Computation},
number = {12},
year = {2011},
volume = {46},
pages = {1378--1402},
abstract = {We study the cost of multiplication modulo triangular
families of polynomials. Following previous work by Li, Moreno Maza and
Schost, we propose an algorithm that relies on homotopy and fast
evaluation-interpolation techniques. We obtain a quasi-linear time complexity
for substantial families of examples, for which no such result was known
before. Applications are given to notably addition of algebraic numbers in
small characteristic.},
}
@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},
}
@article{Bostan-2011-EFG,
author = {Bostan, Alin and Chyzak, Frédéric and van Hoeij, Mark and
Pech, Lucien},
title = {Explicit formula for the generating series of diagonal 3D
rook paths},
journal = {Sém. Loth. Comb.},
year = {2011},
volume = {B66a},
note = {27 pages},
url = {http://www.emis.de/journals/SLC/wpapers/s66bochhope.html},
abstract = {Let an denote the number of ways in which a chess rook
can move from a corner cell to the opposite corner cell of an n times n
times n three-dimensional chessboard, assuming that the piece moves closer
to the goal cell at each step. We describe the computer-driven
discovery and proof of the fact that the generating series G(x)=
sum n geq 0 an xn admits the following explicit expression in terms of
a Gaussian hypergeometric function: G(x) = 1 + 6 ⋅ int _0^x frac
pFq 211/32/32 frac 27 w(2-3w)(1-4w)^3(1-4w)(1-64w) dw.
},
}
@phdthesis{Chen2011,
author = {Chen, Shaoshi},
title = {Quelques applications de l'algèbre différentielle et aux
différences pour le télescopage créatif},
year = {2011},
month = {February},
school = {École polytechnique (Palaiseau, France)},
note = {Defended on February 16, 2011},
url = {http://algo.inria.fr/papers/pdf/Chen-2011-SAD.pdf},
abstract = {Since the 1990's, Zeilberger's method of creative
telescoping has played an important role in the automatic verification of
special-function identities. The long-term goal initiated in this work is to
obtain fast algorithms and implementations for definite integration and
summation in the framework of this method. Our contributions include new
practical algorithms, complexity analyses of algorithms, and theoretical
criteria for the termination of existing algorithms. On the practical side,
we present a new algorithm for computing minimal telescopers for bivariate
rational functions. This algorithm is based on Hermite reduction. We also
improve the classical Almkvist and Zeilberger's algorithm for
rational-function inputs. The Hermite-reduction based algorithm and improved
Almkvist and Zeilberger's algorithm are analyzed in terms of field
operations. Both complexity analysis and experimental results show that our
algorithms are superior to other known ones for rational-function inputs. On
the theoretic side, we present a structure theorem for multivariate
hyperexponential-hypergeometric functions. This theorem is based on
(multivariate) Christoper's theorem for hyperexponential functions, the
Ore-Sato theorem for hypergeometric terms, and our generalization of a recent
result by Feng, Singer, and Wu on compatible bivariate continuous-discrete
rational functions. The structure theorem allows us to decomposes a
hyperexponential-hypergeometric function as a product of a rational function,
several exponential and power functions, and factorial terms. Furthermore, we
derive two criteria for the existence of telescopers for bivariate
hyperexponential-hypergeometric functions: one is with respect to the
continuous variable, and the other with respect to the discrete one. The two
criteria solve the termination problems of the continuous-discrete analogue
of Zeilberger's algorithms.},
}
@inproceedings{Chyzak-2011-UCP,
author = {Chyzak, Frédéric and Darrasse, Alexis},
title = {Using Camlp4 for presenting dynamic mathematics on the
web: DynaMoW, an OCaml language extension for the run-time generation of
mathematical contents and their presentation on the web},
booktitle = {ICFP'11 (September 19–21, 2011, Tokyo, Japan)},
year = {2011},
editor = {Danvy, Olivier},
publisher = {ACM},
pages = {259–265},
note = {(An experience report.)},
url = {http://ddmf.msr-inria.inria.fr/download/DynaMoW-ICFP11.pdf},
abstract = {We report on the design and implementation of a programming
tool, DynaMoW, to control interactive and incremental mathematical
calculations to be presented on the web. This tool is implemented as a
language extension of OCaml using Camlp4. Fragments of mathematical code
written for a computer-algebra system as well as fragments of mathematical
web documents are embedded directly and naturally inside OCaml code. A
DynaMoW-based application is made of independent web services, whose
parameter types are checked by the OCaml extension. The approach is
illustrated by two implementations of online mathematical encyclopedias on
top of DynaMoW.},
}
@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{FlajoletPelletierSoria2011,
author = {Flajolet, Philippe and Pelletier, Maryse and Soria,
Michèle},
title = {On Buffon Machines and Numbers},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms},
year = {2011},
editor = {Randall, Dana},
pages = {172–183},
note = {Proceedings of the Twenty-Second Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), January 2011, San Francisco.},
url = {http://www.siam.org/proceedings/soda/2011/SODA11_015_flajoletp.pdf},
}
@phdthesis{Mezzarobba2011,
author = {Mezzarobba, Marc},
title = {Autour de l'évaluation numérique des fonctions
D-finies},
year = {2011},
month = {November},
address = {Palaiseau, France},
school = {École polytechnique},
url = {http://algo.inria.fr/papers/pdf/these-mezzarobba-preliminaire.pdf},
}
@article{AdBrDeLu2010,
author = {Addario-Berry, L. and Broutin, N. and Devroye, L. and
Lugosi, G.},
title = {On combinatorial testing problems},
journal = {The Annals of Statistics},
year = {2010},
volume = {38},
pages = {3063--3092},
keywords = {statistics},
arxiv = {abs/0908.3437},
}
@article{AdBrGo2010,
author = {Addario-Berry, L. and Broutin, N. and Goldschmidt, C.},
title = {Critical random graphs: limiting constructions and
distributional properties},
journal = {Electronic Journal of Probability},
year = {2010},
volume = {15},
pages = {741--775},
keywords = {random graph, CRT},
arxiv = {abs/0908.3629},
}
@article{AdBrLu2010,
author = {Addario-Berry, L. and Broutin, N. and Lugosi, G.},
title = {The longest minimum weight path in a complete graph},
journal = {Combinatorics, Probability and Computing},
year = {2010},
volume = {19},
pages = {1--19},
keywords = {recursive tree, random graph},
doi = {10.1017/S0963548309990204},
}
@article{BaFl10,
author = {Bacher, Roland and Flajolet, Philippe},
title = {Pseudo-factorials, elliptic functions, and continued
fractions},
journal = {Ramanujan J.},
number = {1},
year = {2010},
volume = {21},
pages = {71–97},
doi = {10.1007/s11139-009-9186-9},
url = {http://dx.doi.org/10.1007/s11139-009-9186-9},
}
@article{BeFlGu10,
author = {Beaton, Nicholas R. and Flajolet, Philippe and Guttmann,
Anthony J.},
title = {The unusual asymptotics of three-sided prudent polygons},
journal = {J. Phys. A},
number = {34},
year = {2010},
volume = {43},
pages = {342001, 10},
doi = {10.1088/1751-8113/43/34/342001},
url = {http://dx.doi.org/10.1088/1751-8113/43/34/342001},
}
@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{BoFuPi10,
author = {Bodini, Olivier and Fusy, Éric and Pivoteau, Carine},
title = {Random sampling of plane partitions},
journal = {Combin. Probab. Comput.},
number = {2},
year = {2010},
volume = {19},
pages = {201–226},
doi = {10.1017/S0963548309990332},
arxiv = {abs/0712.0111},
url = {http://dx.doi.org/10.1017/S0963548309990332},
}
@inproceedings{Bostan10,
author = {Bostan, Alin},
title = {Algorithmes rapides pour les polynômes, séries
formelles et matrices},
booktitle = {Actes des Journées Nationales de Calcul Formel},
year = {2010},
address = {Luminy, France},
pages = {75–262},
note = {Les cours du CIRM, tome 1, numéro 2},
url = {http://ccirm.cedram.org:80/ccirm-bin/fitem?id=CCIRM_2010__1_2_75_0},
}
@article{BoDu10,
author = {Bostan, Alin and Dumas, Philippe},
title = {{W}ronskians and linear independence},
journal = {American Mathematical Monthly},
number = {8},
year = {2010},
volume = {117},
pages = {722--727},
abstract = {We give a new and simple proof of the fact that a finite
family of analytic functions has a zero Wronskian only if it is linearly
dependent.},
}
@article{BoKa10,
author = {Bostan, Alin and Kauers, Manuel},
title = {The complete generating function for {G}essel walks is
algebraic},
journal = {Proceedings of the American Mathematical Society},
number = {9},
year = {2010},
month = {September},
volume = {138},
pages = {3063--3078},
note = {With an Appendix by Mark van Hoeij},
arxiv = {abs/0909.1965},
abstract = {Gessel walks are lattice walks in the quarter plane $\set
N^2$ which start at the origin~$(0,0)\in\set N^2$ and consist only of steps
chosen from the set
${\leftarrow,\penalty0\swarrow,\penalty0\nearrow,\penalty0\rightarrow}$. We
prove that if $g(n;i,j)$ denotes the number of Gessel walks of length~$n$
which end at the point~$(i,j)\in\set N^2$, then the trivariate generating
series $\displaystyle\smash{ G(t;x,y)=\sum_{n,i,j\geq 0} g(n;i,j)x^i y^j t^n
}$ is an algebraic function.},
}
@article{BBHMWZA10,
author = {Bostan, A. and Boukraa, S. and Hassani, S. and Maillard,
J.-M. and Weil, J.-A. and Zenine, N. and Abarenkova, N.},
title = {Renormalization, isogenies and rational symmetries of
differential equations},
journal = {Advances in Mathematical Physics},
year = {2010},
volume = {2010},
pages = {44pp},
doi = {10.1155/2010/941560},
arxiv = {abs/0911.5466},
abstract = {We give an example of infinite order rational
transformation that leaves a linear differential equation covariant. This
example can be seen as a non-trivial but still simple illustration of an
exact representation of the renormalization group.},
}
@inproceedings{BoChChLi10,
author = {Bostan, Alin and Chen, Shaoshi and Chyzak, Fr\'{e}d\'{e}ric
and Li, Ziming},
title = {Complexity of creative telescoping for bivariate rational
functions},
booktitle = {ISSAC'10: Proceedings of the 2010 International Symposium
on Symbolic and Algebraic Computation},
year = {2010},
publisher = {ACM},
address = {New York, NY, USA},
pages = {203--210},
doi = {http://doi.acm.org/10.1145/1837934.1837975},
abstract = {The long-term goal initiated in this work is to obtain fast
algorithms and implementations for definite integration in Almkvist and
Zeilberger's framework of (differential) creative telescoping. Our
complexity-driven approach is to obtain tight degree bounds on the various
expressions involved in the method. To make the problem more tractable, we
restrict to \emph{bivariate rational\/} functions. By considering this
constrained class of inputs, we are able to blend the general method of
creative telescoping with the well-known Hermite reduction. We then use our
new method to compute diagonals of rational power series arising from
combinatorics.},
}
@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{BrDeMc2010,
author = {Broutin, N. and Devroye, L. and McLeish, E.},
title = {{Note on the structure of Kruskal's algorithm}},
journal = {Algorithmica},
year = {2010},
volume = {56},
pages = {141--156},
keywords = {mst, height, tree, euclidean, percolation},
}
@book{sagebook-1.0,
author = {Alexandre Casamayou and Guillaume Connan and Thierry Dumont
and Laurent Fousse and François Maltey and Matthias Meulien and Marc
Mezzarobba and Clément Pernet and Nicolas M. Thiéry and Paul
Zimmermann},
title = {Calcul mathématique avec Sage},
year = {2010},
url = {http://sagebook.gforge.inria.fr/},
}
@mastersthesis{Panafieu2010,
author = {Elie de Panafieu},
title = {Complexit\'e et qualit\'e du d\'ecouplage obtenu par la
m\'ethode du vecteur cyclique},
year = {2010},
month = {ao\^ut},
school = {\'Ecole Normale Sup\'erieure},
note = {26 pages},
}
@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.},
}
@inproceedings{FlRoVa10,
author = {Flajolet, Philippe and Roux, Mathieu and Vallée,
Brigitte},
title = {Digital Trees and Memoryless Sources: from
Arithmetics to Analysis},
booktitle = {DMTCS Proceedings of the 21st International Meeting on
Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of
Algorithms (AofA'10)},
year = {2010},
pages = {233–260},
url = {http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0117/3289},
}
@inproceedings{Lumbroso10,
author = {Lumbroso, J{\'e}r{\'e}mie},
title = {An optimal cardinality estimation algorithm based on order
statistics and its full analysis},
booktitle = {DMTCS Proceedings of the 21st International Meeting on
Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of
Algorithms (AofA'10)},
year = {2010},
pages = {489--504},
}
@inproceedings{Mezzarobba2010,
author = {Mezzarobba, Marc},
title = {Num{G}fun: a Package for Numerical and Analytic Computation
with {D}-finite Functions},
booktitle = {Proceedings of the 2010 International Symposium on Symbolic
and Algebraic Computation (ISSAC 2010)},
year = {2010},
publisher = {ACM},
institution = {arXiv},
pages = {139--145},
doi = {10.1145/1837934.1837965},
arxiv = {abs/1002.3077},
abstract = {This article describes the implementation in the software
package NumGfun of classical algorithms that operate on solutions of linear
differential equations or recurrence relations with polynomial coefficients,
including what seems to be the first general implementation of the fast
high-precision numerical evaluation algorithms of Chudnovsky and Chudnovsky.
In some cases, our descriptions contain small improvements over existing
algorithms. We also provide references to relevant ideas not currently used
in NumGfun.},
}
@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.},
}
@article{AdBrLu2009,
author = {Addario-Berry, L. and Broutin, N. and Lugosi, G.},
title = {Effective resistance of random trees},
journal = {The Annals of Applied Probability},
year = {2009},
volume = {19},
pages = {1092--1107},
keywords = {branching process, resistance},
doi = {10.1214/08-AAP572},
arxiv = {abs/0801.1909},
}
@article{AdBrRe2009,
author = {Addario-Berry, L. and Broutin, N. and Reed, B.},
title = {Critical random graphs and the structure of a minimum
spanning tree},
journal = {Random Structures Algorithms},
year = {2009},
volume = {35},
pages = {323--347},
keywords = {diameter, random walk, MST},
doi = {10.1002/rsa.20241},
}
@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.},
}
@incollection{BoLu09,
author = {Bodini, Olivier and Lumbroso, J{\'e}r{\'e}mie},
title = {Optimal partial tiling of {M}anhattan polyominoes},
booktitle = {Discrete geometry for computer imagery},
year = {2009},
publisher = {Springer},
volume = {5810},
series = {Lecture Notes in Comput. Sci.},
address = {Berlin},
pages = {79--91},
}
@article{BoFl09,
author = {Bóna, Miklós and Flajolet, Philippe},
title = {Isomorphism and symmetries in random phylogenetic trees},
journal = {J. Appl. Probab.},
number = {4},
year = {2009},
volume = {46},
pages = {1005–1019},
doi = {10.1239/jap/1261670685},
url = {http://dx.doi.org/10.1239/jap/1261670685},
}
@inproceedings{BoKa09,
author = {Bostan, Alin and Kauers, Manuel},
title = {Automatic classification of restricted lattice walks},
booktitle = {DMTCS Proceedings of the 21st International Conference on
Formal Power Series and Algebraic Combinatorics (FPSAC'09), Hagenberg,
Austria},
year = {2009},
pages = {203--217},
arxiv = {abs/0811.2899},
abstract = {We propose an experimental mathematics approach leading to
the computer-driven discovery of various conjectures about structural
properties of generating functions coming from enumeration of 2D and 3D
lattice walks.},
}
@inproceedings{BoSc09b,
author = {Bostan, Alin and Schost, {\'E}ric},
title = {Fast algorithms for differential equations in positive
characteristic},
booktitle = {ISSAC'09},
year = {2009},
editor = {May, John},
pages = {47--54},
doi = {10.1145/1576702.1576712},
arxiv = {abs/ 0901.3843},
abstract = {We address complexity issues for linear differential
equations in characteristic $p>0$: resolution and computation of the
$p$-curvature. For these tasks, our main focus is on algorithms whose
complexity behaves well with respect to $p$. We prove bounds linear in $p$ on
the degree of polynomial solutions and propose algorithms for testing the
existence of polynomial solutions in sublinear time $\tilde{O}(p^{1/2})$, and
for determining a whole basis of the solution space in quasi-linear time
$\tilde{O}(p)$; the $\tilde{O}$ notation indicates that we hide logarithmic
factors. We show that for equations of arbitrary order, the $p$-curvature can
be computed in subquadratic time $\tilde{O}(p^{1.79})$, and that this can be
improved to $O(\log(p))$ for first order equations and to $\tilde{O}(p)$ for
classes of second order equations.},
}
@article{BoSc09,
author = {Bostan, Alin and Schost, {\'E}ric},
title = {A simple and fast algorithm for computing exponentials of
power series},
journal = {Information Processing Letters},
number = {13},
year = {2009},
volume = {109},
pages = {754--756},
doi = {10.1016/j.ipl.2009.03.012},
abstract = {As was initially shown by Brent, exponentials of truncated
power series can be computed using a constant number of polynomial
multiplications. This note gives a relatively simple algorithm with a low
constant factor.},
}
@article{BBGHJMZ09,
author = {A. Bostan and S. Boukraa and A. J. Guttmann and S. Hassani
and I. Jensen and J.-M. Maillard and N. Zenine},
title = {High order {F}uchsian equations for the square lattice
{I}sing model: $\tilde{\chi}^{(5)}$},
journal = {J. Phys. A: Math. Theor.},
number = {27},
year = {2009},
volume = {42},
pages = {32pp},
doi = {10.1088/1751-8113/42/27/275209},
abstract = {We consider the Fuchsian linear differential equation
obtained (modulo a prime) for $\tilde{\chi}^{(5)}$, the five-particle
contribution to the susceptibility of the square lattice Ising model. We show
that one can understand the factorization of the corresponding linear
differential operator from calculations using just a single prime. A
particular linear combination of $\tilde{\chi}^{(1)}$ and
$\tilde{\chi}^{(3)}$ can be removed from $\tilde{\chi}^{(5)}$ and the
resulting series is annihilated by a high order globally nilpotent linear
ODE. The corresponding (minimal order) linear differential operator, of order
29, splits into factors of small orders. A fifth order linear differential
operator occurs as the left-most factor of the ``depleted" differential
operator and it is shown to be equivalent to the symmetric fourth power of
$L_E$, the linear differential operator corresponding to the elliptic
integral $E$. This result generalizes what we have found for the lower order
terms $\tilde{\chi}^{(3)}$ and $\tilde{\chi}^{(4)}$. We conjecture that a
linear differential operator equivalent to a symmetric $(n-1)$-th power of
$L_E$ occurs as a left-most factor in the minimal order linear differential
operators for all $\tilde{\chi}^{(n)}$'s.},
}
@article{BBHMWZ09,
author = {A. Bostan and S. Boukraa and S. Hassani and J. -M. Maillard
and J. -A. Weil and N. Zenine},
title = {Globally nilpotent differential operators and the square
{I}sing model},
journal = {J. Phys. A: Math. Theor.},
number = {12},
year = {2009},
volume = {42},
pages = {50pp},
doi = {10.1088/1751-8113/42/12/125206},
abstract = {We recall various multiple integrals related to the
isotropic square Ising model, and corresponding, respectively, to the
n-particle contributions of the magnetic susceptibility, to the (lattice)
form factors, to the two-point correlation functions and to their
lambda-extensions. These integrals are holonomic and even G-functions: they
satisfy Fuchsian linear differential equations with polynomial coefficients
and have some arithmetic properties. We recall the explicit forms, found in
previous work, of these Fuchsian equations. These differential operators are
very selected Fuchsian linear differential operators, and their remarkable
properties have a deep geometrical origin: they are all globally nilpotent,
or, sometimes, even have zero p-curvature. Focusing on the factorised parts
of all these operators, we find out that the global nilpotence of the factors
corresponds to a set of selected structures of algebraic geometry: elliptic
curves, modular curves, and even a remarkable weight-1 modular form emerging
in the three-particle contribution $\chi^{(3)}$ of the magnetic
susceptibility of the square Ising model. In the case where we do not have
G-functions, but Hamburger functions (one irregular singularity at 0 or
$\infty$) that correspond to the confluence of singularities in the scaling
limit, the p-curvature is also found to verify new structures associated with
simple deformations of the nilpotent property.},
}
@misc{BoChChLi09,
author = {Bostan, Alin and Chyzak, Frédéric and Chen, Shaoshi
and Li, Ziming},
title = {Rational-functions telescopers: Blending creative
telescoping with Hermite reduction},
year = {2009},
howpublished= {Poster at the conference ISSAC'09 (Seoul, South Korea)},
url = {http://issac2009.kias.re.kr/program_page.html#posters},
}
@misc{ChLi90,
author = {Chen, Shaoshi and Li, Ziming},
title = {A speed-up of the Hermite reduction for rational
functions},
year = {2009},
howpublished= {Poster at the conference ICMM'09 (Beijing, China)},
url = {http://mmrc.iss.ac.cn/wu90/},
}
@inproceedings{ChFlGoLe09,
author = {Cheung, Y. K. and Flajolet, P. and Golin, M. and Lee, C. Y.
J.},
title = {Multidimensional Divide-and-Conquer and Weighted Digital
Sums (Extended Abstract)},
booktitle = {Proceedings of the Fifth Workshop on Analytic Algorithmics
and Combinatorics (ANALCO)},
year = {2009},
publisher = {SIAM Press},
pages = {58--65},
}
@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.},
}
@book{FlSe09,
author = {Flajolet, Philippe and Sedgewick, Robert},
title = {Analytic combinatorics},
year = {2009},
publisher = {Cambridge University Press},
address = {Cambridge},
pages = {xiv+810},
}
@mastersthesis{Pech2009,
author = {Pech, Lucien},
title = {Algorithmes pour la sommation et l'intégration
symboliques},
year = {2009},
month = {novembre},
school = {École Normale Supérieure},
note = {22 pages},
url = {http://algo.inria.fr/papers/pdf/Pech-2009-ASI.pdf},
}
@inproceedings{VaClFiFl09,
author = {Vallée, Brigitte and Clément, Julien and Fill,
James Allen and Flajolet, Philippe},
title = {The Number of Symbol Comparisons in QuickSort and
QuickSelect},
booktitle = {Proceedings of the 36th International Colloquium on
Automata, Languages and Programming: Part I},
year = {2009},
publisher = {Springer-Verlag},
series = {ICALP '09},
address = {Berlin, Heidelberg},
pages = {750–763},
doi = {http://dx.doi.org/10.1007/978-3-642-02927-1_62},
url = {http://dx.doi.org/10.1007/978-3-642-02927-1_62},
}
@mastersthesis{Benoit09,
author = {Benoit, Alexandre},
title = {Développements de fonctions D-finies sur des
polynômes de Tchebychev},
year = {2008},
school = {Université Paris VI-MPRI},
url = {http://algo.inria.fr/papers/pdf/Benoit2008.pdf},
}
@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$.},
}
@inproceedings{BoChLR08,
author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Le Roux,
Nicolas},
title = {Products of Ordinary Differential Operators by Evaluation
and Interpolation},
booktitle = {ISSAC'08 (July 20--23, 2008, Hagenberg, Austria)},
year = {2008},
publisher = {ACM},
pages = {23--30},
note = {Conference proceedings},
arxiv = {abs/0804.2181},
abstract = {It is known that multiplication of linear differential
operators over ground fields of characteristic zero can be reduced to a
constant number of matrix products. We give a new algorithm by evaluation and
interpolation that is faster than the previously-known one by a constant
factor, and prove that in characteristic zero, multiplication of differential
operators and of matrices are computationally equivalent problems. In
positive characteristic, we show that differential operators can be
multiplied in nearly optimal time. This equivalence fails in positive
characteristic and we give an algorithm that multiplies differential
operators in nearly linear time when the characteristic is small. Theoretical
results are validated by intensive experiments.},
}
@article{BoJeSc08,
author = {Bostan, Alin and Jeannerod, Claude-Pierre and Schost,
Éric},
title = {Solving structured linear systems with large displacement
rank},
journal = {Theoretical Computer Science},
number = {1-3},
year = {2008},
publisher = {Elsevier Science Publishers Ltd.},
volume = {407},
address = {Essex, UK},
pages = {155–181},
doi = {http://dx.doi.org/10.1016/j.tcs.2008.05.014},
abstract = {Linear systems with structures such as Toeplitz-,
Vandermon de- or Cauchy-likeness can be solved in tilde O (α2 n)
operations, wher e n is the matrix size, α is its displacement rank,
and tilde O ( ) denotes the omission of logarithmic factors. We show that
for such matrices, th is cost can be reduced to tilde O (αω-1
n), where ω is a feasible exponent for matrix multiplication over the
base field. The best known estimate for ω is ω < 2.38,
resulting in costs of order tilde O (α1.38 n). We present
consequences for Hermite-Padé approximation an d bivariate
interpolation.},
}
@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.},
}
@article{BrDe2008a,
author = {Broutin, N. and Devroye, L.},
title = {{An analysis of the height of tries with random weights on
the edges}},
journal = {Combinatorics, Probability and Computing},
year = {2008},
volume = {17},
pages = {161--202},
keywords = {trie, height},
doi = {10.1017/S0963548307008796},
}
@inproceedings{BrFl2008,
author = {Broutin, N. and Flajolet, P.},
title = {The height of random binary unlabelled trees},
booktitle = {Fifth Colloquium on Mathematics and Computer Science},
year = {2008},
volume = {AI},
series = {DMTCS Proceedings},
pages = {121–134},
keywords = {height},
url = {http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAI0106},
}
@article{BrDeMc2008,
author = {Broutin, N. and Devroye, L. and McLeish, E.},
title = {Weighted height of random trees},
journal = {Acta Informatica},
year = {2008},
volume = {45},
pages = {237--277},
keywords = {random tree, height, large deviation},
doi = {10.1007/s00236-008-0069-0},
}
@article{BrDeMcSa2008,
author = {Broutin, N. and Devroye, L. and McLeish, E. and de la
Salle, M.},
title = {The height of increasing trees},
journal = {Random Structures and Algorithms},
year = {2008},
volume = {32},
pages = {494--518},
keywords = {increasing trees, height},
doi = {10.1002/rsa.20202},
}
@article{ChDrKlKo07,
author = {Chyzak, Fr{\'e}d{\'e}ric and Drmota, Michael and Klausner,
Thomas and Kok, Gerard},
title = {The distribution of patterns in random trees},
journal = {Combinatorics, Probability \& Computing},
year = {2008},
volume = {17},
pages = {21--59},
doi = {10.1017/S0963548307008425},
arxiv = {abs/cs/0605019},
web-comment = {The 2004 version of this paper was incomplete and removed
from this list.},
abstract = {Let~$T_n$ denote the set of unrooted labeled trees of
size~$n$ and let~$M$ be a particular (finite, unlabeled) tree. Assuming that
every tree of~$T_n$ is equally likely, it is shown that the limiting
distribution as $n$~goes to infinity of the number of occurrences of~$M$ as
an induced subtree is asymptotically normal with mean value and variance
asymptotically equivalent to $\mu n$ and~$\sigma^2n$, respectively, where the
constants $\mu>0$ and~$\sigma\ge 0$ are computable.},
}
@techreport{Dumas08,
author = {Dumas, Philippe},
title = {Mean asymptotic behaviour of radix-rational sequences and
dilation equations (Extended version)},
year = {2008},
institution = {arXiv},
arxiv = {0807.1523},
url = {http://arxiv.org/abs/0807.1523},
abstract = {The generating series of a radix-rational sequence is a
rational formal power series from formal language theory viewed through a
fixed radix numeration system. For each radix-rational sequence with complex
values we provide an asymptotic expansion for the sequence of its Cesàro
means. The precision of the asymptotic expansion depends on the joint
spectral radius of the linear representation of the sequence; the
coefficients are obtained through some dilation equations. The proofs are
based on elementary linear algebra.},
}
@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.},
}
@incollection{FlHu08,
author = {Flajolet, Philippe and Huillet, Thierry},
title = {Analytic combinatorics of the {M}abinogion urn},
booktitle = {Fifth {C}olloquium on {M}athematics and {C}omputer
{S}cience},
year = {2008},
publisher = {Assoc. Discrete Math. Theor. Comput. Sci., Nancy},
series = {Discrete Math. Theor. Comput. Sci. Proc., AI},
pages = {549--571},
}
@article{FlVe07,
author = {Flajolet, Philippe and Vepstas, Linas},
title = {On Differences of Zeta Values},
journal = {Journal of Computational and Applied Mathematics},
number = {1--2},
year = {2008},
month = {October},
volume = {220},
pages = {58--73},
keywords = {zeta function, finite differences, CV},
arxiv = {abs/math/0611332},
}
@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},
}
@article{Meunier08,
author = {Meunier, Fr\'ed\'eric},
title = {A combinatorial proof of a theorem of {F}reund},
journal = {Journal of Combinatorial Theory, Series A},
number = {2},
year = {2008},
volume = {115},
pages = {317--325},
}
@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.},
}
@article{BoFuKaVi07b,
author = {Bodirsky, Manuel and Fusy, \'Eric and Kang, Mihyun and
Vigerske, Stefan},
title = {Enumeration and Asymptotic Properties of Unlabeled
Outerplanar Graphs},
journal = {Electronic Journal of Combinatorics},
number = {R66},
year = {2007},
month = {September},
volume = {14},
note = {24 pages},
}
@inproceedings{BoFuKaVi07,
author = {Bodirsky, Manuel and Fusy, {\'E}ric and Kang, Mihyun and
Vigerske, Stefan},
title = {An unbiased pointing operator for unlabeled structures,
with applications to counting and sampling},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2007},
pages = {356--365},
}
@article{BoClReRoMa07,
author = {Boeva, Valentina and Clément, Julien and Régnier,
Mireille and Roytberg, Mikhail and Makeev, Vsevolod},
title = {Exact p-value calculation for heterotypic clusters of
regulatory motifs and its application in computational annotation of
cis-regulatory modules},
journal = {Algorithms for molecular biology},
number = {13},
year = {2007},
volume = {2},
pages = {25 pages},
url = {http://www.almob.org/content/2/1/13},
}
@article{BoGaSc07,
author = {A. Bostan and P. Gaudry and \'E. Schost},
title = {Linear recurrences with polynomial coefficients and
application to integer factorization and {C}artier-{M}anin operator},
journal = {SIAM Journal on Computing},
number = {6},
year = {2007},
volume = {36},
pages = {1777--1806},
abstract = {We study the complexity of computing one or several terms
(not necessarily consecutive) in a recurrence with polynomial coefficients.
As applications, we improve the best currently known upper bounds for
factoring integers deterministically, and for computing the Cartier-Manin
operator of hyperelliptic curves.},
}
@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.},
}
@inproceedings{BoJeSc07,
author = {Bostan, Alin and Jeannerod, Claude-Pierre and Schost,
Éric},
title = {Solving Toeplitz- and Vandermonde-like Linear Systems
with Large Displacement Rank},
booktitle = {ISSAC'07: Proceedings of the 2007 international symposium
on Symbolic and algebraic computation},
year = {2007},
editor = {Brown, C. W.},
publisher = {ACM Press},
pages = {33–40},
doi = {10.1145/1277548.1277554},
abstract = {Linear systems with structures such as Toeplitz-,
Vandermonde- or Cauchy-likeness can be solved in tilde O (α2 n)
operations, where n is the matrix size, α is its displacement rank,
and tilde O ( ) denotes the omission of logarithmic factors. We show that
for Toeplitz-like and Vandermonde-like matrices, this cost can be reduced to
tilde O (αω-1 n), where ω is a feasible exponent for
matrix multiplication over the base field. The best known estimate for
ω is ω < 2.38, resulting in costs of order tilde O
(α1.38 n). We also present consequences for Hermite-Padé
approximation and bivariate interpolation.},
}
@inproceedings{BrDe2007,
author = {Broutin, N. and Devroye, L.},
title = {The height of list tries and TST},
booktitle = {International Conference on Analysis of Algorithms},
year = {2007},
publisher = {Discrete Mathematics and Theoretical Computer Science},
volume = {AH},
series = {DMTCS Proceedings},
pages = {271–282},
keywords = {trie, TST, profile, height},
url = {http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAH0118},
}
@inproceedings{ChQuRo07,
author = {Chyzak, Fr\'ed\'eric and Quadrat, Alban and Robertz,
Daniel},
title = {{OreModules}: A symbolic package for the study of
multidimensional linear systems},
booktitle = {Applications of Time Delay Systems},
year = {2007},
editor = {Chiasson, J. and Loiseau, J. J.},
publisher = {Springer Berlin / Heidelberg},
volume = {352},
series = {Lecture Notes in Control and Information Sciences},
pages = {233--264},
note = {ISBN 978-3-540-49555-0},
doi = {10.1007/978-3-540-49556-7_15},
abstract = {In the seventies, the study of transfer matrices of
time-invariant linear systems of ordinary differential equations (ODEs) led
to the development of the polynomial approach. In particular, the univariate
polynomial matrices play a central role in this approach (e.g., Hermite,
Smith and Popov forms, invariant factors, primeness, B\'ezout/Diophantine
equations).},
}
@article{DuLiWa07,
author = {Dumas, Philippe and Lipmaa, Helger and Wallén, Johan},
title = {Asymptotic behaviour of a non-commutative rational series
with a nonnegative linear representation},
journal = {Discrete Mathematics & Theoretical Computer Science},
number = {1},
year = {2007},
volume = {9},
pages = {247–274},
url = {http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/478/1836},
}
@inproceedings{Flajolet07,
author = {Flajolet, Philippe},
title = {Analytic Combinatorics---A Calculus of Discrete
Structures},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2007},
publisher = {SIAM Press},
pages = {137--148},
}
@inproceedings{FlFuGaMe07,
author = {Flajolet, Philippe and Fusy, {\'Eric} and Gandouet, Olivier
and Meunier, {Fr\'ed\'eric}},
title = {HyperLoglog: the analysis of a near-optimal cardinality
estimation algorithm},
booktitle = {Analysis of Algorithms 2007 (AofA07)},
year = {2007},
editor = {Jacquet, Philippe},
series = {Discrete Mathematics and Theoretical Computer Science
Proceedings},
pages = {127--146},
keywords = {probabilistic counting, Mellin transform, depoissonization,
CV},
}
@inproceedings{FlFuPi07,
author = {Flajolet, Philippe and Fusy, {\'E}ric and Pivoteau,
Carine},
title = {Boltzmann Sampling of Unlabelled Structures},
booktitle = {Proceedings of the Ninth Workshop on Algorithm Engineering
and Experiments and the Fourth Workshop on Analytic Algorithmics and
Combinatorics},
year = {2007},
editor = {Appelgate, David},
publisher = {SIAM Press},
pages = {201--211},
keywords = {Boltzmann model, CV, analytic combinatorics},
note = {Proceedings of the New Orleans Conference},
}
@phdthesis{Fu07th,
author = {Fusy, É.},
title = {Combinatoire des cartes planaires et applications
algorithmiques},
year = {2007},
month = {June},
school = {École Polytechnique},
url = {http://algo.inria.fr/papers/pdf/these_eric_fusy.pdf},
}
@inproceedings{Fusy07,
author = {Fusy, {\'E}ric},
title = {Straight-line drawing of quadrangulations},
booktitle = {Graph Drawing 2006},
year = {2007},
publisher = {Springer-Verlag},
volume = {4372},
series = {Lecture Notes in Computer Science},
pages = {234--239},
note = {Karlsruhe, Germany, September 18--20, 2006},
}
@inproceedings{FuGi07,
author = {Fusy, \'Eric and Giroire, Fr\'ed\'eric},
title = {Estimating the number of active flows in a data stream over
a sliding window},
booktitle = {Proceedings of the Ninth Workshop on Algorithm Engineering
and Experiments and the Fourth Workshop on Analytic Algorithmics and
Combinatorics},
year = {2007},
editor = {Appelgate, David},
publisher = {SIAM Press},
pages = {223--231},
note = {Proceedings of the New Orleans Conference},
}
@article{FuPoSc07,
author = {Fusy, Eric and Poulalhon, Dominique and Schaeffer,
Gilles},
title = {Bijective counting of plane bipolar orientations},
journal = {Electronic Notes in Discrete Mathematics},
year = {2007},
volume = {29},
pages = {283–287},
keywords = {bijection; bipolar orientations; non-intersecting paths},
url = {http://www.sciencedirect.com/science/article/B75GV-4PCHPN5-1R/2/84e28461fe6672d2c0b27589b5b04f9e},
abstract = {We introduce a bijection between plane bipolar orientations
with fixed numbers of vertices and faces, and non-intersecting triples of
upright lattice paths with some specific extremities. Writing [theta]ij for
the number of plane bipolar orientations with (i+1) vertices and (j+1) faces,
our bijection provides a combinatorial proof of the following formula due to
Baxter:},
}
@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.},
}
@incollection{MeSe07,
author = {Meunier, Fr\'ed\'eric and Seb{\"o}, Andras},
title = {Parcours et coupes},
booktitle = {Graphes et applications, tome 2},
year = {2007},
publisher = {Herm\`es Science Publications},
pages = {1--31},
}
@mastersthesis{Mezzarobba2007,
author = {Mezzarobba, Marc},
title = {Génération automatique de procédures numériques
pour les fonctions D-finies},
year = {2007},
month = {octobre},
school = {Master parisien de recherche en informatique},
note = {version 1.2, 89 pages},
url = {http://algo.inria.fr/papers/pdf/Mezzarobba_MScThesisMPRI2007-1.2.pdf},
}
@inproceedings{AdBrRe2006,
author = {Addario-Berry, L. and Broutin, N. and Reed, B.},
title = {The diameter of the minimum spanning tree of the complete
graph},
booktitle = {Fourth Colloquium on Mathematics and Computer Science
Algorithms, Trees Combinatorics and Probability},
year = {2006},
publisher = {Discrete Mathematics and Theoretical Computer Science},
volume = {AG},
series = {DMTCS Proceedings},
pages = {237–240},
keywords = {random tree, random walk, diameter, MST},
url = {http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAG0116},
}
@inproceedings{AmBeGiHuPe06,
author = {O. Amini and J.-C. Bermond and F. Giroire and F. Huc and S.
P{\'e}rennes},
title = {Design of Minimal Fault Tolerant Networks: Asymptotic
Bounds},
booktitle = {Huiti\`emes Rencontres Francophones sur les Aspects
Algorithmiques des T\'el\'ecommunications (AlgoTel'06)},
year = {2006},
month = {May},
address = {Tr\'egastel, France},
pages = {37--40},
}
@misc{Besson06,
author = {Besson, Bruno},
title = {Matrices poids-position : principes et algorithmes},
year = {2006},
note = {Mémoire de Master 2, Université Paris XI},
url = {http://algo.inria.fr/papers/pdf/Besson06.pdf},
}
@inproceedings{BoFuPi06,
author = {Olivier Bodini and {\'E}ric Fusy and Carine Pivoteau},
title = {Random sampling of plane partitions},
booktitle = {Gascom 2006},
year = {2006},
editor = {Renzo Pinzani and Vincent Vajnovszki},
publisher = {LE2I},
address = {Dijon, France},
pages = {124--135},
}
@article{BoMaPaRe06,
author = {V. Boeva and V. Makeev and D. Papatsenko and M.
R{\'e}gnier},
title = {Short fuzzy tandem repeats in genomic sequences,
identification, and possible role in regulation of gene expression},
journal = {Bioinformatics},
number = {6},
year = {2006},
volume = {22},
pages = {676--684},
}
@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.},
}
@article{BrDe2006,
author = {Broutin, N. and Devroye, L.},
title = {{Large deviations for the weighted height of an extended
class of trees}},
journal = {Algorithmica},
year = {2006},
volume = {46},
pages = {271--297},
keywords = {weighted tree, large deviation, branching random walk},
doi = {10.1007/s00453-006-0112-x},
}
@article{CoFl06,
author = {Conrad, Eric van Fossen and Flajolet, Philippe},
title = {The {Fermat} cubic, elliptic functions, continued
fractions, and a combinatorial excursion},
journal = {S\'eminaire Lotharingien de Combinatoire},
number = {B54g},
year = {2006},
volume = {54},
pages = {1--44},
}
@phdthesis{Fayolle06,
author = {Julien Fayolle},
title = {Compression de données sans perte et combinatoire
analytique},
year = {2006},
school = {École doctorale en informatique, télécommunication et
électronique de l'Université Pierre et Marie Curie},
url = {http://algo.inria.fr/papers/pdf/Fayolle06.pdf},
}
@inproceedings{Flajolet06,
author = {Flajolet, Philippe},
title = {The Ubiquitous Digital Tree},
booktitle = {{STACS~2006}},
year = {2006},
editor = {Durand, Bruno and Thomas, Wolfgang},
volume = {3884},
series = {Lecture Notes in Computer Science},
pages = {1--22},
note = {Proceedings of 23rd Annual Symposium on Theoretical Aspects
of Computer Science, Marseille, February 2006.},
}
@article{FlDuPu06,
author = {Flajolet, Philippe and Dumas, Philippe and Puyhaubert,
Vincent},
title = {Some exactly solvable models of urn process theory},
journal = {Discrete Mathematics \& Theoretical Computer Science
(Proceedings)},
year = {2006},
volume = {AG},
pages = {59--118},
}
@article{FlFuGoPaPo06,
author = {Flajolet, Philippe and Fusy, Éric and Gourdon, Xavier
and Panario, Daniel and Pouyanne, Nicolas},
title = {A Hybrid of Darboux's Method and Singularity Analysis in
Combinatorial Asymptotics},
journal = {The Electronic Journal of Combinatorics},
number = {1},
year = {2006},
month = {June},
volume = {13},
pages = {R103},
note = {35 pages},
arxiv = {abs/math/0606370},
url = {http://www.combinatorics.org/Volume_13/PDF/v13i1r103.pdf},
}
@article{FlNePr06,
author = {Flajolet, Philippe and Nebel, Markus and Prodinger,
Helmut},
title = {The scientific works of {Rainer Kemp} (1949--2004)},
journal = {Theoretical Computer Science},
number = {3},
year = {2006},
month = {April},
volume = {355},
pages = {371--381},
}
@article{FlSzVa06,
author = {Flajolet, Philippe and Szpankowski, Wojciech and Vall\'ee,
Brigitte},
title = {Hidden Word Statistics},
journal = {Journal of the ACM},
number = {1},
year = {2006},
month = {January},
volume = {53},
pages = {147--183},
}
@article{Fusy06b,
author = {Éric Fusy},
title = {Counting d-polytopes with (d+3) vertices},
journal = {Electronic Journal of Combinatorics},
number = {1},
year = {2006},
volume = {13},
url = {http://www.combinatorics.org/Volume_13/PDF/v13i1r23.pdf},
}
@inproceedings{Fusy05,
author = {{\'E}ric Fusy},
title = {Transversal structures on triangulations, with application
to straight-line drawing},
booktitle = {Graph Drawing 2005},
year = {2006},
editor = {Healy, Patrick and Nikolov, Nikola S.},
publisher = {Springer},
volume = {3843},
series = {Lecture Notes in Computer Science},
pages = {177--188},
note = {Limerick, Ireland, September 12--14, 2005},
}
@inproceedings{Giroire06,
author = {F. Giroire},
title = {Directions to use Probabilistic Algorithms for Cardinality
for {DNA} Analysis},
booktitle = {Journ\'ees Ouvertes Biologie Informatique Math\'ematiques
(JOBIM 2006)},
year = {2006},
month = {July},
pages = {3--5},
}
@phdthesis{Giroire06b,
author = {Giroire, Frédéric},
title = {Réseaux, algorithmique et analyse combinatoire de
grands ensembles},
year = {2006},
month = {November},
school = {Université Paris VI},
url = {http://algo.inria.fr/papers/pdf/Giroire06b.pdf},
}
@article{ReVa06,
author = {M. Régnier and M. Vandenbogaert},
title = {Comparison of Statistical Significance Criteria},
journal = {Journal of Bioinformatics and Computational Biology},
number = {2},
year = {2006},
volume = {4},
pages = {537–551},
url = {http://algo.inria.fr/regnier/publis/ReVa05.ps},
}
@article{AbLe05,
author = {S. A. Abramov and H. Q. Le},
title = {{On the order of the recurrence produced by the method of
creative telescoping}},
journal = {Discrete Mathematics},
number = {1--3},
year = {2005},
month = {August},
volume = {298},
pages = {2--17},
}
@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{BoClReVa05,
author = {V. Boeva and J. Clément and M. Régnier and M.
Vandenbogaert},
title = {Assessing the significance of Sets of Words},
booktitle = {Combinatorial Pattern Matching 05},
year = {2005},
publisher = {Springer Verlag},
volume = {3537},
series = {Lecture Notes in Computer Science},
pages = {358–370},
note = {In Proceedings CPM'05, Jeju Island, Korea},
url = {http://algo.inria.fr/regnier/publis/BoClReVa05.ps},
}
@article{BoSc05,
author = {A. Bostan and {\'E}. Schost},
title = {Polynomial evaluation and interpolation on special sets of
points},
journal = {Journal of Complexity},
number = {4},
year = {2005},
month = {August},
volume = {21},
pages = {420--446},
note = {Festschrift for the 70th Birthday of Arnold
Sch{\"o}nhage},
doi = {10.1016/j.jco.2004.09.009},
abstract = {We give complexity estimates for the problems of evaluation
and interpolation on various polynomial bases. We focus on the particular
cases when the sample points form an arithmetic or a geometric sequence, and
we discuss applications, respectively, to computations with linear
differential operators and to polynomial matrix multiplication.},
}
@inproceedings{BoGoPeSc05,
author = {Bostan, A. and Gonz{\'a}lez-Vega, L. and Perdry, H. and
Schost, {\'E}.},
title = {From {N}ewton sums to coefficients: complexity issues in
characteristic $p$},
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 consider the following problem: given the first $d$
Newton sums of a degree $d$ polynomial $P$, recover the coefficients of $P$.
We propose fast algorithms to perform this conversion for polynomials over
the $p$-adic ring $\Z_p$. As an application, we deduce a new algorithm to
compute the \emph{composed product} of polynomials over the finite field
$\F_p$, whose bit-complexity improves the known results by a factor of
$\,\log d$ in many cases.},
}
@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.},
}
@proceedings{Chyzak05,
title = {Algorithms Seminar, 2002--2004},
year = {2005},
month = {April},
editor = {Chyzak, Fr{\'e}d{\'e}ric},
volume = {5542},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
note = {120 pages},
abstract = {These seminar notes constitute the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, and the asymptotic
analysis of algorithms, data structures, and network protocols.},
}
@incollection{ChPa05,
author = {Chyzak, Frédéric and Paule, Peter},
title = {Computer algebra},
booktitle = {Digital Library of Mathematical Functions},
year = {2005},
editor = {Lozier, Dan and Olver, Frank and Clark, Charles and
Boisvert, Ron},
publisher = {NIST},
note = {40 pages. Under the process of validation by NIST},
web-comment = {This ambitious project, DLMF, is managed by NIST and aims at
providing a new edition for the Handbook of Mathematical Functions,
an
authoritative handbook since 1962.},
abstract = {This chapter focuses on computer algebra techniques which
are tailored primarily for special function applications, that is, for
symbolic manipulation of expressions representing special functions and
sequences. The described methods are algorithms rather than formulas or
identities.},
}
Handbook of Mathematical Functions,an authoritative handbook since 1962.
@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{ChQuRo05,
author = {Chyzak, Frédéric and Quadrat, Alban and Robertz,
Daniel},
title = {Effective algorithms for parametrizing linear control
systems over Ore algebras},
journal = {Applicable Algebra in Engineering, Communication and
Computing},
number = {5},
year = {2005},
month = {November},
publisher = {Springer Verlag},
volume = {16},
pages = {319–376},
doi = {10.1007/s00200-005-0188-6},
web-comment = {Preliminary
version (INRIA Research Report #5181).},
abstract = {In this paper, we study linear control systems over Ore
algebras. Within this mathematical framework, we can simultaneously deal with
different classes of linear control systems such as time-varying ordinary
differential systems (ODEs), differential time-delay systems, partial
differential equations (PDEs), multidi mensional discrete systems,
multidimensional codes etc. We give effective algorithms which check whether
or not a linear control system over some Ore algebra is controllable,
parametrizable, flat or π-free.},
}
@inproceedings{FaWa05,
author = {Julien Fayolle and Mark Daniel Ward},
title = {Analysis of the Average Depth in a Suffix Tree under a
Markov Model},
booktitle = {2005 International Conference on Analysis of Algorithms},
year = {2005},
editor = {Conrado Martínez},
publisher = {Discrete Mathematics and Theoretical Computer Science},
volume = {AD},
series = {DMTCS Proceedings},
pages = {95–104},
url = {http://www.dmtcs.org/proceedings/html/dmAD0109.abs.html},
}
@article{FiFlKa05,
author = {James A. Fill and Philippe Flajolet and Nevin Kapur},
title = {Singularity Analysis, {H}adamard Products, and Tree
Recurrences},
journal = {Journal of Computational and Applied Mathematics},
year = {2005},
month = {February},
volume = {174},
pages = {271--313},
}
@article{FlGaPe05,
author = {Flajolet, Philippe and {Gabarr\'o}, Joaquim and Pekari,
Helmut},
title = {Analytic Urns},
journal = {Annals of Probability},
number = {3},
year = {2005},
volume = {33},
pages = {1200--1233},
arxiv = {abs/math/0407098},
}
@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.},
}
@inproceedings{FusyAofa05,
author = {Éric Fusy},
title = {Quadratic exact size and linear approximate size random
generation of planar graphs},
booktitle = {2005 International Conference on Analysis of Algorithms},
year = {2005},
editor = {Conrado Martínez},
publisher = {Discrete Mathematics and Theoretical Computer Science},
volume = {AD},
series = {DMTCS Proceedings},
pages = {125-138},
url = {http://www.dmtcs.org/proceedings/abstracts/dmAD0112.abs.html},
}
@inproceedings{FusyPS05,
author = {{\'E}ric Fusy and Dominique Poulalhon and Gilles
Schaeffer},
title = {Dissections and trees, with applications to optimal mesh
encoding and to random sampling},
booktitle = {SODA},
year = {2005},
pages = {690--699},
note = {Proceedings of the Sixteenth Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January
23-25, 2005},
}
@inproceedings{Giroire05,
author = {Frédéric Giroire},
title = {Order statistics and estimating cardinalities of massive
data sets},
booktitle = {2005 International Conference on Analysis of Algorithms},
year = {2005},
editor = {Conrado Martínez},
publisher = {Discrete Mathematics and Theoretical Computer Science},
volume = {AD},
series = {DMTCS Proceedings},
pages = {157-166},
url = {http://www.dmtcs.org/proceedings/html/dmAD0115.abs.html},
}
@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.},
}
@inbook{HuFl05,
author = {Huet, {G\'erard} and Flajolet, Philippe},
title = {Les math\'ematiques dans le monde scientifique
contemporain},
chapter = {Math\'ematiques et Informatique},
year = {2005},
publisher = {Acad\'emie des sciences},
volume = {20},
series = {Rapport sur la science et la technologie},
address = {Paris},
pages = {215--237},
note = {Edited by Jean-Cristophe Yoccoz},
}
@misc{Pivoteau05,
author = {Pivoteau, Carine},
title = {G\'en\'eration al\'eatoire et mod\`eles de {B}oltzmann},
year = {2005},
note = {M\'emoire de DEA, Universit\'e Paris VI},
}
@phdthesis{Puyhaubert05,
author = {Puyhaubert, Vincent},
title = {Modèles d'urnes et phénomènes de seuils en
combinatoire analytique},
year = {2005},
school = {École polytechnique},
url = {http://algo.inria.fr/papers/pdf/Puyhaubert2005.pdf},
}
@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},
}
@article{TaEnRe05,
author = {Fariza Tahi and Stefan Engelen and Mireille R{\'e}gnier},
title = {P-dcfold or How to Predict all Kinds of Pseudoknots in
{RNA} Secondary Structures},
journal = {International Journal on Artificial Intelligence Tools},
number = {14},
year = {2005},
volume = {5},
pages = {703--716},
}
@article{Tompa05,
author = {M. Tompa and N. Li and T.L. Bailey and G.M. Church and
De Moor, B. and E. Eskin and A.V. Favorov and M.C. Frith and Y. Fu and J.W.
Kent and V.J. Makeev and A.A. Mironov and W.S. Noble and G. Pavesi and G.
Pesole and M. Régnier and N. Simonis and S. Sinha and G. Thijs and J. van
Helden and M. Vandenbogaert and Z. Weng and C. Workman and C. Ye and Z.
Zhu},
title = {An Assessment of Computational Tools for the Discovery of
Transcription Factor Binding Sites.},
journal = {Nature Biotechnology},
number = {1},
year = {2005},
month = {January},
volume = {23},
pages = {137 – 144},
url = {http://www.nature.com/cgi-taf/DynaPage.taf?file=/nbt/journal/v23/n1/abs/nbt1053.html},
}
@misc{Vera05,
author = {Vera, Antonio},
title = {Analyse dynamique d'algorithmes Euclidiens en dimension
2},
year = {2005},
note = {M\'emoire de DEA, Universit\'e Paris VI},
}
@inproceedings{AbLe04,
author = {S. A. Abramov and H. Q. Le},
title = {{Utilizing relationships among linear systems generated by
{Z}eilberger's algorithm}},
booktitle = {Formal Power Series and Algebraic Combinatorics},
year = {2004},
pages = {29--38},
note = {Proceedings of FPSAC'04, Vancouver, June 2004},
}
@article{AbCaGeLe04,
author = {S. A. Abramov and J. J. Carette and K. O. Geddes and H. Q.
Le},
title = {Telescoping in the Context of Symbolic Summation in
{M}aple},
journal = {Journal of Symbolic Computation},
number = {4},
year = {2004},
month = {October},
volume = {38},
pages = {1303--1326},
}
@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{BoMaRe04,
author = {V. Boeva and V. Makeev and M. R{\'e}gnier},
title = {{SWAN:} searching for highly divergent tandem repeats in
{DNA} sequences and statistical significance},
booktitle = {JOBIM'04},
year = {2004},
publisher = {IEEE Computer Society},
note = {In Proceedings JOBIM'04, Montr{\'e}al},
}
@article{BoSc04b,
author = {A. Bostan and {\'E}. Schost},
title = {On the complexities of multipoint evaluation and
interpolation},
journal = {Theoretical Computer Science},
number = {1--3},
year = {2004},
month = {December},
volume = {329},
pages = {223--235},
doi = {10.1016/j.jco.2004.09.009},
abstract = {We give complexity estimates for the problems of evaluation
and interpolation on various polynomial bases. We focus on the particular
cases when the sample points form an arithmetic or a geometric sequence, and
we discuss applications, respectively, to computations with linear
differential operators and to polynomial matrix multiplication.},
}
@inproceedings{BoGaSc03,
author = {A. Bostan and P. Gaudry and {\'E}. Schost},
title = {Linear recurrences with polynomial coefficients and
computation of the {C}artier-{M}anin operator on hyperelliptic curves},
booktitle = {Fq7, International Conference on Finite Fields and
Applications (Toulouse, France, May 5-9, 2003)},
year = {2004},
editor = {Gary L. Mullen, Alain Poli, Henning Stichtenoth},
publisher = {Springer--Verlag},
volume = {2948},
series = {Lecture Notes in Computer Science},
pages = {40--58},
doi = {10.1007/b95905},
abstract = {We improve an algorithm originally due to Chudnovsky and
Chudnovsky for computing one selected term in a linear recurrent sequence
with polynomial coefficients. Using baby-steps / giant-steps techniques, the
$n$th term in such a sequence can be computed in time proportional to
$\sqrt{n}$, instead of $n$ for a naive approach. As an intermediate result,
we give a fast algorithm for computing the values taken by an univariate
polynomial $P$ on an arithmetic progression, taking as input the values of
$P$ on a translate on this progression. We apply these results to the
computation of the Cartier-Manin operator of a hyperelliptic curve. If the
base field has characteristic $p$, this enables us to reduce the complexity
of this computation by a factor of order $\sqrt{p}$. We treat a practical
example, where the base field is an extension of degree 3 of the prime field
with $p=2^{32}-5$ elements.},
}
@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{ChFlGaGi04,
author = {Brigitte Chauvin and Philippe Flajolet and Dani\`ele Gardy
and Bernhard Gittenberger},
title = {{And/Or Trees Revisited}},
journal = {Combinatorics, Probability and Computing},
number = {4--5},
year = {2004},
volume = {13},
pages = {501--513},
note = {Special issue on Analysis of Algorithms.},
}
@inproceedings{ChQuRo04,
author = {Frédéric Chyzak and Alban Quadrat and Daniel Robertz},
title = {OreModules, A symbolic package for the study of
multidimensional linear systems},
booktitle = {Sixteenth International Symposium on Mathematical Theory of
Networks and Systems},
year = {2004},
month = {July},
publisher = {Katholieke Universiteit Leuven},
address = {Leuven, Belgium},
note = {Proceedings MTNS2004, Katholieke Universiteit Leuven,
Belgium, July 5–9, 2004},
url = {http://www.mtns2004.be/database/papersubmission/upload/206.pdf},
web-comment = {More on the package web site.},
}
@book{DrFlGaGi04,
title = {Mathematics and Computer Science III: Algorithms, Trees,
Combinatorics and Probabilities},
year = {2004},
editor = {Drmota, M. and Flajolet, P. and Gardy, D. and Gittenberger,
B.},
publisher = {{Birkh{\"a}user Verlag}},
series = {Trends in Mathematics (Mathematics, Computer Science)},
note = {554 pages.},
}
@article{DuFlLoSc04,
author = {Philippe Duchon and Philippe Flajolet and Guy Louchard and
Gilles Schaeffer},
title = {Boltzmann Samplers for the Random Generation of
Combinatorial Structures},
journal = {Combinatorics, Probability and Computing},
number = {4--5},
year = {2004},
volume = {13},
pages = {577--625},
note = {Special issue on Analysis of Algorithms.},
}
@phdthesis{Durand04,
author = {Marianne Durand},
title = {Combinatoire analytique et algorithmique des ensembles de
données},
year = {2004},
school = {École polytechnique},
url = {http://algo.inria.fr/papers/pdf/Durand04.pdf},
}
@inproceedings{Fayolle04,
author = {Julien Fayolle},
title = {An average-case analysis of basic parameters of the suffix
tree},
booktitle = {Mathematics and Computer Science},
year = {2004},
editor = {Michael Drmota and Philippe Flajolet and Dani{\`e}le Gardy
and Bernhard Gittenberger},
publisher = {Birkh{\"a}user},
pages = {217--227},
note = {Proceedings of a colloquium organized by TU Wien, Vienna,
Austria, September 2004},
}
@inproceedings{Flajolet04,
author = {Philippe Flajolet},
title = {Counting by coin tossings},
booktitle = {{Proceedings of ASIAN'04 (Ninth Asian Computing Science
Conference)}},
year = {2004},
editor = {Maher, M.},
volume = {3321},
series = {Lecture Notes in Computer Science},
pages = {1--12},
note = {Text of Opening Keynote Address.},
}
@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.},
}
@inproceedings{GeLeLi04,
author = {Keith Geddes and Ha Le and Ziming Li},
title = {{Differential rational normal forms and a reduction
algorithm for hyperexponential functions}},
booktitle = {Symbolic and Algebraic Computation},
year = {2004},
editor = {J. Gutierrez},
publisher = {ACM Press},
pages = {183--190},
note = {Proceedings of ISSAC'04, Santander, July 2004},
}
@inproceedings{LeLi04,
author = {Ha Le and Ziming Li},
title = {{Differential rational normal forms and representations of
hyperexponential functions}},
booktitle = {Rhine Workshop on Computer Algebra},
year = {2004},
pages = {3--12},
note = {Proceedings of RWCA'04, Nijmegen, March 2004.},
}
@article{LeRe04,
author = {M. Lescot and M. Régnier},
title = {Motif statistics on plants datasets},
journal = {Biophysics},
number = {1},
year = {2004},
volume = {48},
pages = {1–6},
note = {Proc. Moscow Conference on Computational Molecular Biology,
MCCMB'03},
url = {http://algo.inria.fr/regnier/publis/LeRe03.ps},
}
@inproceedings{DuLiWa04,
author = {Lipmaa, Helger and Wall{\'e}n, Johan and Dumas, Philippe},
title = {Differential Probability of Exclusive-Or},
booktitle = {Fast Software Encryption 2004},
year = {2004},
editor = {Roy, Bimal and Meier, Willi},
publisher = {Springer-Verlag},
volume = {3017},
series = {Lecture Notes in Computer Science},
pages = {317--331},
note = {Delhi, India, February 5--7, 2004},
}
@article{Puyhaubert04,
author = {Puyhaubert, Vincent},
title = {Generating functions and the satisfiability threshold},
journal = {Discrete Mathematics and Theoretical Computer Science},
number = {2},
year = {2004},
volume = {6},
pages = {425–436},
keywords = {First moment method, exponential generating functions,
saddle-point bounds},
url = {http://www.dmtcs.org/volumes/abstracts/dm060216.abs.html},
}
@inproceedings{Regnier04,
author = {Mireille Régnier},
title = {Mathematical Tools for Regulatory Signals Extraction},
booktitle = {Bioinformatics of Genome Regulation and Structure},
year = {2004},
editor = {N. Kolchanov and R. Hofestaedt},
publisher = {Kluwer Academic Publisher},
pages = {61–70},
note = {Preliminary version at BGRS'02},
url = {http://algo.inria.fr/regnier/publis/Regnier2.doc},
}
@article{ReDe04,
author = {Mireille Régnier and Alain Denise},
title = {Rare events and Conditional Events on random strings},
journal = {DMTCS},
number = {2},
year = {2004},
volume = {6},
pages = {191–214},
url = {http://dmtcs.loria.fr/pspapers/dm060203.ps},
}
@article{ReTa04,
author = {M. Régnier and F. Tahi},
title = {Generating Functions in Computational Biology},
journal = {Journal of Iranian Statistics},
year = {2004},
note = {Preliminary version at MABS'97; to appear},
url = {http://algo.inria.fr/regnier/publis/ReTa04.ps},
}
@phdthesis{Vandenbogaert04,
author = {Mathias Vandenbogaert},
title = {Algorithmes et mesures statistiques pour la recherche de
signaux fonctionnels dans les zones de régulation},
year = {2004},
school = {INRIA & LaBRI},
url = {http://algo.inria.fr/papers/pdf/Vandenbogaert04.pdf},
}
@inproceedings{BaChLR03,
author = {Barkatou, Moulay and Chyzak, Frédéric and
Loday-Richaud, Michèle},
title = {Remarques algorithmiques liées au rang d'un
opérateur différentiel linéaire},
booktitle = {From Combinatorics to Dynamical Systems (Journées de
Calcul Formel, Strasbourg, March 22-23, 2002)},
year = {2003},
editor = {Fauvet, F. and Mitschi, C.},
publisher = {de Gruyter},
volume = {3},
series = {IRMA Lectures in Mathematics and Theoretical Physics},
pages = {87–129},
note = {In French. ISBN 3-11-017875-3},
web-comment = {Preliminary
version.},
abstract = {(French) Dans cet article nous décrivons et comparons
différentes méthodes algorithmiques pour résoudre le problème suivant
: étant donnée une série hat f(x)= sum m geq 0umxm solution
d'une équation différentielle linéaire ordinaire et un nombre
entier r>0, construire une équation différentielle vérifiée par les
sous-séries hat fj(x)= sum m geq 0uj+mrxj+mr de ses termes de
r en r. Cette question apparaî t naturellement lors de l'implantation
en calcul formel des solutions formelles et de leurs (multi-)sommes. Les
méthodes proposées sont implantées en sc Maple et nous donnons
l'adresse des programmes correspondants.En appendice nous indiquons une
démarche constructive réaliste pour le calcul effectif des invariants
formels d'une équation ou d'un système. (English) This paper aims at
introducing and comparing various methods for solving the following problem
which arises naturally in computer algebra for differential equations: given
a series hat f(x)= sum m geq 0umxm solution of an ordinary linear
differential equation and given an integer r geq 2 find a differential
equation satisfied by the sub-series hat fj(x)= sum _m geq
0uj+mrxj+mr. These methods have been implemented in sc Maple.
References are given to the corresponding programs. Possible realistic
algorithms to effectively calculate the formal invariants of an ordinary
linear differential system of order one and arbitrary rank are sketched in an
Appendix.},
}
@phdthesis{Bostan03,
author = {Bostan, Alin},
title = {Algorithmique efficace pour des opérations de base en
Calcul formel.},
year = {2003},
school = {École polytechnique},
url = {http://algo.inria.fr/bostan/these/These.pdf},
abstract = {The subject of this thesis is the design and implementation
of efficient algorithms for some basic operations in computer algebra, as
well as their applications to related fields, such as computational number
theory and cryptography. The first part of the text is dedicated to basic
algorithms on univariate polynomials. The tool which we use systematically is
a constructive version of Tellegen's transposition principle, which makes it
possible to obtain new algorithms for the problems of multipoint evaluation
and interpolation (in various polynomial bases and for various families of
evaluation points), as well as a theorem of equivalence between the
complexities of these two problems. The second part is devoted to fast
computation with algebraic numbers. We begin by studying certain elementary
operations, such as the composed sum and the composed product and their
generalization — the diamond product of Brawley and Carlitz. Their
calculation rests on the use of the formal Newton operator and the algebraic
duality, translated algorithmically by the use of transposition principle and
baby step / giant step methods. The results are then generalized to the
framework of zero-dimensional algebraic polynomial systems, for the
computation of minimal polynomials in quotient algebras and that of rational
parametrizations. In the third part, we investigate the question of the
efficient computation of a term in a linear recurrent sequence with
polynomial coefficients. As an application, we obtain theoretical and
practical improvements of a point-counting method used in hyperelliptic curve
cryptography. Then, we propose an evaluation-interpolation type method for
certain usual operations on linear differential operators with polynomial
coefficients.},
}
@inproceedings{BoLeSc03,
author = {Bostan, A. and Lecerf, G. and Schost, {\'E}.},
title = {Tellegen's Principle Into Practice},
booktitle = {Symbolic and Algebraic Computation},
year = {2003},
editor = {J. R. Sendra},
publisher = {ACM Press},
pages = {37--44},
note = {Proceedings of ISSAC'03, Philadelphia, August 2003.},
doi = {10.1145/860854.860870},
abstract = {The transposition principle, also called Tellegen's
principle, is a set of transformation rules for linear programs. Yet, though
well known, it is not used systematically, and few practical implementations
rely on it. In this article, we propose explicit transposed versions of
polynomial multiplication and division but also new faster algorithms for
multipoint evaluation, interpolation and their transposes. We report on their
implementation in Shoup's NTL C++ library.},
}
@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{BrCaDu03,
author = {Herv\'e Br{\"o}nnimann and Fr\'ed\'eric Cazals and Marianne
Durand},
title = {Randomized Jumplists: A Jump-and-Walk Dictionary
DataStructure},
booktitle = {Proceedings of the STACS'03 Conference, Berlin, February
2003},
year = {2003},
publisher = {Springer Verlag},
volume = {2607},
series = {Lecture Notes in Computer Science},
pages = {283--294},
}
@article{ChFl03,
author = {Philippe Chassaing and Philippe Flajolet},
title = {Hachage, Arbres, Chemins, et Graphes},
journal = {Gazette des Math\'ematiciens},
year = {2003},
address = {Soci\'et\'e Math\'ematique de France},
pages = {29--49},
}
@proceedings{Chyzak03,
title = {Algorithms Seminar, 2001–2002},
year = {2003},
month = {November},
editor = {Chyzak, Frédéric},
volume = {5003},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-5003.html},
abstract = {These seminar notes constitute the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, asymptotic analysis,
number theory, as well as the analysis of algorithms, data structures, and
network protocols.},
}
@inproceedings{ChQuRo03,
author = {Chyzak, Frédéric and Quadrat, Alban and Robertz,
Daniel},
title = {Linear control systems over Ore algebras: effective
algorithms for the computation of parametrizations},
booktitle = {Time-Delay Systems},
year = {2003},
note = {Electronic proceedings of an IFAC Workshop,
INRIA-Roquencourt (France)},
url = {http://algo.inria.fr/chyzak/Publications/tds03.ps},
web-comment = {Conference web
site.},
}
@article{Durand03,
author = {Marianne Durand},
title = {Asymptotic Analysis of an Optimized Quicksort Algorithm},
journal = {Information Processing Letters},
year = {2003},
volume = {85},
pages = {73--77},
}
@inproceedings{DuFl03,
author = {Marianne Durand and Philippe Flajolet},
title = {Loglog Counting of Large Cardinalities},
booktitle = {Annual European Symposium on Algorithms (ESA03)},
year = {2003},
month = {September},
editor = {Di Battista, G. and Zwick, U.},
volume = {2832},
series = {Lecture Notes in Computer Science},
pages = {605--617},
}
@article{DuTa03,
author = {Marianne Durand and Stephen Taylor},
title = {Emerging Behavior as Binary Search Trees Are Symetrically
Updated},
journal = {Theoretical Computer Science},
year = {2003},
volume = {297},
pages = {425--445},
keywords = {asymptotics, generating functions},
}
@techreport{FlSe03,
author = {Flajolet, Philippe and Sedgewick, Robert},
title = {Analytic Combinatorics: Basic Complex Asymptotics},
number = {ALCOM-FT-TR-300},
year = {2003},
month = {November},
institution = {ALCOM Project},
note = {133 pages. Chapters 4 and 5 of the book project
\emph{Analytic Combinatorics}},
}
@misc{Giroire03,
author = {Giroire, Fr\'ed\'eric},
title = {Etude de Probl\`emes Combinatoires li\'es \`a l'Analyse du
G\'enome : S\'equen\c{c}age et Polymorphisme},
year = {2003},
note = {M\'emoire de DEA, Universit\'e Paris VI.},
}
@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{ReDe03b,
author = {M. Régnier and A. Denise},
title = {Statistiques Extrêmes sur les Mots},
booktitle = {XXXV-èmes Journées de Statistique},
year = {2003},
volume = {2},
pages = {799–802},
note = {In Proceedings XXXV-èmes Journées de Statistique,
Lyon},
url = {http://algo.inria.fr/regnier/publis/ReDe03b.ps},
}
@inproceedings{TaEnRe03,
author = {F. Tahi and S. Engelen and M. R{\'e}gnier},
title = {A fast algorithm for {RNA} secondary structure prediction
including pseudoknots approach},
booktitle = {BIBE'03},
year = {2003},
publisher = {IEEE Computer Society},
pages = {11--17},
note = {In Proceedings BIBE'03, Washington DC},
}
@article{VaMa03,
author = {Vandenbogaert, M. and Makeev, V.},
title = {Analysis of bacterial RM-systems through genome-scale
analysis and related taxonomic issues.},
journal = {In Silico Biology},
number = {3},
year = {2003},
editor = {Edgar Wingender, 2003, Bioinformation Systems e.V.},
volume = {12},
pages = {127–143},
note = {Special Issues of Volume 3: Bioinformatics on Genome
Regulation and Structure (BGRS 2002, Novossibirsk), Published as online
journal by Bioinformation Systems e. V.; regularly issued as printed version
by IOS Press},
url = {http://www.bioinfo.de/isb/2003/03/0012/},
}
@article{BaFl02,
author = {Cyril Banderier and Philippe Flajolet},
title = {Basic Analytic Combinatorics of Directed Lattice Paths},
journal = {Theoretical Computer Science},
number = {1-2},
year = {2002},
volume = {281},
pages = {37--80},
}
@article{BaBoDeFlGaGo02,
author = {Cyril Banderier and Mireille Bousquet-M\'elou and Alain
Denise and Philippe Flajolet and Dani\`ele Gardy and Dominique
Gouyou-Beauchamps},
title = {Generating Functions of Generating Trees},
journal = {Discrete Mathematics},
number = {1-3},
year = {2002},
month = {March},
volume = {246},
pages = {29--55},
}
@book{ChFlGaMo02,
title = {Mathematics and Computer Science II: Algorithms, Trees,
Combinatorics and Probabilities},
year = {2002},
editor = {Brigitte Chauvin and Philippe Flajolet and Dani\`ele Gardy
and A. Mokkadem},
publisher = {{Birkh\"auser Verlag}},
series = {Trends in Mathematics},
address = {Basel},
note = {560 pages. Proceedings of a Colloquium held at Versailles,
September 2002},
}
@proceedings{Chyzak02,
title = {Algorithms Seminar, 2000–2001},
year = {2002},
month = {March},
editor = {Chyzak, Frédéric},
volume = {4406},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-4406.html},
abstract = {These seminar notes constitute the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, asymptotic analysis,
computational biology, and average-case analysis of algorithms and data
structures.},
}
@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.},
}
@inproceedings{DuFlLoSc02,
author = {Duchon, Philippe and Flajolet, Philippe and Louchard, Guy
and Schaeffer, Gilles},
title = {Random Sampling from {B}oltzmann Principles},
booktitle = {Automata, Languages, and Programming},
number = {2380},
year = {2002},
editor = {P. Widmayer et al.},
publisher = {Springer Verlag},
series = {Lecture Notes in Computer Science},
pages = {501--513},
note = {Proceedings of the 29th ICALP Conference, Malaga, July
2002.},
}
@misc{Fayolle02,
author = {Fayolle, Julien},
title = {Param\`etres des arbres suffixes dans le cas de sources
simples},
year = {2002},
note = {M\'emoire de DEA, Universit\'e Paris VI.},
}
@inproceedings{Flajolet02,
author = {Philippe Flajolet},
title = {Singular Combinatorics},
booktitle = {Proceedings of the International Congress of
Mathematicians},
year = {2002},
editor = {Li Tatsien},
publisher = {World Scientific},
volume = {{III}},
pages = {561--571},
note = {Invited lecture, ICM02, Beijing, China, 20--28 August
2002.},
}
@techreport{FlSe02,
author = {Philippe Flajolet and Robert Sedgewick},
title = {Analytic Combinatorics---Symbolic Combinatorics},
number = {4103},
year = {2002},
volume = {TR-02-123},
institution = {INRIA},
note = {186+vii pages.},
}
@article{FlSz02,
author = {Philippe Flajolet and Wojtek Szpankowski},
title = {Analytic Variations on Redundancy Rates of Renewal
Processes},
journal = {IEEE Transactions on Information Theory},
number = {11},
year = {2002},
volume = {48},
pages = {2911--2921},
}
@article{FlHaNiSp02,
author = {Philippe Flajolet and Kostas Hatzis and Sotiris Nikoletseas
and Paul Spirakis},
title = {On the Robustness of Interconnections in Random Graphs: A
Symbolic Approach},
journal = {Theoretical Computer Science},
number = {2},
year = {2002},
volume = {287},
pages = {513--534},
}
@inproceedings{MaSe02,
author = {Matera, Guillermo and Sedoglavic, Alexandre},
title = {The differential {H}ilbert function of a differential
rational mapping can be computed in polynomial time},
booktitle = {Proceedings of the 2002 International Symposium on Symbolic
and Algebraic Computation},
year = {2002},
month = {July~7--10},
editor = {Mora, Teo},
publisher = {ACM press},
address = {Lille, France},
organization= {Association for Computing Machinery},
pages = {184--191},
}
@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.},
}
@inproceedings{OlSe02,
author = {Ollivier, Fran\c{c}ois and Sedoglavic, Alexandre},
title = {Algorithmes efficaces pour tester l'identifiabilit{\'e}
locale},
booktitle = {Actes de la Conf\'erence Internationale Francophone
d'Automatique 2002},
year = {2002},
month = {July~8--10},
address = {Nantes, France},
organization= {IEEE},
pages = {811--816},
}
@article{PaMaLiReNaDe02,
author = {Papatsenko, Dmitri A. and Makeev, Vsevolod J. and Lifanov,
Alex P. and R{\'e}gnier, Mireille and Nazina, Anna G. and Desplan, Claude},
title = {Extraction of Functional Binding Sites from Unique
Regulatory Regions: The {\em Drosophila\/} Early Developmental Enhancers},
journal = {Genome Research},
number = {3},
year = {2002},
volume = {12},
pages = {470--481},
}
@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{Sedoglavic02,
author = {Sedoglavic, Alexandre},
title = {A probabilistic algorithm to test local algebraic
observability in polynomial time},
journal = {Journal of Symbolic Computation},
number = {5},
year = {2002},
month = {May},
volume = {33},
pages = {735--755},
}
@article{TaGoRe02,
author = {F. Tahi and M. Gouy and M. Régnier},
title = {Automatic RNA secondary structure prediction with a
comparative approach},
journal = {Computers and Chemistry},
number = {5},
year = {2002},
editor = {J. L. Risler},
volume = {26},
pages = {521–530},
note = {poster at RECOMB'01 and MFRS'01; Montréal},
url = {http://algo.inria.fr/regnier/publis/TaGoRe02.ps},
}
@article{AtChDu01,
author = {Atallah, M. J. and Chyzak, F. and Dumas, P.},
title = {A randomized algorithm for approximate string matching},
journal = {Algorithmica},
number = {3},
year = {2001},
volume = {29},
pages = {468–486},
web-comment = {Preliminary
version (INRIA Research Report #3194).},
abstract = {We give a randomized algorithm in deterministic
time O(N log M) for estimating the score vector of matches between a text
string of length N and a pattern string of length M, i.e., the vector
obtained when the pattern is slid along the text, and the number of matches
is counted for each position. A direct application is approximate string
matching. The randomized algorithm bases on convolution to find an estimator
of the scores; the variance of the estimator is particularly small for scores
that are close to M, i.e., for approximate occurrences of the pattern in
the text. No assumption is made about the probabilistic characteristics of
the input, or about the size of the alphabet. The solution extends to string
matching with classes, class complements, ``never match'' and ``always
match'' symbols, to the weighted case and to higher dimensions.},
}
@phdthesis{Banderier01,
author = {Cyril Banderier},
title = {Combinatoire analytique des chemins et des cartes},
year = {2001},
month = {June},
school = {Université Paris VI},
url = {http://algo.inria.fr/banderier/Papers/},
}
@article{BaFlShSo01,
author = {Cyril Banderier and Philippe Flajolet and Gilles Schaeffer
and Michèle Soria},
title = {Random Maps, Coalescing Saddles, Singularity Analysis, and
Airy Phenomena},
journal = {Random Structures & Algorithms},
number = {3/4},
year = {2001},
volume = {19},
pages = {194–246},
url = {http://algo.inria.fr/flajolet/Publications/rsa0903.ps.gz},
}
@article{ChFl01,
author = {Philippe Chassaing and Philippe Flajolet},
title = {Hachage, Arbres, Chemins, et Graphes},
journal = {Bulletin de Probabilit\'es},
year = {2001},
volume = {5},
address = {Universit\'e Paris VI},
pages = {1--17},
}
@article{ChPaScScZi01,
author = {Chyzak, Frédéric and Paule, Peter and Scherzer,
Otmar and Schoisswohl, Armin and Zimmermann, Burkhard},
title = {The construction of orthonormal wavelets using symbolic
methods and a matrix analytical approach for wavelets on the interval},
journal = {Experimental Mathematics},
number = {1},
year = {2001},
volume = {10},
pages = {67–86},
web-comment = {Preliminary
version.},
abstract = {In this paper we discuss closed form representations of
filter coefficients of wavelets on the real line, half real line and on
compact intervals. We show that computer algebra can be applied to achieve
this task. Moreover, we present a matrix analytical approach that unifies
constructions of wavelets on the interval.},
}
@article{ClFlVa01,
author = {Julien Clément and Philippe Flajolet and Brigitte
Vallée},
title = {Dynamical Sources in Information Theory: A General Analysis
of Trie Structures},
journal = {Algorithmica},
number = {1/2},
year = {2001},
volume = {29},
pages = {307–369},
url = {http://www.inria.fr/rrrt/rr-3645.html},
}
@article{DaMiRo01,
author = {Jean-François Dantzer and Isi Mitrani and Philippe
Robert},
title = {Large Scale and Heavy Traffic Asymptotics for Systems with
Unreliable Servers},
journal = {Queueing Systems, Theory and Applications},
number = {1},
year = {2001},
volume = {38},
pages = {5–24},
url = {http://www.inria.fr/rrrt/rr-3807.html},
}
@inproceedings{DeReVa01,
author = {A. Denise and M. Régnier and M. Vandenbogaert},
title = {Assessing statistical significance of overrepresented
oligonucleotides},
booktitle = {WABI'01},
year = {2001},
publisher = {Springer-Verlag},
pages = {85–97},
note = {Proc. First Intern. Workshop on Algorithms in
Bioinformatics, Aarhus, Denmark, August 2001},
url = {http://algo.inria.fr/regnier/publis/DeReVa01.ps},
}
@article{DuRo01,
author = {Vincent Dumas and Philippe Robert},
title = {On the maximum throughput of a resource sharing model},
journal = {Mathematics of Operation Research},
number = {1},
year = {2001},
volume = {26},
pages = {163--173},
}
@inproceedings{DuGuRo01,
author = {Vincent Dumas and Fabrice Guillemin and Philippe Robert},
title = {Limit results for {M}arkovian models of TCP},
booktitle = {Globecom'2001},
year = {2001},
month = {November},
address = {San Antonio},
}
@inproceedings{DuGuRo01a,
author = {Alain Dupuis and Fabrice Guillemin and Philippe Robert},
title = {Modeling Max-Min Fairness for Elastic Flows in
Telecommunication Networks},
booktitle = {ITC'17},
year = {2001},
month = {December},
address = {Salvador da Bahia},
}
@article{Flajolet01,
author = {Philippe Flajolet},
title = {{$D\cdot E\cdot K =(100)_8$}},
journal = {Random Structures \& Algorithms},
number = {3/4},
year = {2001},
volume = {19},
pages = {150--162},
note = {Introduction to special volume on ``Analysis of
Algorithms'' dedicated to D. E. Knuth.},
}
@article{FlLo01,
author = {Philippe Flajolet and Guy Louchard},
title = {Analytic Variations on the Airy Distribution},
journal = {Algorithmica},
number = {3},
year = {2001},
volume = {31},
pages = {361–377},
url = {http://algo.inria.fr/flajolet/Publications/Airy7.ps.gz},
}
@techreport{FlSe01,
author = {Philippe Flajolet and Robert Sedgewick},
title = {Analytic Combinatorics: Functional Equations, Rational and
Algebraic Functions},
number = {4103},
year = {2001},
institution = {INRIA},
note = {98 pages.},
}
@article{FlGoPa01,
author = {Philippe Flajolet and Xavier Gourdon and Daniel Panario},
title = {The Complete Analysis of a Polynomial Factorization
Algorithm over Finite Fields},
journal = {Journal of Algorithms},
number = {1},
year = {2001},
volume = {40},
pages = {37–81},
url = {http://www.inria.fr/rrrt/rr-3370.html},
}
@inproceedings{FlGuSzVa01,
author = {Philippe Flajolet and Yves Guivarc'h and Wojtek Szpankowski
and Brigitte Vall\'ee},
title = {Hidden Pattern Statistics},
booktitle = {Automata, Languages, and Programming},
number = {2076},
year = {2001},
editor = {F. Orejas and P. Spirakis and J. van Leeuwen},
publisher = {Springer Verlag},
series = {Lecture Notes in Computer Science},
pages = {152--165},
note = {Proceedings of the 28th ICALP Conference, Crete, July
2001.},
}
@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.},
}
@phdthesis{Lecerf01,
author = {Grégoire Lecerf},
title = {Une alternative aux méthodes de réécriture pour
la résolution des systèmes algébriques},
year = {2001},
school = {École polytechnique},
url = {http://algo.inria.fr/papers/pdf/Lecerf01.pdf},
}
@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.},
}
@inproceedings{Mishna01,
author = {Marni Mishna},
title = {Attribute grammars and automatic complexity analysis},
booktitle = {FPSAC'01},
year = {2001},
month = {May},
pages = {371–380},
url = {http://algo.inria.fr/mishna/Mishna01.ps},
}
@inproceedings{Regnier01a,
author = {M. R{\'e}gnier},
title = {Complexity of {U}nusual {W}ords {C}ounting},
booktitle = {JOBIM'00},
year = {2001},
publisher = {Springer-Verlag},
volume = {2066},
series = {Lecture Notes in Computer Science},
pages = {101--117},
note = {Proceedings of JOBIM'00, Montpellier},
}
@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{Vallee01,
author = {Vall{\'e}e, Brigitte},
title = {Dynamical Sources in Information Theory: Fundamental
Intervals and Word Prefixes},
journal = {Algorithmica},
number = {1/2},
year = {2001},
volume = {29},
pages = {262--306},
}
@inproceedings{AdJaRo00,
author = {C\'edric Adjih and Philippe Jacquet and Philippe Robert},
title = {Differentiated admission control in large networks},
booktitle = {INFOCOM 2000},
year = {2000},
publisher = {{IEEE}},
address = {Tel Aviv},
pages = {1455--1461},
}
@inproceedings{BaDo00,
author = {Cyril Banderier and Robert P. Dobrow},
title = {A Generalized Cover Time for Random Walks on Graphs},
booktitle = {FPSAC'00},
year = {2000},
month = {June},
publisher = {Springer},
pages = {113–124},
url = {http://algo.inria.fr/banderier/Papers/Dobrow/walksgraphs.ps},
}
@article{BaBoDeFlGaGo01,
author = {Cyril Banderier and Mireille Bousquet-Mélou and Alain
Denise and Philippe Flajolet and Danièle Gardy and Dominique
Gouyou-Beauchamps},
title = {Generating Functions for Generating Trees},
journal = {Discrete Mathematics},
year = {2000},
note = {An earlier version "On Generating Functions of Generating
Trees" was in the proceedings of FPSAC'99 (pp. 40-52)and as INRIA Report
3661},
url = {http://www.inria.fr/rrrt/rr-3661.html},
}
@inproceedings{BaFlShSo00,
author = {Cyril Banderier and Philippe Flajolet and Gilles Schaeffer
and Michèle Soria},
title = {Planar Maps and Airy Phenomena},
booktitle = {ICALP'00},
year = {2000},
month = {January},
publisher = {Springer-Verlag},
volume = {1853},
series = {Lecture Notes in Computer Science},
pages = {388–402},
url = {http://algo.inria.fr/banderier/Papers/Airy/coal.ps},
}
@techreport{Chyzak00a,
author = {Chyzak, Frédéric},
title = {About the non-minimality of the outputs of Zeilberger's
algorithm},
number = {00-08},
year = {2000},
month = {avril},
address = {Linz, Austria},
institution = {Austrian project SFB F013},
note = {Bruno Buchberger and Peter Paule, Eds. 20 pages},
url = {http://www.sfb013.uni-linz.ac.at/reports/2000/ps-files/sfb00-08.ps.gz},
web-comment = {This work is still at a preliminary stage and needs more
thoughts...},
abstract = {We report on case studies where Zeilberger's fast algorithm
and the other holonomy-based algorithms known so far for definite
hypergeometric summation fail to find the minimal annihilating recurrence
satisfied by the sum. To explain the phenomenon we propose a new elimination
paradigm, together with a promising heuristic method which we hope to turn
into an algorithm in the future. The approach applies to partial -finite
functions as well and extends to the related algorithms.},
}
@proceedings{Chyzak00c,
title = {Algorithms Seminar, 1999–2000},
year = {2000},
month = {November},
editor = {Chyzak, Frédéric},
volume = {4056},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-4056.html},
abstract = {These seminar notes constitute the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, asymptotic analysis,
computational biology, and average-case analysis of algorithms and data
structures.},
}
@article{Chyzak00b,
author = {Frédéric Chyzak},
title = {An Extension of Zeilberger's Fast Algorithm to General
Holonomic Functions},
journal = {Discrete Mathematics},
number = {1-3},
year = {2000},
volume = {217},
pages = {115–134},
note = {Special issue Formal power series and algebraic
combinatorics (Vienna, 1997)},
url = {http://www.inria.fr/rrrt/rr-3195.html},
web-comment = {Preliminary version (INRIA Research Report #3195).},
abstract = {(English) We extend Zeilberger's fast algorithm for
definite hypergeometric summation to non-hypergeometric holonomic sequences.
The algorithm generalizes to the differential case and to q-calculus as
well. Its theoretical justification is based on a description by linear
operators and on the theory of holonomy. (French) Nous étendons
l'algorithme rapide de Zeilberger pour la sommation
hypergéométrique définie au cas des suites holonomes non
hypergéométriques. L'algorithme se généralise aussi au cas
différentiel et du q-calcul. Sa justification théorique se fonde sur
une description par opérateurs linéaires et sur la théorie de
l'holonomie.},
}
@phdthesis{Clement00,
author = {Julien Cl\'ement},
title = {Arbres Digitaux et Sources Dynamiques},
year = {2000},
month = {September},
school = {Universit\'e de Caen},
}
@phdthesis{Dantzer00,
author = {Jean-Fran{\c{c}}ois Dantzer},
title = {Stabilit{\'e} des r{\'e}seaux de files d'attente et limites
fluides stochastiques},
year = {2000},
school = {Universit{\'e} de Versailles-St Quentin},
}
@techreport{DaRo00,
author = {Dantzer, Jean-François and Robert, Philippe},
title = {Analysis of a multi-class queueing system},
number = {4037},
year = {2000},
month = {October},
institution = {INRIA},
url = {http://www.inria.fr/rrrt/rr-4037.html},
}
@article{DaHaRo00,
author = {Dantzer, Jean-Fran\c{c}ois and Haddani, Mostapha and
Robert, Philippe},
title = {On the stability of a bandwidth packing algorithm},
journal = {Probability in the Engineering and Informational
Sciences},
number = {1},
year = {2000},
volume = {14},
pages = {57--79},
}
@article{FlGu00,
author = {Philippe Flajolet and Fabrice Guillemin},
title = {The Formal Theory of Birth-and-Death Processes, Lattice
Path Combinatorics, and Continued Fractions},
journal = {Advances in Applied Probability},
year = {2000},
volume = {32},
pages = {750–778},
url = {http://www.inria.fr/rrrt/rr-3667.html},
}
@inproceedings{FlNo00,
author = {Philippe Flajolet and Marc Noy},
title = {Analytic Combinatorics of Chord Diagrams},
booktitle = {Formal Power Series and Algebraic Combinatorics},
year = {2000},
editor = {D. Krob and A. A. Mikhalev and A. V. Mikhalev},
pages = {191–201},
note = {(Proceedings of the 12th International Conference,
FPSAC'2000; June 2000, Moscow. Lecture Notes in Computer Science)},
url = {http://algo.inria.fr/flajolet/Publications/RR3914.ps.gz},
}
@inproceedings{FlSz00,
author = {Philippe Flajolet and Wojtek Szpankowski},
title = {Analytic Variations on the Redundancy Rate of Renewal
Processes},
booktitle = {2000 IEEE International Symposium on Information
Theory},
year = {2000},
publisher = {IEEE Information Theory Society},
pages = {499},
note = {Short abstract},
url = {http://www.inria.fr/rrrt/rr-3553.html},
}
@inproceedings{FlVa00,
author = {Philippe Flajolet and Brigitte Vallée},
title = {Continued Fractions, Comparison Algorithms, and Fine
Structure Constants},
booktitle = {Analysis and Applications},
year = {2000},
editor = {M. Théra},
publisher = {American Mathematical Society},
volume = {27},
series = {Conference Proceedings, Canadian Mathematical Society},
address = {Providence},
pages = {53–82},
url = {http://algo.inria.fr/flajolet/Publications/thera10.ps.gz},
}
@inproceedings{FlHaNiSp00,
author = {Philippe Flajolet and Kostas Hatzis and Sotiris Nikoletseas
and Paul Spirakis},
title = {Trade-offs between density and robustness in random
interconnection graphs},
booktitle = {IFIP International Conference on Theoretical Computer
Science},
year = {2000},
month = {August},
editor = {J van Leeuwen and O. Watanabe and M. Hagiya and P.~D. Moses
and T. Ito},
volume = {1872},
series = {Lecture Notes in Computer Science},
pages = {152--168},
note = {(Proceedings of IFIP TCS'2000, Sendai, August 2000.)},
}
@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.},
}
@article{HiRe00,
author = {Daniel Hirschberg and Mireille R{\'e}gnier},
title = {Tight {B}ounds on the {N}umber of {S}tring
{S}ubsequences},
journal = {Journal of Discrete Algorithms},
number = {1},
year = {2000},
volume = {1},
pages = {123--132},
note = {preliminary version at CPM'99},
}
@inproceedings{KiFlYa00,
author = {John Kieffer and Philippe Flajolet and En-Hui Yang},
title = {Data Compression Via Binary Decision Diagrams},
booktitle = {{2000 IEEE International Symposium on Information
Theory}},
year = {2000},
publisher = {IEEE Information Theory Society},
pages = {296},
note = {(Short abstract).},
}
@article{KoMaRo00,
author = {Kotz, Samuel and Mahmoud, Hosam and Robert, Philippe},
title = {On Generalized {P}\'olya Urn Models},
journal = {Statistics \& Probability Letters},
number = {2},
year = {2000},
volume = {49},
pages = {163--173},
}
@article{MaFlJaRe00,
author = {Hosam Mahmoud and Philippe Flajolet and Philippe Jacquet
and Mireille Régnier},
title = {Analytic Variations on Bucket Selection and Sorting},
journal = {Acta Informatica},
number = {9-10},
year = {2000},
volume = {36},
pages = {735–760},
url = {http://www.inria.fr/rrrt/rr-3399.html},
}
@inproceedings{Nicodeme00,
author = {Pierre Nicod\`eme},
title = {Regexpcount: a Maple package for the manipulation of
automata and marked automata},
booktitle = {GCB 2000},
year = {2000},
publisher = {{Logos Verlag}},
address = {Berlin},
pages = {63--73},
}
@article{Regnier00b,
author = {M. Régnier},
title = {A Unified Approach to Word Occurrences Probabilities},
journal = {Discrete Applied Mathematics},
number = {1},
year = {2000},
volume = {104},
pages = {259–280},
note = {Special issue on Computational Biology},
url = {http://algo.inria.fr/regnier/publis/Regnier00.ps},
}
@inproceedings{ReMo00,
author = {M. R{\'e}gnier and L. Mouchard},
title = {Periods and quasiperiods characterization},
booktitle = {CPM'00},
year = {2000},
publisher = {Springer-Verlag},
volume = {1848},
series = {Lecture Notes in Computer Science},
pages = {388--396},
note = {Proc. 11-th Annual Symposium on Combinatorial Pattern
Matching, CPM'00, Montreal},
}
@inproceedings{ReLiMa00,
author = {M. R{\'e}gnier and A. Lifanov and V. Makeev},
title = {Three Variations on Word Counting},
booktitle = {GCB'00},
year = {2000},
publisher = {Logos-Verlag},
pages = {75--82},
note = {Proceedings German Conference on Bioinformatics,
Heidelberg},
}
@book{Robert00,
author = {Philippe Robert},
title = {R{\'e}seaux et files d'attente: m{\'e}thodes
probabilistes},
year = {2000},
month = {Octobre},
publisher = {Springer-Verlag},
volume = {35},
series = {Math{\'e}matiques et {A}pplications},
address = {Berlin},
pages = {x+368},
}
@inproceedings{BaBoDeFlGaGo99,
author = {Banderier, Cyril and Bousquet-M\'elou, Mireille and Denise,
Alain and Flajolet, Philippe and Gardy, Dani\`ele and Gouyou-Beauchamps,
Dominique},
title = {On Generating Functions of Generating Trees},
booktitle = {Formal Power Series and Algebraic Combinatorics},
year = {1999},
editor = {C. Mart{\'\i}nez, M. Noy, O. Serra},
pages = {40--52},
note = {Proceedings of FPSAC'99, Universitat Polit\`ecnica de
Catalunya. Version pr\'eliminaire dans le rapport de recherche INRIA
\#3661},
}
@article{ChGuPa99,
author = {Chyzak, Frédéric and Gutman, Ivan and Paule,
Peter},
title = {Predicting the Number of Hexagonal Systems with 24 and 25
Hexagons},
journal = {Communications in Mathematical and Computer Chemistry},
year = {1999},
volume = {40},
pages = {139–151},
web-comment = {Preliminary
version.},
abstract = {We predict the number of hexagonal systems consisting of 24
and 25 hexagons to be H24=122237774262384
and H25=606259305418149, with 6 and 5 significant digits, respectively.
Further estimates for Hn up to n=31 are also given.},
}
@article{CoRoSt99,
author = {Coffman, E. G., Jr. and Robert, Ph. and Stolyar, A. J.},
title = {The Interval Packing Process of Linear Networks},
journal = {ACM SIGMETRICS Performance Evaluation Review},
number = {3},
year = {1999},
month = {December},
volume = {27},
pages = {3-4},
}
@inproceedings{DaMiPuRo99,
author = {Dantzer, Jean-Fran\c{c}ois and Mitrani, Isi and Puhalskii,
Anatolii and Robert, Philippe},
title = {Large Scale and Heavy Traffic Asymptotics for Systems with
Unreliable Servers},
booktitle = {INFORMS AP99},
year = {1999},
month = {Juillet},
editor = {Volker Schmidt},
address = {Ulm},
}
@article{DeFlHuNoSt99,
author = {Luc Devroye and Philippe Flajolet and Ferran Hurtado and
Marc Noy and William Steiger},
title = {Random Triangulations},
journal = {Discrete and Computational Geometry},
year = {1999},
pages = {105--117},
keywords = {triangulation, Catalan domain},
}
@article{Flajolet99,
author = {Philippe Flajolet},
title = {Singularity analysis and asymptotics of Bernoulli sums},
journal = {Theoretical Computer Science},
number = {1-2},
year = {1999},
volume = {215},
pages = {371–381},
keywords = {singularity analysis, information theory, polylogarithm},
url = {http://www.inria.fr/rrrt/rr-3401.html},
}
@article{FlNo99,
author = {Philippe Flajolet and Marc Noy},
title = {Analytic Combinatorics of Non-crossing Configurations},
journal = {Discrete Mathematics},
number = {1-3},
year = {1999},
volume = {204},
pages = {203–229},
note = {(Selected papers in honor of Henry W. Gould)},
url = {http://www.inria.fr/rrrt/rr-3196.html},
}
@article{FlPr99,
author = {Philippe Flajolet and Helmut Prodinger},
title = {On Stirling Numbers for Complex Argument and Hankel
Contours},
journal = {SIAM Journal on Discrete Mathematics},
number = {2},
year = {1999},
volume = {12},
pages = {155–159},
url = {http://www.inria.fr/rrrt/rr-3373.html},
}
@inproceedings{FrRoTi99b,
author = {Christine Fricker and Philippe Robert and Danielle Tibi},
title = {Convergence to equilibrium of finite {M}arkov chains},
booktitle = {INFORMS AP99},
year = {1999},
month = {Juillet},
editor = {Volker Schmidt},
address = {Ulm},
}
@article{FrRoTi99a,
author = {Christine Fricker and Philippe Robert and Danielle Tibi},
title = {On the rates of convergence of {E}rlang's model},
journal = {Journal of Applied Probability},
number = {4},
year = {1999},
volume = {36},
pages = {1--18},
}
@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.},
}
@phdthesis{Chyzak98,
author = {Frédéric Chyzak},
title = {Fonctions holonomes en calcul formel},
year = {1998},
school = {École polytechnique},
note = {INRIA, TU 0531. 227 pages.},
url = {http://algo.inria.fr/chyzak/Publications/these.ps},
abstract = {(French) Cette thèse montre comment le calcul
formel permet la manipulation d'une grande classe de suites et fonctions
solutions d'opérateurs linéaires, la classe des fonctions holonomes.
Celle-ci contient de nombreuses fonctions spéciales, en une ou plusieurs
variables, et de nombreuses suites de la combinatoire. Un cadre théorique
est tout d'abord introduit pour algorithmiser les propriétés de clôture
de la classe holonome, pour y permettre un test à zéro et pour
unifier les calculs différentiels sur les fonctions et les calculs de
récurrences sur les suites. Ces méthodes s'appuient sur des calculs par
une extension de la théorie des bases de Gröbner dans un cadre de
polynômes non commutatifs, les polynômes de Ore. Deux types d'algorithmes
de sommation et d'intégration symboliques définies et indéfinies sont
ensuite développés, dont la justification théorique fait appel à la
théorie des mathcal D-modules holonomes. Les premiers ont recours à
une élimination polynomiale non commutative par bases de Gröbner ; les
seconds à des algorithmes de résolution de systèmes fonctionnels
linéaires en leurs solutions fractions rationnelles. Bien plus que la
recherche de formes closes, l'objectif est de pouvoir continuer à calculer
avec la représentation implicite des objets holonomes même en l'absence
de formes explicites. Ce type de calculs permet en particulier la preuve
automatique d'identités sommatoires et intégrales. Une implantation de
ces algorithmes dans le système de calcul formel sc Maple a permis de
donner la première preuve automatique d'identités jusqu'à présent
inaccessibles par le calcul formel. (English) This thesis shows how
computer algebra makes it possible to manipulate a large class of sequences
and functions that are solutions of linear operators, namely that of
holonomic functions. This class contains numerous special functions, in one
or several variables, as well as numerous combinatorial sequences. First, a
theoretical framework is introduced in order to give algorithms for the
closure properties of the holonomic class, to permit a zero test in this
class, and to unify differential calculations with functions and calculations
of recurrences with sequences. These methods are based on calculations by an
extension of the theory of Gröbner bases in a framework of non-commutative
polynomials, namely Ore polynomials. Two kinds of algorithms for symbolic
definite and indefinite summation and integration are then developed, whose
theoretical justification appeals to the theory of holonomic mathcal
D-modules. The former resort to non-commutative polynomial elimination by
Gröbner bases; the latter to algorithms to solve linear functional systems
for their rational function solutions. Much more than the search for closed
forms, the aim is to be able to continue to compute with the implicit
representation of holonomic objects even when no explicit form is available.
In particular, this type of calculation makes the automatic proof of
summatory and integral identities possible. An implementation of these
algorithms for the computer algebra system sc Maple has made it possible
to give the first automatic proof of identities so far unreachable by
computer algebra.},
}
@incollection{Chyzak98b,
author = {Frédéric Chyzak},
title = {Gröbner Bases, Symbolic Summation and Symbolic
Integration},
booktitle = {Gröbner Bases and Applications},
year = {1998},
editor = {B. Buchberger and F. Winkler},
publisher = {Cambridge University Press},
volume = {251},
series = {London Mathematical Society Lecture Notes Series},
pages = {32–60},
note = {Proceedings of the Conference 33 Years of Gröbner Bases,
ISBN 0-521-63298-6},
web-comment = {Preliminary
version (INRIA Research Report #3297). Errata.},
abstract = {The treatment of combinatorial expressions and special
functions by linear operators is amenable to Gröbner basis methods. In this
tutorial, we illustrate the applications of Gröbner bases to symbolic
summation and integration.},
}
@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.},
}
@inproceedings{ClFlVa98,
author = {Julien Clément and Philippe Flajolet and Brigitte
Vallée},
title = {The Analysis of Hybrid Trie Structures},
booktitle = {Proceedings of the Ninth Annual ACM–SIAM Symposium on
Discrete Algorithms},
year = {1998},
publisher = {SIAM Press},
address = {Philadelphia},
pages = {531–539},
url = {http://www.inria.fr/rrrt/rr-3295.html},
}
@article{CoFlFlHo98,
author = {Ed Coffman and Philippe Flajolet and Leopold Flatto and
Micha Hofri},
title = {The Maximum of a Random Walk and Its Application to
Rectangle Packing},
journal = {Probability in Engineering and Informational Sciences},
year = {1998},
month = {July},
volume = {12},
pages = {373–386},
keywords = {random walk, maximum, Rice integrals},
url = {http://www.inria.fr/rrrt/rr-3223.html},
}
@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.},
}
@article{FlVa98,
author = {Philippe Flajolet and Brigitte Vallée},
title = {Continued Fraction Algorithms, Functional Operators, and
Structure Constants},
journal = {Theoretical Computer Science},
number = {1–2},
year = {1998},
month = {March},
volume = {194},
pages = {1–34},
url = {http://www.inria.fr/rrrt/rr-2931.html},
}
@article{FlPoVi98,
author = {Philippe Flajolet and Patricio Poblete and Alfredo Viola},
title = {On the Analysis of Linear Probing Hashing},
journal = {Algorithmica},
number = {4},
year = {1998},
month = {December},
volume = {22},
pages = {490–515},
keywords = {hashing, linear probing, Airy distribution},
url = {http://www.inria.fr/rrrt/rr-3265.html},
}
@inproceedings{LeMo98a,
author = {R. Lercier and F. Morain},
title = {Algorithms for computing isogenies between elliptic
curves},
booktitle = {Computational Perspectives on Number Theory: Proceedings of
a Conference in Honor of A. O. L. Atkin},
year = {1998},
editor = {D. A. Buell and J. T. Teitelbaum},
publisher = {American Mathematical Society, International Press},
volume = {7},
series = {AMS/IP Studies in Advanced Mathematics},
pages = {77--96},
}
@inproceedings{Morain98a,
author = {F. Morain},
title = {Primality proving using elliptic curves: an update},
booktitle = {Algorithmic Number Theory},
year = {1998},
editor = {J. P. Buhler},
publisher = {Springer-Verlag},
volume = {1423},
series = {Lecture Notes in Computer Science},
pages = {111--127},
note = {Third International Symposium, ANTS-III, Portland, Oregon,
june 1998, Proceedings},
}
@article{Nicodeme98,
author = {Pierre Nicod\`eme},
title = {{SSMAL}: similarity searching with alignment graphs},
journal = {Bioinformatics},
number = {6},
year = {1998},
volume = {14},
pages = {508--515},
}
@inproceedings{PaGoFl98,
author = {Daniel Panario and Xavier Gourdon and Philippe Flajolet},
title = {An analytic approach to smooth polynomials over finite
fields},
booktitle = {Algorithmic Number Theory Symposium (ANTS)},
year = {1998},
editor = {J. P. Buhler},
publisher = {Springer Verlag},
volume = {1423},
series = {Lecture Notes in Computer Science},
pages = {226--236},
keywords = {random polynomial, Dickman function},
}
@misc{Regnier98b,
author = {M. R{\'e}gnier},
title = {Generating {F}unctions in {C}omputational {B}iology},
year = {1998},
note = {Invited to MABS'97},
}
@inproceedings{Regnier98a,
author = {R{\'e}gnier, M.},
title = {A {U}nified {A}pproach to {W}ord {S}tatistics},
booktitle = {RECOMB'98},
year = {1998},
publisher = {ACM},
}
@article{ReSz98b,
author = {Mireille Régnier and Wojciech Szpankowski},
title = {On Pattern Frequency Occurrences in a Markovian
Sequence?},
journal = {Algorithmica},
number = {4},
year = {1998},
volume = {22},
pages = {631–649},
note = {This paper was presented in part at the 1997 International Symposium on Information Theory, Ulm, Germany.},
url = {http://algo.inria.fr/papers/other/ReSz97b.ps.gz},
}
@inproceedings{ReSz98c,
author = {Mireille Régnier and Wojciech Szpankowski},
title = {On the Approximate Pattern Occurrences in a Text},
booktitle = {Compression and Complexity of SEQUENCES 1997},
year = {1998},
publisher = {IEEE Computer Society},
pages = {253–264},
note = {Proceedings SEQUENCE'97, Positano, Italy},
url = {http://algo.inria.fr/papers/other/ReSz97a.ps.gz},
}
@inproceedings{ReSz98a,
author = {Mireille Régnier and Wojtek Szpankowski},
title = {Complexity of Sequential Pattern Matching
Algorithms},
booktitle = {RANDOM'98},
number = {1518},
year = {1998},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
pages = {187–199},
url = {http://algo.inria.fr/papers/other/ReSz98a.ps},
}
@article{Robert98,
author = {Philippe Robert},
title = {A remark on the space-time properties of some storage
processes},
journal = {Queueing Systems, Theory and Applications},
number = {2-4},
year = {1998},
volume = {29},
pages = {189--192},
}
@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.},
}
@inproceedings{Chyzak97,
author = {Chyzak, Frédéric},
title = {An Extension of Zeilberger's Fast Algorithm to General
Holonomic Functions},
booktitle = {Formal Power Series and Algebraic Combinatorics, 9th
Conference},
year = {1997},
organization= {Universität Wien},
pages = {172–183},
note = {Conference proceedings. Subsumed in [Chyzak, 2000c]},
web-comment = {Preliminary version (INRIA Research Report #3195).},
}
@techreport{DaDu97,
author = {Dantzer, Jean-Francois and Dumas, Vincent},
title = {Conditions d'ergodicité de l'anneau de Cambridge et de
certaines de ses faces. Limites fluides},
number = {3320},
year = {1997},
month = {December},
institution = {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-3320.html},
}
@article{DaFlVa97,
author = {Hervé Daudé and Philippe Flajolet and Brigitte
Vallée},
title = {An Average-case Analysis of the Gaussian Algorithm for
Lattice Reduction},
journal = {Combinatorics, Probability and Computing},
number = {4},
year = {1997},
month = {December},
volume = {6},
pages = {329–349},
url = {http://www.inria.fr/rrrt/rr-2798.html},
}
@article{DrSo97,
author = {Drmota, Michael and Soria, Mich{\`e}le},
title = {Images and Preimages in Random Mappings},
journal = {SIAM Journal on Discrete Mathematics},
number = {2},
year = {1997},
month = {May},
volume = {10},
pages = {246--269},
}
@book{DuGo97,
author = {Philippe Dumas and Xavier Gourdon},
title = {Maple Son bon usage en math\'ematiques},
year = {1997},
publisher = {Springer-Verlag},
note = {ISBN 3-540-63140-2},
}
@incollection{Flajolet97b,
author = {Philippe Flajolet},
title = {Adaptive Sampling},
booktitle = {Encyclopaedia of Mathematics},
year = {1997},
editor = {M. Hazewinkel},
publisher = {Kluwer Academic Publishers},
volume = {Supplement~{I}},
address = {Dordrecht},
pages = {28},
}
@article{Flajolet97a,
author = {Flajolet, Philippe},
title = {Review of {M}icha {H}ofri's book ``{{\em {A}nalysis of
{A}lgorithms}}''},
journal = {SIAM Review},
number = {2},
year = {1997},
month = {June},
volume = {39},
pages = {341--345},
keywords = {analysis of algorithms},
}
@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.},
}
@techreport{FlSe97,
author = {Philippe Flajolet and Robert Sedgewick},
title = {The Average Case Analysis of Algorithms: Multivariate
Asymptotics and Limit Distributions},
number = {3162},
year = {1997},
month = {May},
institution = {Institut National de Recherche en Informatique et en
Automatique},
note = {123 pages.},
}
@article{FlSz97,
author = {Flajolet, Philippe and Szpankowski, Wojtek},
title = {Analysis of Algorithms},
journal = {Random Structures and Algorithms},
number = {1--2},
year = {1997},
month = {January},
volume = {10},
pages = {1--3},
}
@proceedings{FlSz97b,
title = {Average--Case Analysis of Algorithms},
year = {1997},
editor = {Philippe Flajolet and Wojtek Szpankowski},
publisher = {John Wiley},
volume = {10(1--2)},
series = {Random Structures and Algorithms},
note = {Special issue of the the journal, 302 pages.},
}
@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).},
}
@article{MaReSm97,
author = {{M}ahmoud, H. and R{\'e}gnier, M. and {S}mythe, R.},
title = {Analysis of {B}oyer-{M}oore-{H}orspool {S}tring-{M}atching
{H}euristic},
journal = {Random Structures and Algorithms},
year = {1997},
volume = {10},
pages = {169--186},
}
@article{MaSmRe97,
author = {Hosam M. Mahmoud and Robert T. Smythe and Mireille
Régnier},
title = {Analysis of Boyer-Moore-Horspool String-Matching
Heuristic},
journal = {Random Structures and Algorithms},
number = {1-2},
year = {1997},
volume = {10},
pages = {169–186},
url = {http://algo.inria.fr/papers/other/stringmatch.ps.gz},
}
@article{Morain97,
author = {F. Morain},
title = {Classes d'isomorphismes des courbes elliptiques
supersinguli\`eres en caract\'eristique $\geq 3$},
journal = {\em Utilitas Mathematica},
year = {1997},
month = {December},
volume = {52},
pages = {241--253},
}
@phdthesis{Morain97b,
author = {F. Morain},
title = {Courbes elliptiques, arithm\'etique et corps finis},
year = {1997},
school = {Universit{\'e} Paris 6},
}
@phdthesis{Nicodeme97b,
author = {Nicod\`eme, P.},
title = {Alignement avec des {F}amilles de {S}\'equences
{P}rot\'eiques},
year = {1997},
month = {September},
school = {Universit\'e {P}aris {V}{I}{I}},
}
@inproceedings{NiSt97,
author = {Nicod\`eme, P. and Steyaert, J.-M.},
title = {Selecting Optimal Oligonucleotide Primers for Multiplex
{P}{C}{R}},
booktitle = {Fifth International Conference on Intelligent Systems for
Molecular Biology},
year = {1997},
publisher = {{AAAI} Press},
pages = {210--213},
}
@article{FlGoMa97,
author = {Philippe Flajolet, Xavier Gourdon and Conrado
Martínez},
title = {Patterns in random binary search trees},
journal = {Random Structures and Algorithms},
number = {3},
year = {1997},
month = {October},
volume = {11},
pages = {223–244},
url = {http://www.inria.fr/rrrt/rr-2883.html},
}
@inproceedings{ReSz97a,
author = {Mireille Régnier and Wojciech Szpankowski},
title = {On the Approximate Pattern Occurrences in a Text},
booktitle = {Compression and Complexity of SEQUENCES 1997},
year = {1997},
editor = {IEEE Computer Society},
pages = {253–264},
note = {In Proceedings SEQUENCE'97,Positano, Italy},
url = {http://algo.inria.fr/papers/other/ReSz97a.ps.gz},
}
@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.},
}
@book{SoBrMoPa97,
author = {Mich{\`e}le Soria and Anne Brygoo and Michelle Morcrette
and Odile Pali{\`e}s},
title = {Initiation {\`a} la programmation par {W}ord et {E}xcel},
year = {1997},
publisher = {Vuibert},
series = {Passeport pour l'informatique},
note = {516 pages (ISBN 2-84180-112-8)},
}
@article{DuFl96,
author = {Dumas, Ph. and Flajolet, Ph.},
title = {Asymptotique des récurrences mahleriennes: le cas
cyclotomique},
journal = {Journal de théorie des nombres de Bordeaux},
year = {1996},
volume = {8},
url = {http://algo.inria.fr/papers/other/DuFl96.ps.gz},
}
@inproceedings{Flajolet96b,
author = {Flajolet, Philippe},
title = {Analytic Variations on Quadtrees},
booktitle = {Notes of the Seminar on Probabilistic Methods in
Algorithmics},
number = {5},
year = {1996},
series = {Quaderns, Centre de Recerca Matem{\`a}tica},
address = {Barcelona},
pages = {44--53},
keywords = {lattice reduction, Gauss, continued fraction},
note = {(Summary written by Nicola Galesi)},
}
@techreport{FlSe96,
author = {Philippe Flajolet and Robert Sedgewick},
title = {The Average Case Analysis of Algorithms: Mellin Transform
Asymptotics},
year = {1996},
institution = {Institut National de Recherche en Informatique et en
Automatique},
note = {pages.},
}
@inproceedings{FlGoPa96,
author = {Philippe Flajolet and Xavier Gourdon and Daniel Panario},
title = {Random Polynomials and Polynomial Factorization},
booktitle = {ICALP},
number = {1099},
year = {1996},
editor = {F. Meyer auf der Heide},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
pages = {232–243},
note = {Proceedings 23rd ICALP conference},
url = {http://www.inria.fr/rrrt/rr-2852.html},
}
@phdthesis{Gourdon96,
author = {Gourdon, Xavier},
title = {Combinatoire, algorithmique et géométrie des
polynômes},
year = {1996},
school = {École polytechnique},
url = {http://algo.inria.fr/papers/other/Gourdon96.ps},
}
@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.},
}
@article{GuMo96,
author = {Guillaume, D. and Morain, F.},
title = {Building pseudoprimes with a large number of prime
factors},
journal = {Applicable Algebra in Engineering, Communication and
Computing},
number = {4},
year = {1996},
volume = {7},
pages = {263--277},
}
@article{JaSz96,
author = {Jacquet, Ph. and Szpankowski, W.},
title = {Analytical depoissonization and its applications},
journal = {Theoretical Computer Science},
year = {1996},
note = {68 pp.},
}
@inproceedings{JaMuRo96d,
author = {Philippe Jacquet and Paul M{\"u}hlethaler and Philippe
Robert},
title = {Asymptotic average access delay analysis: adaptive
p-persistence versus tree algorithm},
booktitle = {IEEE 802.14 Normalization Conference},
year = {1996},
pages = {248},
}
@inproceedings{JaMuRo96c,
author = {Philippe Jacquet and Paul M{\"u}hlethaler and Philippe
Robert},
title = {Framing protocols on upstream channel in {CATV} networks:
asymptotic average delay analysis},
booktitle = {IEEE 802.14 Normalization Conference},
year = {1996},
pages = {247},
}
@inproceedings{JaMuRo96b,
author = {Philippe Jacquet and Paul M{\"u}hlethaler and Philippe
Robert},
title = {Simulation of a stack algorithm with priorities and
reservations},
booktitle = {IEEE 802.14 Normalization Conference},
year = {1996},
pages = {181},
}
@inproceedings{JaMuRo96,
author = {Philippe Jacquet and Paul M{\"u}hlethaler and Philippe
Robert},
title = {A unified approach for {CATV} networks capable of mixing
{ATM} and non {ATM} traffics with {CBR} and non {CBR} traffics},
booktitle = {IEEE 802.14 Normalization Conference},
year = {1996},
pages = {180},
}
@misc{Lecomte96,
author = {Lecomte, O.},
title = {R\'eseaux sans fil: Adaptation d'{HiPeRLAN} type~1 sur
{W}avelan},
year = {1996},
note = {M\'emoire de {DEA}, Supelec},
}
@article{MoShWi96,
author = {Morain, F. and Shallit, J. and Williams, H. C.},
title = {La machine {\`a} congruences},
journal = {La revue du Mus{\'e}e des Arts et M{\'e}tiers},
year = {1996},
month = {March},
volume = {14},
pages = {14--19},
}
@misc{Qayyum96,
author = {Qayyum, A.},
title = {Wireless Networks: {HiPeRLAN}},
year = {1996},
note = {M\'emoire de {DEA}, Universit\'e de Paris-Sud},
}
@inproceedings{ReRo96,
author = {Mireille Régnier and Ladan Rostami},
title = {A Simple (but Optimal) 2D-Witness Algorithm},
booktitle = {Third South American Workshop on String Processing},
number = {4},
year = {1996},
series = {International Informatics Series},
pages = {243–256},
url = {http://algo.inria.fr/papers/other/witness.ps.gz},
}
@inproceedings{ReTa96,
author = {R{\'e}gnier, M. and Tahi, F.},
title = {Enumeration and Asymptotics in Computational Biology},
booktitle = {Mathematical Analysis for Biological Sequences},
year = {1996},
note = {Proceedings of a workshop held in Trondheim, Norway},
}
@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.},
}
@inproceedings{Robert96,
author = {Robert, Ph.},
title = {Synchronisation d'un syst\`eme de ressources et probl\`emes
reli\'es},
booktitle = {Journ\'ees SMAI mod\'elisation al\'eatoire et
statistique},
year = {1996},
month = {September},
address = {Toulouse},
organization= {SMAI},
}
@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},
}
@book{SeFl96b,
author = {Robert Sedgewick and Philippe Flajolet},
title = {Introduction \`a l'analyse d'algorithmes},
year = {1996},
publisher = {International Thomson publishing France},
note = {Traduction de Cyril Chabaud. (ISBN 2-84180-957-9)},
}
@book{SeFl96a,
author = {Robert Sedgewick and Philippe Flajolet},
title = {An Introduction to the Analysis of Algorithms},
year = {1996},
publisher = {Addison-Wesley Publishing Company},
note = {512 pages. (ISBN 0-201-40009-X)},
}
@mastersthesis{Chyzak95,
author = {Chyzak, Fr\'ed\'eric},
title = {Manipulations formelles d'op\'erateurs lin\'eaires et
calculs holonomes},
year = {1995},
month = {June},
school = {\'Ecole Polytechnique},
}
@article{CoGiGrLeRoSt95,
author = {Coffman, E.~G. and Gilbert, E.~N. and Greenberg, A.~G. and
Leighton, F.~T. and Robert, P. and Stolyar, A.~L.},
title = {Queues served by a rotating ring},
journal = {Stochastic Models},
number = {3},
year = {1995},
volume = {11},
key = {Queueing Systems},
pages = {371--394},
}
@inproceedings{Crapo95d,
author = {Crapo, Henry},
title = {Gian-Carlo Rota on Combinatorics},
booktitle = {Rota's ``Combinatorial Theory''},
year = {1995},
publisher = {Birkha{\"u}ser Verlag},
volume = {1},
pages = {xix-xliii},
}
@article{Crapo95,
author = {Crapo, Henry},
title = {Projective Configurations: their Invariants and Homology},
journal = {Proceedings of the Royal Irish Academy},
year = {1995},
note = {Special issue ``The Mathematical Heritage of Sir William
Rowan Hamilton'', 33 pages.},
}
@inproceedings{Crapo95b,
author = {Crapo, Henry and Richter-Gebert, J{\"u}rgen},
title = {Automatic Proving of Geometric Theorems},
booktitle = {Invariant Methods in Discrete and Computational Geometry},
year = {1995},
editor = {Neil White},
publisher = {Kluwer Academic Publishers},
pages = {167-196},
}
@inproceedings{Crapo95c,
author = {Crapo, Henry and Rota, Gian-Carlo},
title = {The Resolving Bracket},
booktitle = {Invariant Methods in Discrete and Computational Geometry},
year = {1995},
editor = {Neil White},
publisher = {Kluwer Academic Publishers},
pages = {197-222},
}
@article{DrSo95,
author = {Michael Drmota and Mich\`ele Soria},
title = {Marking in Combinatorial Constructions: Generating
Functions and Limiting Distributions},
journal = {Theoretical Computer Science},
number = {1--2},
year = {1995},
volume = {144},
pages = {67--99},
}
@phdthesis{Dumas01,
author = {Dumas, V.},
title = {Approches fluides pour la stabilit\'e et l'instabilit\'e de
r\'eseaux de files d'attente stochastiques \`a plusieurs classes de
clients},
year = {1995},
month = {December},
key = {Ergodicity},
school = {\'Ecole polytechnique},
}
@techreport{DuGo95,
author = {Philippe Dumas and Xavier Gourdon},
title = {Une introduction à Maple},
number = {173},
year = {1995},
institution = {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rt-0173.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{DuTh95,
author = {Dumas, Ph. and Thimonier, L.},
title = {Random palindromes: multivariate generating function and
Bernoulli density},
journal = {Discrete Mathematics},
number = {1–3},
year = {1995},
volume = {139},
pages = {143–154},
url = {http://www.inria.fr/papers/other/DuTh95.ps.gz},
}
@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{FlGoDu95,
author = {Flajolet, P. and Gourdon, X. and Dumas, P.},
title = {Mellin Transforms and Asymptotics : Harmonic Sums},
journal = {Theoretical Computer Science},
number = {1–2},
year = {1995},
volume = {144},
pages = {3–58},
url = {http://www-rocq.inria.fr/algo/flajolet/Publications/mellin-harm.ps.gz},
}
@article{FlGrKiPr95,
author = {Philippe Flajolet and Peter Grabner and Peter Kirschenhofer
and Helmut Prodinger},
title = {On Ramanujan's Q-function},
journal = {Journal of Computational and Applied Mathematics},
number = {1},
year = {1995},
volume = {58},
pages = {103–116},
keywords = {Ramanujan, Knuth, Q(n) function, linear probing hashing,
asymptotic bounds},
url = {http://www-rocq.inria.fr/algo/flajolet/Publications/rama.ps.gz},
}
@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},
}
@inproceedings{Gourdon95,
author = {Gourdon, Xavier},
title = {Largest Component in Random Combinatorial Structures},
booktitle = {Formal power series and algebraic combinatorics},
year = {1995},
editor = {B. Leclerc and J. Y. Thibon},
publisher = {Universit\'e de Marne-la-Vall\'ee},
pages = {249--260},
note = {Proceedings SFCA'95},
}
@article{JaSz95,
author = {Jacquet, Philippe and Szpankowski, Wojciech},
title = {Asymptotic behavior of the Lempel-Ziv parsing scheme and
digital search trees},
journal = {Theoretical Computer Science},
year = {1995},
month = {June},
volume = {144},
pages = {161--197},
}
@inproceedings{JaMuRo95,
author = {Philippe Jacquet and Paul M{\"u}hlethaler and Philippe
Robert},
title = {{CATV} slotted multiple access {MAC}},
booktitle = {IEEE 802.14 Normalization Conference},
year = {1995},
pages = {166},
}
@inproceedings{JaMuRo95c,
author = {Philippe Jacquet and Paul M{\"u}hlethaler and Philippe
Robert},
title = {Performant implementations of tree collision resolution on
{CATV} network},
booktitle = {IEEE 802.14 Normalization Conference},
year = {1995},
pages = {115},
}
@inproceedings{JaMuRo95b,
author = {Philippe Jacquet and Paul M{\"u}hlethaler and Philippe
Robert},
title = {Using {QoS} parameters to support various traffics on
{CATV} multiple access {MAC}},
booktitle = {IEEE 802.14 Normalization Conference},
year = {1995},
pages = {172},
}
@article{JoMo95,
author = {Joux, A. and Morain, F.},
title = {Sur les sommes de caract{\`e}res li{\'e}es aux courbes
elliptiques {\`a} multiplication complexe},
journal = {Journal of Number Theory},
number = {1},
year = {1995},
month = {November},
volume = {55},
pages = {108--128},
}
@inproceedings{LeMo95,
author = {Lercier, R. and Morain, F.},
title = {Counting the number of points on elliptic curves over
finite fields: strategies and performances},
booktitle = {Advances in Cryptology -- EUROCRYPT '95},
number = {921},
year = {1995},
editor = {L. C. Guillou and J.-J. Quisquater},
series = {Lecture Notes in Computer Science},
pages = {79--94},
note = {International Conference on the Theory and Application of
Cryptographic Techniques, Saint-Malo, France, May 1995, Proceedings},
}
@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.},
}
@article{Morain95a,
author = {Morain, Fran\c{c}ois},
title = {Calcul du nombre de points sur une courbe elliptique dans
un corps fini~: aspects algorithmiques},
journal = {Journal de Th{\'e}orie des Nombres de Bordeaux},
year = {1995},
volume = {7},
pages = {255--282},
}
@book{MoNi95,
author = {Fran{\c{c}}ois Morain and Jean-Louis Nicolas},
title = {Math{\'e}matiques \& {I}nformatique, {Q}uatorze
probl{\`e}me corrig{\'e} pour l'enseignement sup{\'e}rieur},
year = {1995},
publisher = {Vuibert},
series = {Enseignement sup{\'e}rieur \& {I}nformatique},
}
@article{Nicodeme95,
author = {Nicod\`eme, Pierre},
title = {A computer support for genotyping by multiplex {P}{C}{R}},
journal = {Technique et Science Informatique},
number = {1},
year = {1995},
volume = {14},
pages = {23--34},
note = {Num\'ero sp\'ecial informatique et g\'enomes},
}
@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.},
}
@article{ShWiMo95,
author = {Shallit, J. and Williams, H. C. and Morain, F.},
title = {Discovery of a lost factoring machine},
journal = {Mathematical Intelligencer},
number = {3},
year = {1995},
volume = {17},
pages = {41--47},
}
@techreport{Chyzak94,
author = {Frédéric Chyzak},
title = {Holonomic Systems and Automatic Proofs of Identities},
number = {2371},
year = {1994},
month = {October},
institution = {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-2371.html},
abstract = {This report presents three computer algebra packages in the
Maple language for the symbolic manipulation of linear systems of
differential and recurrence equations. They are especially designed to deal
with so-called holonomic systems. We also give a theoretical justification to
our implementation. The set of holonomic functions and sequences is a large
class of objects. It forms an algebra and is closed under algebraic
substitution and diagonal. An implementation of these properties makes it
possible to perform computer assisted proofs of holonomic identities in a
simple way, since any holonomic system has a normal form obtained by an
extension of the Gröbner basis algorithm. For instance, combinatorial
problems often lead to holonomic systems and to identities involving binomial
coefficients. Many identities involving special functions are also captured
by the theory of holonomy. Examples are given to show how some interesting
identities are proved by our system.},
}
@inproceedings{CoMo94,
author = {Couveignes, J.-M. and Morain, F.},
title = {Schoof's algorithm and isogeny cycles},
booktitle = {Algorithmic Number Theory Symposium},
year = {1994},
editor = {L. Adleman and M.-D. Huang},
publisher = {Springer-Verlag},
volume = {877},
series = {Lecture Notes in Computer Science},
pages = {43--58},
note = {1st Algorithmic Number Theory Symposium - Cornell
University, May 6-9, 1994},
}
@article{Crapo94,
author = {Crapo, Henry and Penne, Rudi},
title = {Chirality and the Isotopy Classification of Skew Lines in
Projective 3-Space},
journal = {Advances in Mathematics},
year = {1994},
volume = {103},
pages = {1--106},
}
@inproceedings{DaFlVa94,
author = {Daud\'e, Herv\'e and Flajolet, Philippe and Vall\'ee,
Brigitte},
title = {An Analysis of the {G}aussian Algorithm for Lattice
Reduction},
booktitle = {Algorithmic Number Theory Symposium},
number = {877},
year = {1994},
editor = {L. Adleman},
series = {Lecture Notes in Computer Science},
pages = {144-158},
keywords = {lattice reduction},
note = {Proceedings of {\em ANTS'94}.},
}
@article{FlGo94,
author = {Flajolet, Philippe and Golin, Mordecai},
title = {Mellin Transforms and Asymptotics: The Mergesort
Recurrence},
journal = {Acta Informatica},
year = {1994},
volume = {31},
pages = {673--696},
keywords = {divide-and-conquer recurrence, Mellin transform,
mergesort},
}
@article{FlLa94,
author = {Flajolet, Philippe and Lafforgue, Thomas},
title = {Search Costs in Quadtrees and Singularity Perturbation
Asymptotics},
journal = {Discrete and Computational Geometry},
number = {4},
year = {1994},
volume = {12},
pages = {151--175},
keywords = {singularity perturbation, bivariate asymptotic, limit law,
quadtree},
}
@article{FlSe95,
author = {Philippe Flajolet and Robert Sedgewick},
title = {Mellin Transforms and Asymptotics : Finite Differences and
Rice's Integrals},
journal = {Theoretical Computer Science},
number = {1-2},
year = {1994},
volume = {144},
pages = {101–124},
url = {http://www-rocq.inria.fr/algo/flajolet/Publications/mellin-rice.ps.gz},
}
@article{FlGrKiPrTi94,
author = {Philippe Flajolet and Peter Grabner and Peter Kirschenhofer
and Helmut Prodinger and Robert Tichy},
title = {Mellin Transforms and Asymptotics: Digital Sums},
journal = {Theoretical Computer Science},
number = {2},
year = {1994},
volume = {123},
pages = {291–314},
keywords = {Mellin transforms, digital sum, number representation},
url = {http://www-rocq.inria.fr/algo/flajolet/Publications/mellin-dig.ps.gz},
}
@article{FlZiVa94,
author = {Philippe Flajolet and Paul Zimmerman and Van Cutsem,
Bernard},
title = {A Calculus for the Random Generation of Labelled
Combinatorial Structures},
journal = {Theoretical Computer Science},
number = {1-2},
year = {1994},
volume = {132},
pages = {1–35},
keywords = {random generation, complexity calculus, simulation},
url = {http://www.inria.fr/rrrt/rr-1830.html},
}
@book{Gourdon94a,
author = {Xavier Gourdon},
title = {Les maths en t\^ete, math\'ematiques pour $M'$,
Alg\`ebre},
year = {1994},
publisher = {Ellipse},
note = {288 pages},
}
@book{Gourdon94b,
author = {Xavier Gourdon},
title = {Les maths en t\^ete, math\'ematiques pour $M'$, Analyse},
year = {1994},
publisher = {Ellipse},
note = {416 pages},
}
@phdthesis{Hwang94,
author = {Hwang, H.-K.},
title = {Th{\'e}or{\`e}mes Limites pour les Structures Combinatoires
et les Fonctions Arithm{\'e}tiques},
year = {1994},
month = {December},
address = {Palaiseau, France},
school = {{\'E}cole Polytechnique},
}
@article{JMRo94,
author = {Jean-Marie, A. and Robert, Ph.},
title = {On the transient behavior of some single server queues},
journal = {Queueing Systems, Theory and Applications},
number = {1-2},
year = {1994},
volume = {7},
key = {Limit Theorems},
pages = {129--136},
}
@article{MaRo94,
author = {Malyshev, V.A. and Robert, P.},
title = {Phase transition in a loss load sharing model},
journal = {Annals of Applied Probability},
number = {4},
year = {1994},
volume = {4},
key = {Limit Theorems},
pages = {1161–1176},
html = {[ps]5},
}
@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.},
}
@article{Zimmermann94,
author = {Paul Zimmermann},
title = {Ga{\"\i}a: A Package for the Random Generation of
Combinatorial Structures},
journal = {MapleTech},
number = {1},
year = {1994},
volume = {1},
pages = {38--46},
keywords = {random generation, computer algebra},
}
@article{AtJaSz93,
author = {Atallah, M. and Jacquet, Ph. and Szpankowski, W.},
title = {A probabilistic analysis of a pattern matching problem},
journal = {Random Structures and Algorithms},
number = {2},
year = {1993},
volume = {4},
pages = {191--213},
}
@article{AtMo93b,
author = {A. O. L. Atkin and F. Morain},
title = {Elliptic Curves and Primality Proving},
journal = {Mathematics of Computation},
number = {203},
year = {1993},
month = {July},
volume = {61},
url = {http://www.inria.fr/rrrt/rr-1256.html},
}
@article{AtMo93,
author = {A. O. L. Atkin and F. Morain},
title = {Finding suitable curves for the Elliptic Curve factoring
method},
journal = {Mathematics of Computation},
number = {201},
year = {1993},
month = {January},
volume = {60},
url = {http://www.inria.fr/rrrt/rr-1547.html},
}
@article{BaRe93,
author = {Baeza-Yates, R. and R{\'e}gnier, M.},
title = {Fast Algorithms for Two Dimensional and Multiple Pattern
Matching},
journal = {Information Processing Letters},
number = {1},
year = {1993},
volume = {45},
pages = {51--57},
}
@inproceedings{Breslauer93a,
author = {Breslauer, D.},
title = {Saving {C}omparisons in the {C}rochemore-{P}errin {S}tring
{M}atching {A}lgorithm},
booktitle = {ESA'93},
year = {1993},
editor = {Th. Lengauer},
publisher = {Springer-Verlag},
volume = {726},
series = {Lecture Notes in Computer Science},
pages = {61--72},
note = {In Proc. 1-st Annual European Symposium on Algorithms, Bad
Honnef, Germany},
}
@article{Breslauer93b,
author = {Breslauer, D.},
title = {Testing superprimitivity},
journal = {Information Processing Letters},
year = {1993},
volume = {44},
pages = {345--347},
}
@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.},
}
@article{Crapo93,
author = {Crapo, Henry},
title = {On the Anick-Rota Resolution of the Bracket Ring},
journal = {Advances in Mathematics},
year = {1993},
volume = {99},
pages = {97-123},
}
@article{Crapo93b,
author = {Crapo, Henry and Whiteley, Walter},
title = {Autocontraintes planes et poly\`edres projet\'es I~: le
motif de base},
journal = {Topologie Structurale},
year = {1993},
volume = {20},
pages = {391--400},
}
@inproceedings{Dumas93a,
author = {Dumas, Ph.},
title = {Algebraic Aspects of B-regular Series},
booktitle = {Automata, Languages and Programming},
year = {1993},
editor = {A. Lingas and R. Karlsson and S. Carlsson},
publisher = {Springer Verlag},
series = {Lecture Notes in Computer Science},
organization= {EATCS},
pages = {457–468},
note = {Proceedings of the 20th International Colloquium ICALP 93,
Lund, Sweden},
url = {http://algo.inria.fr/papers/other/Dumas93a.ps.gz},
}
@phdthesis{Dumas93,
author = {Ph. Dumas},
title = {Récurrences Mahlériennes, suites automatiques et
études asymptotiques},
year = {1993},
school = {Université de Bordeaux I},
url = {ftp://ftp.inria.fr/INRIA/publication/Theses/TU-0252/},
}
@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.},
}
@inproceedings{FaReSi93,
author = {Fabret, F. and R{\'e}gnier, M. and Simon, E.},
title = {An {A}daptative {A}lgorithm for {I}ncremental {E}valuation
of {P}roduction {R}ules in {D}atabases},
booktitle = {VLDB'93},
year = {1993},
publisher = {M.~ Kaufmann},
series = {IEEE},
pages = {455--466},
note = {Proc. 19th International Conference on Very Large
Databases, Dublin, Ireland},
}
@inproceedings{FlGo93,
author = {Flajolet, Philippe and Golin, Mordecai},
title = {Exact asymptotics of divide--and--conquer recurrences},
booktitle = {Automata, Languages, and Programming},
number = {700},
year = {1993},
editor = {A. Lingas and R. Karlsson and S. Carlsson},
publisher = {Springer Verlag},
series = {Lecture Notes in Computer Science},
pages = {137--149},
note = {Proceedings of the 20th ICALP Conference, Lund, July
1993},
}
@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{FlSo93,
author = {Philippe Flajolet and Mich{\`e}le Soria},
title = {General Combinatorial Schemas: {G}aussian limit
distributions and exponential tails},
journal = {Discrete Mathematics},
year = {1993},
volume = {114},
pages = {159--180},
}
@article{FlGoPuRo93,
author = {Flajolet, Philippe and Gonnet, Gaston and Puech, Claude and
Robson, J. M.},
title = {Analytic Variations on Quadtrees},
journal = {Algorithmica},
number = {6},
year = {1993},
month = {December},
volume = {10},
pages = {473-500},
keywords = {quadtree, differential equation},
}
@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{FlZiVa93b,
author = {Flajolet, Philippe and Zimmerman, Paul and Van~Cutsem,
Bernard},
title = {A Calculus of Random Generation},
booktitle = {Algorithms---ESA'93},
number = {726},
year = {1993},
editor = {Thomas Lengauer},
series = {Lecture Notes in Computer Science},
pages = {169--180},
note = {Proceedings of the First European Symposium on Algorithms,
Bad Honnef, September 1993.},
}
@inproceedings{GoRaScSm93a,
author = {Golin, Mordecai and Raman, Rajeev and Schwarz, Christian
and Smid, Michiel},
title = {Randomized Data Structures for the Dynamic Closest Pair
problem},
booktitle = {Fourth Annual Symposium on Discrete Algorithms (SODA'93)},
year = {1993},
}
@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.},
}
@article{LiDu93,
author = {B. Litow and Dumas, Ph.},
title = {Additive cellular automata and algebraic series},
journal = {Theoretical Computer Science},
number = {2},
year = {1993},
month = {October},
volume = {119},
pages = {345–354},
url = {http://algo.inria.fr/papers/other/LiDu93.ps.gz},
}
@inproceedings{Morain92e,
author = {Morain, Fran\c{c}ois},
title = {Pseudoprimes: a survey of recent results},
booktitle = {Eurocode 1992},
year = {1993},
editor = {P. Camion and P. Charpin and S. Harari},
publisher = {Springer},
series = {CISM Courses and Lectures},
pages = {207--215},
note = {Udine, novembre 1992},
}
@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{RaJaSz93,
author = {Rais, B. and Jacquet, Ph. and Szpankowski, W.},
title = {A limiting distribution for the depth in Patricia tries},
journal = {SIAM Journal on Discrete Mathematics},
number = {2},
year = {1993},
month = {May},
volume = {6},
pages = {197--213},
}
@inproceedings{ReRo93a,
author = {R{\'e}gnier, M. and Rostami, L.},
title = {A {U}nifying {L}ook at $d$-dimensional {P}eriodicities and
{S}pace {C}overings},
booktitle = {CPM'93},
year = {1993},
publisher = {Springer-Verlag},
volume = {684},
series = {Lecture Notes in Computer Science},
pages = {215--227},
note = {Proceedings 4th Symposium on Combinatorial Pattern
Matching, Padova, Italy},
}
@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{AtJaSz92b,
author = {Atallah, M. and Jacquet, Ph. and Szpankowski, W.},
title = {Pattern matching with mismatches: a randomized algorithm
and its analysis},
booktitle = {3rd Combinatorial Pattern Matching conference},
year = {1992},
month = {May},
address = {Tucson},
}
@article{BaRe92b,
author = {Baeza-Yates, R. and R{\'e}gnier, M.},
title = {Average Running Time of {B}oyer-{M}oore-{H}orspool
Algorithm},
journal = {Theoretical Computer Science},
year = {1992},
volume = {92},
pages = {19--31},
note = {special issue},
}
@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{DuTh92,
author = {Dumas, Philippe and Thimonier, Lo{\"y}s},
title = {Random palindromes: multivariate generating function and
{B}ernoulli density},
booktitle = {S{\'e}ries formelles et combinatoire alg{\'e}brique},
year = {1992},
editor = {P. Leroux and C. Reutenauer},
volume = {11},
series = {Publications du LACIM, Universit{\'e} du Quebec {\`a}
Montr{\'e}al},
pages = {171-181},
note = {Proceedings of the 4th Colloquium},
}
@inproceedings{FaReSi92,
author = {Fabret, F. and R{\'e}gnier, M. and Simon, E.},
title = {Optimizing Incremental Computation of Datalog Programs with
Non-Deterministic Semantics},
booktitle = {ICDT'92},
year = {1992},
publisher = {Springer-Verlag},
volume = {646},
series = {Lecture Notes in Computer Science},
pages = {155--170},
note = {Proc. 4-th International Conference on Database Theory,
Berlin, Germany},
}
@inproceedings{Flajolet92,
author = {Flajolet, Philippe},
title = {Analytic Analysis of Algorithms},
booktitle = {Automata, Languages and Programming},
number = {623},
year = {1992},
editor = {W. Kuich},
series = {Lecture Notes in Computer Science},
pages = {186--210},
keywords = {analysis of algorithms, survey},
note = {Proceedings of the 19th International Colloquium, Vienna,
July 1992.},
}
@article{Flajolet92c,
author = {Flajolet, Philippe},
title = {Introduction {\`a} l'analyse d'algorithmes},
journal = {Singularit{\'e}},
number = {5},
year = {1992},
month = {May},
volume = {3},
pages = {5--16},
keywords = {survey, analysis of algorithms, discrete mathematics},
}
@inproceedings{Flajolet92b,
author = {Flajolet, Philippe},
title = {La calculabilit{\'e} et ses limites},
booktitle = {La Science au Pr\'esent},
year = {1992},
publisher = {Les {\'E}ditions de l'Encyclopedia Universalis},
address = {Paris},
pages = {216--218},
}
@article{FlRi92,
author = {Flajolet, Philippe and Richmond, Bruce},
title = {Generalized Digital Trees and Their
Difference--differential equations},
journal = {Random Structures \& Algorithms},
number = {3},
year = {1992},
volume = {3},
pages = {305--320},
keywords = {digital tree, trie, difference equation},
}
@proceedings{FlZi92,
title = {Algorithms Seminar, 1991–1992},
year = {1992},
editor = {Philippe Flajolet and Zimmerman, P.},
volume = {1779},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-1779.html},
}
@article{FlGaTh92,
author = {Flajolet, Philippe and Gardy, Dani{\`e}le and Thimonier,
Lo{\"y}s},
title = {Birthday paradox, coupon collectors, caching algorithms,
and self--organizing search},
journal = {Discrete Applied Mathematics},
year = {1992},
volume = {39},
pages = {207--229},
}
@inproceedings{Golin92a,
author = {Golin, Mordecai},
title = {Dynamic Closest Pairs: A Probabilistic Approach},
booktitle = {Third Scandinavian Workshop on Algorithm Theory (SWAT
'92)},
year = {1992},
}
@inproceedings{Golin92b,
author = {Golin, Mordecai},
title = {Maxima in Convex Regions},
booktitle = {Fourth Annual Symposium on Discrete Algorithms (SODA
'93)},
year = {1992},
}
@inproceedings{GoScSm92,
author = {Golin, Mordecai and Schwarz, Christian and Smid, Michiel},
title = {Further Dynamic Computational Geometry},
booktitle = {The Fourth Canadian Conference on Computational Geometry},
year = {1992},
}
@article{HoFl92,
author = {Hoshi, Mamoru and Flajolet, Philippe},
title = {Page Usage in a Quadtree Index},
journal = {BIT},
year = {1992},
volume = {32},
pages = {384--402},
keywords = {quadtree, paging, index structure, dilogarithm},
}
@inproceedings{JaMu92a,
author = {Jacquet, Ph. and Muhlethaler, P.},
title = {A very simple algorithm for flow control on high speed
networks, via LaPalice queueings},
booktitle = {IEEE Infocom 92},
year = {1992},
month = {May},
address = {Firenze},
}
@article{KeMo92,
author = {Keller, Wilfrid and Morain, Fran\c{c}ois},
title = {The complete factorization of some large {M}ersenne
composites},
journal = {Abstracts of the AMS},
number = {5},
year = {1992},
month = {October},
volume = {13},
pages = {506},
}
@inproceedings{Morain92d,
author = {Morain, Fran\c{c}ois},
title = {Easy numbers for the {E}lliptic {C}urve {P}rimality
{P}roving algorithm},
booktitle = {ISSAC '92},
year = {1992},
editor = {Paul S. Wang},
publisher = {ACM Press},
address = {New York},
pages = {263--268},
note = {Proceedings, July 27--29, Berkeley},
}
@inproceedings{Nicodeme92,
author = {Nicod{\`e}me, Pierre},
title = {Compact Balanced Tries},
booktitle = {Algorithms, Software, Architecture, Information Processing
92},
year = {1992},
editor = {J. van Leeuwen},
publisher = {North-Holland},
volume = {1},
pages = {477--483},
note = {Proceedings of the IFIP 12th World Computer Congress,
Madrid.},
}
@article{Regnier92a,
author = {R{\'e}gnier, M.},
title = {Enumeration of bordered words},
journal = {RAIRO Theoretical Informatics and Applications},
number = {4},
year = {1992},
volume = {26},
pages = {303--317},
}
@inproceedings{Regnier92b,
author = {R{\'e}gnier, M.},
title = {A language approach to string searching evaluation},
booktitle = {CPM'92},
year = {1992},
publisher = {Springer-Verlag},
volume = {644},
series = {Lecture Notes in Computer Science},
pages = {15--26},
note = {Proc. 3-rd Symposium on Combinatorial Pattern Matching,
Tucson, Arizona},
}
@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.},
}
@techreport{Zimmermann92,
author = {P. Zimmermann},
title = {Analysis of functions with a finite number of return
values},
number = {1625},
year = {1992},
month = {February},
institution = {Institut National de Recherche en Informatique et en
Automatique},
keywords = {automatic analysis},
note = {12 pages},
url = {http://www.inria.fr/rrrt/rr-1625.html},
}
@inproceedings{AlRe91b,
author = {L.~Albert and M.~Regnier},
title = {Complexity of recursive production rules execution},
booktitle = {Third International Symposium on Mathematical Fundamentals
of Database and Knowledge Base Systems},
year = {1991},
month = {May},
address = {Goehren, Germany},
}
@inproceedings{AlRe91,
author = {Albert, L. and R{\'e}gnier, M.},
title = {Graph Applications to Recursive Production Rules
Programs},
booktitle = {MFDBS'91, Goehren, Germany},
year = {1991},
}
@article{Crapo91b,
author = {Crapo, Henry},
title = {Invariant-Theoretic Methods in Scene Analysis and
Structural Mechanics},
journal = {Journal of Symbolic Computation},
year = {1991},
volume = {11},
pages = {523-548},
note = {{\em Dans\/} Num\'ero sp\'ecial sur le th\`eme ``Th\'eorie
des Invariants'', MR~90d:~51002},
}
@article{Crapo91,
author = {Crapo, Henry},
title = {On the Generic Rigidity of Structures in the Plane},
journal = {SIAM Journal of Discrete Mathematics},
year = {1991},
note = {Accept\'e pour publication.},
}
@article{FlSo91,
author = {P. Flajolet and M. Soria},
title = {The Cycle Construction},
journal = {SIAM Journal on Discrete Mathematics},
number = {1},
year = {1991},
month = {February},
volume = {4},
pages = {58--60},
}
@inproceedings{FlGoPuRo91,
author = {Flajolet, {\Ph} and Gonnet, Gaston and Puech, Claude and
Robson, J. M.},
title = {The Analysis of Multidimensional Searching in
Quad--Trees},
booktitle = {Proceedings of the Second Annual ACM--SIAM Symposium on
Discrete Algorithms},
year = {1991},
publisher = {SIAM Press},
address = {Philadelphia},
pages = {100-109},
}
@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{JaSz91b,
author = {Jacquet, {\Ph} and Szpankowski, W.},
title = {Analysis of digital tries with Markovian dependency},
journal = {IEEE Transactions on Information Theory},
number = {5},
year = {1991},
month = {September},
volume = {37},
pages = {1470-1475},
}
@inproceedings{Morain91a,
author = {Morain, F.},
title = {Building cyclic elliptic curves modulo large primes},
booktitle = {Advances in Cryptology -- EUROCRYPT '91},
year = {1991},
editor = {{D. Davies}},
publisher = {Springer--Verlag},
volume = {547},
series = {Lecture Notes in Computer Science},
pages = {328--336},
note = {Proceedings of the Workshop on the Theory and Application
of Cryptographic Techniques, Brighton, United Kingdom, April 8--11, 1991},
}
@inproceedings{Morain90a,
author = {Morain, F.},
title = {Distributed Primality Proving and the primality of
$(2^{3539}+1)/3$},
booktitle = {Advances in Cryptology -- EUROCRYPT '90},
year = {1991},
editor = {{I. B. Damg\aa rd}},
publisher = {Springer--Verlag},
pages = {110--123},
note = {Proceedings of the Workshop on the Theory and Application
of Cryptographic Techniques, Aarhus, Denmark, May 21--24, 1990},
}
@article{Morain91b,
author = {Morain, Fran\c{c}ois},
title = {\`A la chasse aux papillons},
journal = {Quadrature},
year = {1991},
month = {Septembre--Octobre},
volume = {10},
pages = {33--34},
}
@phdthesis{Regnier91a,
author = {R{\'e}gnier, M.},
title = {Mots et motifs~: performances asymptotiques},
year = {1991},
address = {Orsay, France},
school = {Univ. Paris-Sud},
}
@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},
}
@phdthesis{Zimmermann91,
author = {Zimmermann, Paul},
title = {S\'eries g\'en\'eratrices et analyse automatique
d'algorithmes},
year = {1991},
address = {Palaiseau, France},
school = {{\'E}cole polytechnique},
}
@inproceedings{ZiZi91,
author = {Zimmermann, P. and Zimmermann, W.},
title = {The {A}utomatic {C}omplexity {A}nalysis of
{D}ivide-and-{C}onquer {A}lgorithms},
booktitle = {Computer and Information Sciences VI},
year = {1991},
publisher = {Elsevier},
pages = {395--404},
note = {Egalement disponible en Rapport de Recherche {\sc Inria}
1149},
}
@phdthesis{Albert90,
author = {L.~Albert},
title = {Quelques analyses de {complexit\'{e}} en moyenne sur les
algorithmes de multi-filtrage, d'unification et de {requ\^{e}te} multiple},
year = {1990},
month = {Octobre},
school = {Universit\'e de Paris--Sud, Orsay},
}
@inproceedings{AlFlMF90,
author = {Allouche, J.--P. and Flajolet, P. and {Mend\`es France},
M.},
title = {Algebraically independent formal power series: a language
theory interpretation},
booktitle = {Analytic Number Theory},
number = {1434},
year = {1990},
editor = {K. Nagasaka and E. Fouvry},
publisher = {Springer Verlag},
series = {Lecture Notes in Mathematics},
pages = {11-18},
note = {Proceedings, Tokyo 1988},
}
@inproceedings{BaRe90,
author = {Baeza-Yates, R. and R{\'e}gnier, M.},
title = {Fast Algorithms for Two Dimensional and Multiple Pattern
Matching},
booktitle = {SWAT'90},
year = {1990},
publisher = {Springer-Verlag},
volume = {447},
series = {Lecture Notes in Computer Science},
pages = {332--347},
note = {Proc. Swedish Workshop on Algorithm Theory, Bergen,
Norway},
}
@inproceedings{BaGoRe90,
author = {Baeza-Yates, R. and Gonnet, G. and R{\'e}gnier, M.},
title = {Analysis of {B}oyer-{M}oore-Type String Searching
Algorithms},
booktitle = {Proc. first SIAM-ACM Symposium on Discrete Algorithms},
year = {1990},
publisher = {SIAM},
pages = {328--343},
note = {SODA '90, San Francisco, January 22--24, 1990},
}
@article{BiCrGuHaRoTr90,
author = {Bideau, Daniel and Crapo, Henry and Guyon, Etienne and
Hansen, Alex and Roux, St/'ephane and Troadec, Jean-Paul},
title = {Non-local and non-linear problems in mechanics of
disordered systems: applications to granular media and rigidity problems},
journal = {Reports on Progress in Physics},
year = {1990},
volume = {53},
pages = {373-419},
}
@article{CoFaJaRo90,
author = {Coffman, E.G. and Fayolle, G. and Jacquet, Ph. and Robert,
Ph.},
title = {Largest-first sequential selection with a sum constraint},
journal = {Operations Research Letter},
year = {1990},
month = {May},
pages = {141--146},
}
@article{Crapo90e,
author = {Crapo, Henry},
title = {On the Generic Rigidity of Structures in the Plane},
journal = {SIAM Journal on Discrete Mathematics},
year = {1990},
}
@article{CrGuHaBiTr90,
author = {Crapo, Henry and Guyon, Etienne and Roux, St\'ephane and
Hansen, Alex and Bideau, Daniel and Troadec, Jean-Paul},
title = {Non-local and non-linear problems in mechanics of
disordered systems: application to granular media and rigidity problems},
journal = {Reports on Progress in Physics},
year = {1990},
volume = {53},
pages = {373-419},
}
@article{Flajolet90a,
author = {Flajolet, P.},
title = {On adaptive sampling},
journal = {Computing},
year = {1990},
volume = {34},
pages = {391--400},
}
@inproceedings{FlOd90a,
author = {Flajolet, P. and Odlyzko, A. M.},
title = {Random Mapping Statistics},
booktitle = {Advances in Cryptology -- EUROCRYPT '89},
year = {1990},
editor = {J-J. Quisquater},
volume = {434},
series = {Lecture Notes in Computer Science},
pages = {329--354},
keywords = {random mapping, survey, combinatorial models,
cryptography},
note = {Proceedings of {Eurocrypt'89}, Houthalen, Belgium, April
10--13, 1989},
}
@article{FlOd90b,
author = {Flajolet, Philippe and Odlyzko, Andrew M.},
title = {Singularity Analysis of Generating Functions},
journal = {SIAM Journal on Discrete Mathematics},
number = {2},
year = {1990},
volume = {3},
pages = {216--240},
keywords = {asymptotics, generating functions},
}
@article{FlSc90,
author = {Flajolet, P. and Schott, R.},
title = {Non--overlapping Partitions, Continued Fractions, {B}essel
Functions and a Divergent Series},
journal = {European Journal of Combinatorics},
year = {1990},
volume = {11},
pages = {421--432},
}
@article{FlSo90,
author = {Philippe Flajolet and Mich{\`e}le Soria},
title = {Gaussian Limiting Distributions for the Number of
Components in Combinatorial Structures},
journal = {Journal of Combinatorial Theory, {\rm {S}eries {A}}},
year = {1990},
volume = {53},
pages = {165--182},
}
@inproceedings{FlSiSt90,
author = {Flajolet, Philippe and Sipala, Paolo and Steyaert,
Jean--Marc},
title = {Analytic Variations on the Common Subexpression Problem},
booktitle = {Automata, Languages, and Programming},
year = {1990},
editor = {M. S. Paterson},
volume = {443},
series = {Lecture Notes in Computer Science},
pages = {220--234},
note = {Proceedings of the 17th ICALP Conference, Warwick, July
1990},
}
@book{FrGaSo90,
author = {Christine Froidevaux and Marie-Claude Gaudel and
Mich{\`e}le Soria},
title = {Types de donn{\'e}es et algorithmes},
year = {1990},
publisher = {Ediscience},
address = {Paris},
}
@article{JaMe90,
author = {Jacquet, Ph. and Merle, E.},
title = {Analysis of a stack algorithm for {CSMA-CD} random length
packet communications},
journal = {IEEE Transactions on Information Theory},
number = {2},
year = {1990},
month = {March},
volume = {36},
pages = {420-425},
}
@inproceedings{Morain89c,
author = {Morain, F.},
title = {Atkin's test: news from the front},
booktitle = {Advances in Cryptology -- EUROCRYPT '89},
year = {1990},
editor = {J.-J. Quisquater},
publisher = {Springer-Verlag},
volume = {434},
series = {Lecture Notes in Computer Science},
pages = {626--635},
note = {Proc. Eurocrypt '89, Houthalen, April 10--13},
}
@article{Morain90f,
author = {Morain, F.},
title = {Comment calculer $a^n$},
journal = {Quadrature},
year = {1990},
month = {November},
volume = {6},
pages = {60--61},
}
@article{Morain90e,
author = {Morain, F.},
title = {Qui factorisera ${F}_9$ ?},
journal = {Quadrature},
year = {1990},
volume = {4},
pages = {31--32},
note = {mai--juin},
}
@phdthesis{Morain90c,
author = {Morain, Fran{\c{c}}ois},
title = {Courbes elliptiques et tests de primalit{\'e}},
year = {1990},
month = {Septembre},
school = {Universit{\'e} Claude Bernard-Lyon {I}},
}
@article{MoOl90,
author = {Morain, F. and Olivos, J.},
title = {Speeding up the computations on an elliptic curve using
addition-subtraction chains},
journal = {RAIRO Theoretical Informatics and Applications},
number = {6},
year = {1990},
volume = {24},
pages = {531--543},
}
@phdthesis{Soria90,
author = {Mich{\`e}le Soria-Cousineau},
title = {M{\'e}thodes d'analyse pour les constructions combinatoires
et les algorithmes},
year = {1990},
school = {Universit\'e de Paris--Sud, Orsay},
}
@inproceedings{VaFl90,
author = {Vall\'ee, Brigitte and Flajolet, Philippe},
title = {Gauss' Reduction Algorithm: An Average Case Analysis},
booktitle = {Proceedings of the 31st Symposium on Foundations of
Computer Science},
year = {1990},
month = {October},
publisher = {IEEE Computer Society Press},
pages = {830--839},
}
@incollection{ViFl90,
author = {Vitter, J. and Flajolet, P.},
title = {Analysis of Algorithms and Data Structures},
booktitle = {Handbook of Theoretical Computer Science},
chapter = {9},
year = {1990},
editor = {J. van Leeuwen},
publisher = {North Holland},
volume = {A: Algorithms and Complexity},
pages = {431--524},
}
@inproceedings{Albert89,
author = {L.~Albert},
title = {Average case complexity analysis of {RETE} pattern match
algorithm and average size of join in Databases},
booktitle = {Foundations of Software Technology and Theoretical Computer
Science},
number = {405},
year = {1989},
month = {{D\'ecembre}},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
pages = {223-241},
note = {Proceedings of $9^{th}$ FFTTCS, Bangalore, India},
}
@article{ChKaSo89,
author = {Christine Choppy and St{\'e}phane Kaplan and Mich{\`e}le
Soria},
title = {Complexity analysis of Term Rewriting Systems},
journal = {Theoretical Computer Science},
year = {1989},
volume = {67},
pages = {261--282},
}
@inproceedings{Crapo89,
author = {Crapo, Henry},
title = {Applications de l'Homologie G{\'e}om{\'e}trique},
booktitle = {Comptes rendus des Journ{\'e}es G{\'e}om{\'e}trie et
Robotique, Toulouse, mai 1988},
year = {1989},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
}
@inproceedings{CuLaFl89,
author = {Cunto, W. and Lau, G. and Flajolet, P.},
title = {Analysis of {$kdt$}--trees: {$kd$}--trees improved by local
reorganisations},
booktitle = {Algorithms and Data Structures},
year = {1989},
editor = {F. Dehne and J-R. Sack and N. Santoro},
volume = {382},
series = {Lecture Notes in Computer Science},
pages = {24--38},
}
@article{FlFr89,
author = {Flajolet, P. and Fran\c{c}on, J.},
title = {Elliptic Functions, Continued Fractions and Doubled
Permutations},
journal = {European Journal of Combinatorics},
year = {1989},
volume = {10},
pages = {235--241},
}
@inproceedings{FlKiTi89,
author = {Flajolet, P. and Kirschenhofer, P. and Tichy, R. F.},
title = {Discrepancy of Sequences in Discrete Spaces},
booktitle = {Irregularities of Partitions},
year = {1989},
editor = {G. Hal{\'a}sz and V. T. S{\'o}s},
publisher = {Springer Verlag},
volume = {8},
series = {Algorithms and Combinatorics},
pages = {61--70},
}
@article{FlKnPi89,
author = {Flajolet, P. and Knuth, D. E. and Pittel, B.},
title = {The first cycles in an evolving graph},
journal = {Discrete Mathematics},
year = {1989},
volume = {75},
pages = {167--215},
}
@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.},
}
@article{GaFlPu89b,
author = {Gardy, D. and Flajolet, P. and Puech, C.},
title = {Average cost of orthogonal range queries in multiattribute
trees},
journal = {Information Systems},
number = {4},
year = {1989},
volume = {14},
pages = {341--350},
}
@inproceedings{GaFlPu89a,
author = {Gardy, D. and Flajolet, P. and Puech, C.},
title = {On the performance of orthogonal range queries in
multiattribute and doubly chained trees},
booktitle = {Algorithms and Data Structures},
year = {1989},
editor = {F. Dehne and J-R. Sack and N. Santoro},
volume = {382},
series = {Lecture Notes in Computer Science},
pages = {218--229},
}
@techreport{HeMoSaSeVuZi89,
author = {Herv\'e, J.-C. and Morain, F. and Salesin, D. and Serpette,
B. and Vuillemin, J. and Zimmermann, P.},
title = {BigNum: A Portable and Efficient Package for Arbitrary
Precision Arithmetic},
number = {1016},
year = {1989},
month = {Avril},
institution = {INRIA},
}
@phdthesis{Jacquet89,
author = {Jacquet, Ph.},
title = {Contribution de l'analyse d'algorithmes {\`a}
l'{\'e}valuation de protocoles de communication},
year = {1989},
month = {Novembre},
school = {Universit{\'e} de Paris--Sud},
}
@article{JaRe89a,
author = {Jacquet, Ph. and R{\'e}gnier, M.},
title = {New Results on the Size of Tries},
journal = {IEEE Transactions on Information Theory},
number = {1},
year = {1989},
volume = {35},
pages = {203--205},
keywords = {size of tries, variance},
}
@article{JaSz89a,
author = {Jacquet, P. and Szpankowski, W.},
title = {Ultimate characterization of the burst response of an
interval searching algorithm: a study of a functional equation},
journal = {SIAM Journal on Computing},
number = {4},
year = {1989},
volume = {18},
pages = {777--791},
}
@inproceedings{LuReSc89,
author = {Luccio, F. and R{\'e}gnier, M. and Schott, R.},
title = {Discs and other related data structures},
booktitle = {Algorithms and data structures},
year = {1989},
publisher = {Springer-Verlag},
volume = {382},
series = {Lecture Notes in Computer Science},
pages = {192--205},
note = {Proceedings of the workshop WADS'89, Ottawa, August 17-19,
1989},
}
@article{Morain89g,
author = {Morain, F.},
title = {On the lcm of the differences of eight primes},
journal = {Mathematics of Computation},
number = {185},
year = {1989},
month = {January},
volume = {52},
pages = {225--229},
}
@inproceedings{Regnier89b,
author = {R{\'e}gnier, M.},
title = {Knuth-{M}orris-{P}ratt algorithm: an Analysis},
booktitle = {MFCS'89},
year = {1989},
publisher = {Springer-Verlag},
volume = {379},
series = {Lecture Notes in Computer Science},
pages = {431--444},
note = {Proceedings Mathematical Foundations for Computer Science
89, Porubka, Poland},
}
@article{Regnier89a,
author = {R{\'e}gnier, M.},
title = {The Limiting Distribution of Quicksort},
journal = {RAIRO Theoretical Informatics and Applications},
number = {3},
year = {1989},
volume = {23},
pages = {335--343},
keywords = {quicksort, limiting distributions, martingales},
}
@inproceedings{ReSi89,
author = {R{\'e}gnier, M. and Simon, E.},
title = {Efficient evaluation of rules in a {DBMS}},
booktitle = {BD3 89},
year = {1989},
publisher = {INRIA},
pages = {131--154},
note = {Proceedings des 6-{\`e}mes Journ{\'e}es Bases de
Donn{\'e}es Avanc{\'e}es},
}
@techreport{Zimmermann89,
author = {Zimmermann, P.},
title = {Alas~: un syst{\`e}me d'analyse alg{\'e}brique},
number = {968},
year = {1989},
month = {January},
institution = {Institut National de Recherche en Informatique et en
Automatique},
note = {119 pages},
}
@techreport{ZiZi89,
author = {Paul Zimmermann and Wolf Zimmermann},
title = {The Automatic Complexity Analysis of
Divide-and-Conquer Algorithms},
year = {1989},
month = {December},
institution = {Institut National de Recherche en Informatique et en
Automatique},
note = {Research Report 1149. 13 pages},
url = {http://www.inria.fr/rrrt/rr-1149.html},
}
@article{Albert88,
author = {Albert, Luc},
title = {Pr{\'e}sentation et {\'e}valuation de la complexit{\'e} en
moyenne d'algorithmes de filtrage dans les moteurs d'inf{\'e}rences ({R}ete
et arbre d'unification)},
journal = {Revue d'Intelligence Artificielle},
year = {1988},
volume = {2},
pages = {7--40},
}
@incollection{AsBoCrWh88,
author = {Ash, Peter and Bolker, Ethan and Crapo, Henry and Whiteley,
Walter},
title = {Convex polyhedra, {D}irichlet tessellations, and spider
webs},
booktitle = {Shaping space (Northampton, Mass., 1984)},
year = {1988},
publisher = {Birkh\"auser Boston},
series = {Design Sci. Collect.},
address = {Boston, MA},
pages = {231--250},
}
@article{ChCr88,
author = {Cheung, Alan and Crapo, Henry},
title = {On relative position in extensions of combinatorial
geometries},
journal = {J. Combin. Theory Ser. B},
number = {2},
year = {1988},
volume = {44},
pages = {201--229},
}
@inproceedings{Crapo88,
author = {Crapo, Henry},
title = {Graphics programming in {P}ost{S}cript},
booktitle = {Proceedings of the Third International Conference on
Engineering Graphics and Descriptive Geometry, Vol.\ 1 (Vienna, 1988)},
year = {1988},
publisher = {Tech. Univ. Vienna},
address = {Vienna},
pages = {79--84},
}
@inproceedings{Crapo88b,
author = {Crapo, Henry},
title = {Towards Nonlinear {C}ayley Factorization},
booktitle = {Symbolic Computations in Geometry},
year = {1988},
publisher = {University of Minnesota},
volume = {389},
series = {preprint series},
address = {Minneapolis},
organization= {Institure for Mathematics and its Applications},
pages = {69--81},
}
@article{CrCh88,
author = {Crapo, Henry and Cheung, Alan},
title = {On Relative Position in Extensions of Combinatorial
Geometries},
journal = {Journal Of Combinatorial Theory B},
year = {1988},
volume = {44},
pages = {201-229},
}
@inproceedings{CrLa88,
author = {Crapo, Henry and Laumond, Jean-Paul},
title = {{H}amilton Cycles in {D}elaunay Complexes},
booktitle = {Comptes rendus des Journ{\'e}es G{\'e}om{\'e}trie et
Robotique, Toulouse, mai 1988},
year = {1988},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
}
@inproceedings{Flajolet88b,
author = {Flajolet, P.},
title = {L'analyse d'algorithmes ou le risque calcul{\'e}},
booktitle = {Journ{\'e}es Scientifiques et Prix U.A.P. 1985,1986,1987},
year = {1988},
publisher = {Conseil Scientifique de l'UAP},
pages = {17--34},
note = {(Text of Prize Award Lecture, 1986)},
}
@incollection{Flajolet88a,
author = {Flajolet, P.},
title = {Mathematical Methods in the Analysis of Algorithms and Data
Structures},
booktitle = {Trends in Theoretical Computer Science},
chapter = {6},
year = {1988},
editor = {Egon B{\"o}rger},
publisher = {Computer Science Press},
address = {Rockville, Maryland},
pages = {225--304},
note = {(Lecture Notes for {\em A Graduate Course in Computation
Theory\/}, Udine, 1984)},
}
@inproceedings{Flajolet88d,
author = {Flajolet, P.},
title = {Random Tree Models in the Analysis of Algorithms},
booktitle = {PERFORMANCE'87},
year = {1988},
editor = {P.-J. Courtois and G. Latouche},
publisher = {Elsevier Science Publishers (North Holland)},
pages = {171--187},
note = {(Invited lecture)},
}
@inproceedings{FlGaTh88,
author = {Flajolet, P. and Gardy, D. and Thimonier, L.},
title = {Probabilistic Languages and Random Allocations},
booktitle = {Automata, Languages and Programming},
year = {1988},
editor = {Timo Lepist{\"o} and Arto Salomaa},
publisher = {Springer-Verlag},
volume = {317},
series = {Lecture Notes in Computer Science},
pages = {239--253},
note = {Proceedings of 15th ICALP Colloquium, Tempere, Finland,
July 1988},
}
@article{FlKiTi88,
author = {Flajolet, P. and Kirschenhofer, P. and Tichy, R. F.},
title = {Deviations from uniformity in random strings},
journal = {Probability Theory and Related Fields},
number = {1},
year = {1988},
volume = {80},
pages = {139--150},
}
@inproceedings{Regnier88a,
author = {R{\'e}gnier, M.},
title = {Trie Hashing Analysis},
booktitle = {DE4},
year = {1988},
editor = {IEEE},
publisher = {Computer Society Press},
volume = {827},
pages = {377--381},
note = {Proceedings of the 4-th International Conference on Data
Engineering, Los Angeles},
}
@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},
}
@techreport{Zimmermann88,
author = {Paul Zimmermann},
title = {Alas : un système d'analyse algébrique},
year = {1988},
institution = {Université de Paris VII},
note = {120 pages. Also available as INRIA Research Report 968
(1989)},
url = {http://www.inria.fr/rrrt/rr-0968.html},
}