On Buffon Machines and Numbers (2009)
Flajolet, Philippe, Pelletier, Maryse, Soria, Michele
Buffon's needle experiment is well-known: take a plane on which parallel lines at unit distance one from the next have been marked, throw a needle of unit length at random, and, finally, declare the...
Lindel\"of Representations and (Non-)Holonomic Sequences (2009)
Flajolet, Philippe, Gerhold, Stefan, Salvy, Bruno
Various sequences that possess explicit analytic expressions can be analysed asymptotically through integral representations due to Lindel\"of, which belong to an attractive but largely forgotten...
Philippe Flajolet, Eric Fusy, Xavier Gourdon, Daniel Panario, Nicolas Pouyanne
Abstract. A “hybrid method”, dedicated to asymptotic coefficient extraction in combinatorial generating functions, is presented, which combines Darboux’s method and singularity analysis theory....
Isomorphism and Symmetries in Random Phylogenetic Trees (2009)
Bona, Miklos, Flajolet, Philippe
The probability that two randomly selected phylogenetic trees of the same size are isomorphic is found to be asymptotic to a decreasing exponential modulated by a polynomial factor. The number of...
The height of random binary unlabelled trees (2008)
Broutin, Nicolas, Flajolet, Philippe
This extended abstract is dedicated to the analysis of the height of non-plane unlabelled rooted binary trees. The height of such a tree chosen uniformly among those of size $n$ is proved to have a...
Extended abstract submitted to ICALP’06. BOLTZMANN SAMPLING OF UNLABELLED STRUCTURES (2008)
Philippe Flajolet, Éric Fusy, Carine Pivoteau
Abstract. Boltzmann models from statistical physics combined with methods from analytic combinatorics give rise to efficient algorithms for the random generation of unlabelled objects. The resulting...
Eric Van, Fossen Conrad, Philippe Flajolet
Kindly dedicated to Gérard · · ·Xavier Viennot on the occasion of his sixtieth birthday. Abstract. Elliptic functions considered by Dixon in the nineteenth century and related to Fermat’s...
SINGULARITY ANALYSIS AND ASYMPTOTICS OF BERNOULLI SUMS (2008)
Projet Algo, Philippe Flajolet
Abstract: The asymptotic analysis of a class of binomial sums that arise in information theory can be performed in a simple way by means of singularity analysis of generating functions. The method...
Proceedings in Lecture Notes in Computer Science. THE UBIQUITOUS DIGITAL TREE (2008)
Abstract. The digital tree also known as trie made its first appearance as a general-purpose data structure in the late 1950’s. Its principle is a recursive partitioning based on successive bits or...
Philippe Flajolet, Wojciech Szpankowski, Brigitte Vallée
Abstract. We consider the sequence comparison problem, also known as “hidden ” pattern problem, where one searches for a given subsequence in a text (rather than a string understood as a sequence...
INFORMATION SCIENCES 38,121-146 (1986) 121 The Analysis of Simple List Structures (2008)
Philippe Flajolet, Claude Puech
We present an analysis of simple lists, either sorted or unsorted, under the set of all their possible histories (i.e. evolutions considered up to order isomorphism) of length n. Using the theory of...
THE FERMAT CUBIC, ELLIPTIC FUNCTIONS, CONTINUED FRACTIONS, AND A COMBINATORIAL EXCURSION (2008)
Eric Van, Fossen Conrad, Philippe Flajolet
Kindly dedicated to Gérard · · ·Xavier Viennot on the occasion of his sixtieth birthday. Abstract. Elliptic functions considered by Dixon in the nineteenth century and related to Fermat’s...
Philippe Flajolet, Inria Rocquencourt
Abstract. We present three classes of random tree models tbat occur in the average case analysis of a variety of computer algorithms including symbolic manipulation algorithms, rompilling, comparison...
Philippe Flajolet, Rene Scho-it
The counting sequence of a special class of set partitions leads to special numbers called Bessel numbers. The corresponding ordinary generating function has a simple continued fraction expansion...
On Differences of Zeta Values (2008)
Philippe Flajolet, Linas Vepstas
ABSTRACT. Finite differences of values of the Riemann zeta function at the integers are explored. Such quantities, which occur as coefficients in Newton series representations, have surfaced in works...
Philippe Flajolet, Inria Rocquencourt
proposes a natural combinatorial setting for results stated by P'olya regarding the enumeration of `diagonally convex lattice polygons ' also known as parallelogram polyominoes, staircase...
Continued Fractions, Comparison Algorithms, and Fine Structure Constants (2007)
Philippe Flajolet, Brigitte Vallée, To Jonathan Borwein
. There are known algorithms based on continued fractions for comparing fractions and for determining the sign of 2 \Theta 2 determinants. The analysis of such extremely simple algorithms leads to an...
Non Overlapping Partitions, Continued Fractions, Bessel Functions, and a Divergent Series (2007)
Philippe Flajolet, René Schott
. The counting sequence of a special class of set partitions leads to special numbers called Bessel numbers. The corresponding ordinary generating function has a simple continued fraction expansion...
Philippe Flajolet, Fabrice Guillemin, Fabrice Guillemin
: Classic works of Karlin-McGregor and Jones-Magnus have established a general correspondence between continuous-time birth-and-death processes and continued fractions of the Stieltjes-Jacobi type...
Airy phenomena and analytic combinatorics of connected graphs (2007)
Philippe Flajolet, Bruno Salvy, Gilles Schaeffer
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...
(1), WOJCIECH SZPANKOWSKI (2007)
Abstract. We consider the sequence comparison problem, also known as \hidden " pattern problem, where one searches for a given subsequence in a text (rather than a string understood as a...
Philippe Flajolet, G. Nigel Martin
This paper introduces a class of probabilistic counting lgorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large file stored on disk) in...
Singularity Analysis, Hadamard Products, and Tree Recurrences (2007)
James Allen Fill, Philippe Flajolet, James Allen, Nevin Kapur
We present a toolbox for extracting asymptotic information on the coefficients of combinatorial generating functions. This toolbox notably includes a treatment of the effect of Hadamard products on...
Analytic Combinatorics --- Complex Asymptotics (2007)
Chapters Iv, Philippe Flajolet, Robert Sedgewick
This booklet develops in about 240 pages the basics of asymptotic enumeration through an approach that revolves around generating functions and complex analysis. Major properties of generating...
Fast Computation with Two Algebraic Numbers (2007)
Alin Bostan, Philippe Flajolet, Bruno Salvy, Eric Schost
We propose fast algorithms for computing composed products and composed sums, as well as diamond products of univariate polynomials. These operations correspond to special resultants, that we compute...
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (2007)
Flajolet, Philippe, Fusy, Eric, Gandouet, Olivier, Meunier, Frédéric
This extended abstract describes and analyses a near-optimal probabilistic algorithm, HYPERLOGLOG , dedicated to estimating the number of distinct elements (the cardinality) of very large data...
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (2007)
Flajolet, Philippe, Fusy, Eric, Gandouet, Olivier, Meunier, Frédéric
This extended abstract describes and analyses a near-optimal probabilistic algorithm, HYPERLOGLOG , dedicated to estimating the number of distinct elements (the cardinality) of very large data...
On Differences of Zeta Values (2006)
Flajolet, Philippe, Vepstas, Linas
Finite differences of values of the Riemann zeta function at the integers are explored. Such quantities, which occur as coefficients in Newton series representations, have surfaced in works of...
A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics (2006)
Flajolet, Philippe, Fusy, Eric, Gourdon, Xavier, Panario, Daniel, Pouyanne, Nicolas
A ``hybrid method'', dedicated to asymptotic coefficient extraction in combinatorial generating functions, is presented, which combines Darboux's method and singularity analysis theory. This hybrid...
The scientific works of Rainer Kemp (1949–2004) (2006)
Philippe Flajolet, Markus Nebel, Helmut Prodinger
This short note presents a summary of the scientific contributions of Rainer Kemp (1949–2004) in the area of discrete mathematics, combinatorial enumeration, and analysis of algorithms. A complete...
Fast Computation of Special Resultants (2005)
Bostan, Alin, Flajolet, Philippe, Salvy, Bruno, Schost, Éric
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,...
Fast Computation of Special Resultants (2005)
Bostan, Alin, Flajolet, Philippe, Salvy, Bruno, Schost, Éric
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,...
Fast Computation of Special Resultants (2005)
Bostan, Alin, Flajolet, Philippe, Salvy, Bruno, Schost, Éric
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,...
The Fermat cubic, elliptic functions, continued fractions, and a combinatorial excursion (2005)
Conrad, Eric Van Fossen, Flajolet, Philippe
Elliptic functions considered by Dixon in the nineteenth century and related to Fermat's cubic, $x^3+y^3=1$, lead to a new set of continued fraction expansions with sextic numerators and cubic...
Flajolet, Philippe, Gabarró, Joaquim, Pekari, Helmut
This article describes a purely analytic approach to urn models of the generalized or extended Pólya–Eggenberger type, in the case of two types of balls and constant “balance,” that is,...
On the non-holonomic character of logarithms, powers, and the n-th prime function (2005)
Flajolet, Philippe, Gerhold, Stefan, Salvy, Bruno
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...
Fast Computation of Special Resultants (2005)
Bostan, Alin, Flajolet, Philippe, Salvy, Bruno, Schost, Éric
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,...
Fast Computation of Special Resultants (2005)
Bostan, Alin, Flajolet, Philippe, Salvy, Bruno, Schost, Éric
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,...
On the non-holonomic character of logarithms, powers, and the nth prime function (2005)
Philippe Flajolet, Stefan Gerhold, Bruno Salvy
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...
Generating functions for generating trees (2004)
Banderier, Cyril, Flajolet, Philippe, Gardy, Daniele, Bousquet-Melou, Mireille, Denise, Alain, Gouyou-Beauchamps, Dominique
Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the...
Flajolet, Philippe, Gabarro, Joaquim, Pekari, Helmut
This article describes a purely analytic approach to urn models of the generalized or extended P\'olya-Eggenberger type, in the case of two types of balls and constant ``balance,'' that is, constant...
Boltzmann samplers for the random generation of combinatorial structures (2004)
Philippe Duchon, Philippe Flajolet, Guy Louchard, Gilles Schaeffer
Abstract. This article proposes a surprisingly simple framework for the random generation of combinatorial congurations based on what we call Boltzmann models. The idea is to perform random...
Airy Phenomena and Analytic Combinatorics of Connected Graphs (2004)
Philippe Flajolet, Bruno Salvy, Gilles Schaeffer
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...
Singularity analysis, Hadamard products, and tree recurrences (2003)
Fill, James Allen, Flajolet, Philippe, Kapur, Nevin
We present a toolbox for extracting asymptotic information on the coefficients of combinatorial generating functions. This toolbox notably includes a treatment of the effect of Hadamard products on...
Combinatorial enumeration leads to counting generating functions presenting a wide variety of analytic types. Properties of generating functions at singularities encode valuable information regarding...
LogLog Counting of Large Cardinalities (2003)
Marianne Durand, Philippe Flajolet
Abstract. Using an auxiliary memory smaller than the size of this abstract, the LogLog algorithm makes it possible to estimate in a single pass and within a few percents the number of dierent words...
Philippe Flajolet, Joaquim Gabarr O, Helmut Pekari
Abstract. This article describes a purely analytic approach to urn models of the generalized or extended Polya-Eggenberger type, in the case of two types of balls and constant \balance",...
Fast Computation with Two Algebraic Numbers (2003)
Alin Bostan, Philippe Flajolet, Bruno Salvy, Eric Schost
We propose fast algorithms for computing composed products and composed sums, as well as diamond products of univariate polynomials. These operations correspond to special resultants, that we compute...
Singularity Analysis, Hadamard Products, and Tree Recurrences (2003)
James Allen Fill, Philippe Flajolet, Nevin Kapur
We present a toolbox for extracting asymptotic information on the coecients of combinatorial generating functions. This toolbox notably includes a treatment of the eect of Hadamard products on...
Philippe Flajolet, Joaquim Gabarró, Helmut Pekari
This article describes a purely analytic approach to urn models of the generalized or extended Pólya–Eggenberger type, in the case of two types of balls and constant “balance, ” that is,...
Fast Computation with Two Algebraic Numbers (2002)
Bostan, Alin, Flajolet, Philippe, Salvy, Bruno, Schost, Éric
We propose fast algorithms for computing composed multiplications and composed sums, as well as «diamond products» of univariate polynomials.
Airy Phenomena and Analytic Combinatorics of Connected Graphs (2002)
Flajolet, Philippe, Salvy, Bruno, Schaeffer, Gilles
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...
Generating functions for generating trees (2002)
Banderier, Cyril, Flajolet, Philippe, Gardy, Danièle, Bousquet-Mélou, Mireille, Denise, Alain, Gouyou-Beauchamps, Dominique
Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the...
Generating Functions for Generating Trees (2002)
Banderier,Cyril, Bousquet-Mélou,Mireille, Denise,Alain, Flajolet,Philippe, Gardy,Danièle, Gouyou-Beauchamps,Dominique
Fast Computation with Two Algebraic Numbers (2002)
Bostan, Alin, Flajolet, Philippe, Salvy, Bruno, Schost, Éric
We propose fast algorithms for computing composed multiplications and composed sums, as well as «diamond products» of univariate polynomials.
Airy Phenomena and Analytic Combinatorics of Connected Graphs (2002)
Flajolet, Philippe, Salvy, Bruno, Schaeffer, Gilles
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...
Fast Computation with Two Algebraic Numbers (2002)
Bostan, Alin, Flajolet, Philippe, Salvy, Bruno, Schost, Éric
We propose fast algorithms for computing composed multiplications and composed sums, as well as «diamond products» of univariate polynomials.
Airy Phenomena and Analytic Combinatorics of Connected Graphs (2002)
Flajolet, Philippe, Salvy, Bruno, Schaeffer, Gilles
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...
Generating functions for generating trees (2002)
Banderier, Cyril, Flajolet, Philippe, Gardy, Danièle, Bousquet-Mélou, Mireille, Denise, Alain, Gouyou-Beauchamps, Dominique
Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the...
Generating functions for generating trees (2002)
Banderier, Cyril, Flajolet, Philippe, Gardy, Danièle, Bousquet-Mélou, Mireille, Denise, Alain, Gouyou-Beauchamps, Dominique
Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the...
Generating Functions for Generating Trees (2002)
Banderier, Cyril, Bousquet-Mélou, Mireille, Denise, Alain, Flajolet, Philippe, Gardy, Danièle, Gouyou-Beauchamps, Dominique
Generating functions for generating trees (2002)
Banderier, Cyril, Flajolet, Philippe, Gardy, Danièle, Bousquet-Mélou, Mireille, Denise, Alain, Gouyou-Beauchamps, Dominique
Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the...
Philippe Flajolet, Robert Sedgewick
This booklet develops in nearly 200 pages the basics of combinatorial enumeration through an approach that revolves around generating functions. The major objects of interest here are words, trees,...
Fast computation with two algebraic numbers (2002)
Alin Bostan, Philippe Flajolet, Bruno Salvy, Éric Schost
We propose fast algorithms for computing composed products and composed sums, as well as diamond products of univariate polynomials. These operations correspond to special resultants, that we compute...
Philippe Flajolet, Robert Sedgewick, Inria Rocquencourt
This booklet develops in nearly 200 pages the basics of combinatorial enumeration through an approach that revolves around generating functions. The major objects of interest here are words, trees,...
Philippe Flajolet, Robert Sedgewick
This booklet develops in nearly 200 pages the basics of combinatorial enumeration through an approach that revolves around generating functions. The major objects of interest here are words, trees,...
Thème Génie Logiciel, Projet Algorithmes, Alin Bostan, Alin Bostan, Alin Bostan, Philippe Flajolet, ...
apport
Basic Analytic Combinatorics of Directed Lattice Paths (2002)
Cyril Banderier, Philippe Flajolet
Abstract. This paper develops a unied enumerative and asymptotic theory of directed 2-dimensional lattice paths in half-planes and quarter-planes. The lattice paths are specied by a nite set of rules...
Basic Analytic Combinatorics of Directed Lattice Paths (2002)
Cyril Banderier, Philippe Flajolet
Abstract. Lattice paths intervene in many areas of mathematics and computer science. They play a r^ole, for instance, in probability theory (sums of discrete random variables), statistics...
Random Sampling from Boltzmann Principles (2002)
Philippe Duchon, Philippe Flajolet, Guy Louchard, Gilles Schaeffer
This note proposes a new framework for random generation of combinatorial configurations based on what we call Boltzmann models. The idea is to perform random generation of possibly complex...
Symbolic Enumerative Combinatorics and Complex Asymptotic Analysis (2002)
Philippe Flajolet, Projet Algo, Inria Rocquencourt (france, Summary Yvan, Le Borgne
Complex analysis is a fruitful source of asymptotic estimates in enumerative combinatorics.
Philippe Flajolet, Robert Sedgewick
This booklet develops in nearly 200 pages the basics of combinatorial enumeration through an approach that revolves around generating functions. The major objects of interest here are words, trees,...
Philippe Flajolet, Wojciech Szpankowski, Brigitte Vallée
We consider the sequence comparison problem, also known as "hidden" pattern problem, where one searches for a given subsequence in a text (rather than a string understood as a sequence of...
Analytic combinatorics : functional equations, rational and algebraic functions (2001)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods and models in analytic combinatorics. Here, we detail the case of rational and algebraic functions and...
Analytic combinatorics : functional equations, rational and algebraic functions (2001)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods and models in analytic combinatorics. Here, we detail the case of rational and algebraic functions and...
Analytic combinatorics : functional equations, rational and algebraic functions (2001)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods and models in analytic combinatorics. Here, we detail the case of rational and algebraic functions and...
Random maps, coalescing saddles, singularity analysis, and Airy phenomena (2001)
Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michele Soria
A considerable number of asymptotic distributions arising in random combinatorics and analysis of algorithms are of the exponential-quadratic type, that is, Gaussian. We exhibit a class of...
Cyril Banderier, Philippe Flajolet, Gilles Schaeffer
Abstract. A considerable number of asymptotic distributions arising in random combinatorics and analysis of algorithms are of the exponential-quadratic type, that is, Gaussian. We exhibit a class of...
Cyril Banderier, Philippe Flajolet, Gilles Schaeffer
Abstract. A considerable number of asymptotic distributions arising in random combinatorics and analysis of algorithms are of the exponential-quadratic type, that is, Gaussian. We exhibit a class of...
Basic Analytic Combinatorics of Directed Lattice Paths (2001)
Cyril Banderier, Philippe Flajolet
This paper develops a uni ed enumerative and asymptotic theory of directed 2-dimensional lattice paths in half-planes and quarter-planes.
Continued Fractions, Comparison Algorithms, and Fine Structure Constants (2000)
Flajolet, Philippe, Vallée, Brigitte
There are known algorithms based on continued fractions for comparing fractions and for determining the sign of 2x2 determinants. The analysis of such extremely simple algorithms leads to an...
On the Robustness of Interconnections in Random Graphs: A Symbolic Approach (2000)
Flajolet, Philippe, Hatzis, Kostas, Nikoletseas, Sotiris, Spirakis, Paul
Graphs are models of communication networks. This paper applies symbolic combinatorial techniques in order to characterize the interplay between two parameters of a random graph, namely its density...
Flajolet, Philippe, Guillemin, Fabrice
Classic works of Karlin and McGregor and Jones and Magnus have established a general correspondence between continuous-time birth-and-death processes and continued fractions of the Stieltjes-Jacobi...
Analytic Combinatorics of Chord Diagrams (2000)
In this paper we study the enumeration of diagrams of n chords joining 2n points on a circle in disjoint pairs. We establish limit laws for the following three parameters: number of components, size...
Continued Fractions, Comparison Algorithms, and Fine Structure Constants (2000)
Flajolet, Philippe, Vallée, Brigitte
There are known algorithms based on continued fractions for comparing fractions and for determining the sign of 2x2 determinants. The analysis of such extremely simple algorithms leads to an...
On the Robustness of Interconnections in Random Graphs: A Symbolic Approach (2000)
Flajolet, Philippe, Hatzis, Kostas, Nikoletseas, Sotiris, Spirakis, Paul
Graphs are models of communication networks. This paper applies symbolic combinatorial techniques in order to characterize the interplay between two parameters of a random graph, namely its density...
Analytic Combinatorics of Chord Diagrams (2000)
In this paper we study the enumeration of diagrams of n chords joining 2n points on a circle in disjoint pairs. We establish limit laws for the following three parameters: number of components, size...
Continued Fractions, Comparison Algorithms, and Fine Structure Constants (2000)
Flajolet, Philippe, Vallée, Brigitte
There are known algorithms based on continued fractions for comparing fractions and for determining the sign of 2x2 determinants. The analysis of such extremely simple algorithms leads to an...
On the Robustness of Interconnections in Random Graphs: A Symbolic Approach (2000)
Flajolet, Philippe, Hatzis, Kostas, Nikoletseas, Sotiris, Spirakis, Paul
Graphs are models of communication networks. This paper applies symbolic combinatorial techniques in order to characterize the interplay between two parameters of a random graph, namely its density...
Analytic Combinatorics of Chord Diagrams (2000)
In this paper we study the enumeration of diagrams of n chords joining 2n points on a circle in disjoint pairs. We establish limit laws for the following three parameters: number of components, size...
Planar Maps and Airy Phenomena (2000)
Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michele Soria
. A considerable number of asymptotic distributions arising in random combinatorics and analysis of algorithms are of the exponentialquadratic type (e x 2 ), that is, Gaussian. We exhibit here a new...
Analytic Variations on the Airy Distribution (2000)
Philippe Flajolet, Guy Louchard
. The Airy distribution (of the "area" type) occurs as limit distribution of cumulative parameters in a number of combinatorial structures like trees, graphs, walks, parking sequences,...
Analytic Combinatorics of Chord Diagrams (2000)
Philippe Flajolet, Inria Rocquencourt, Marc Noy, Marc Noy, Marc Noy
In this paper we study the enumeration of diagrams of n chords joining 2n points on a circle in disjoint pairs. We establish limit laws for the following three parameters: number of components, size...
On Generating Functions of Generating Trees (1999)
Banderier, Cyril, Bousquet-Mélou, Mireille, Denise, Alain, Flajolet, Philippe, Gardy, Danièle, Gouyou-Beauchamps, Dominique
Generating trees describe conveniently certain families of combinatorial objects: each node of the tree corresponds to an object, and the branch leading to the node encodes the choices made in the...
Flajolet, Philippe, Guillemin, Fabrice
Classic works of Karlin-McGregor and Jones-Magnus have established a general correspondence between continuous-time birth-and-death processes and continued fractions of the Stieltjes-Jacobi type...
Dynamical Sources in Information Theory : A General Analysis of Trie Structures (1999)
Clément, Julien, Flajolet, Philippe, Vallée, Brigitte
Digital trees, also known as tries, are a general purpose flexible data structure that implements dictionaries built on sets of words. An analysis is given of three major representations of tries in...
Nicodème, Pierre, Salvy, Bruno, Flajolet, Philippe
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...
On Generating Functions of Generating Trees (1999)
Banderier, Cyril, Bousquet-Mélou, Mireille, Denise, Alain, Flajolet, Philippe, Gardy, Danièle, Gouyou-Beauchamps, Dominique
Generating trees describe conveniently certain families of combinatorial objects: each node of the tree corresponds to an object, and the branch leading to the node encodes the choices made in the...
Flajolet, Philippe, Guillemin, Fabrice
Classic works of Karlin-McGregor and Jones-Magnus have established a general correspondence between continuous-time birth-and-death processes and continued fractions of the Stieltjes-Jacobi type...
Dynamical Sources in Information Theory : A General Analysis of Trie Structures (1999)
Clément, Julien, Flajolet, Philippe, Vallée, Brigitte
Digital trees, also known as tries, are a general purpose flexible data structure that implements dictionaries built on sets of words. An analysis is given of three major representations of tries in...
Nicodème, Pierre, Salvy, Bruno, Flajolet, Philippe
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...
On Generating Functions of Generating Trees (1999)
Banderier, Cyril, Bousquet-Mélou, Mireille, Denise, Alain, Flajolet, Philippe, Gardy, Danièle, Gouyou-Beauchamps, Dominique
Generating trees describe conveniently certain families of combinatorial objects: each node of the tree corresponds to an object, and the branch leading to the node encodes the choices made in the...
Flajolet, Philippe, Guillemin, Fabrice
Classic works of Karlin-McGregor and Jones-Magnus have established a general correspondence between continuous-time birth-and-death processes and continued fractions of the Stieltjes-Jacobi type...
Dynamical Sources in Information Theory : A General Analysis of Trie Structures (1999)
Clément, Julien, Flajolet, Philippe, Vallée, Brigitte
Digital trees, also known as tries, are a general purpose flexible data structure that implements dictionaries built on sets of words. An analysis is given of three major representations of tries in...
Nicodème, Pierre, Salvy, Bruno, Flajolet, Philippe
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...
Generating Functions for Generating Trees (1999)
Cyril Banderier, Mireille Bousquet-Mélou, Cyril B, Philippe Flajolet, Dani Ele Gardy, ...
Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the...
Generating Functions for Generating Trees (1999)
Cyril Banderier, Mireille Bousquet-Mélou, Cyril B, Philippe Flajolet, Danièle Gardy, ...
Certain families of combinatorial objects admit recursive descriptions in terms of generating trees: each node of the tree corresponds to an object, and the branch leading to the node encodes the...
Pierre Nicodème, Pierre Nicodeme, Philippe Flajolet, Bruno Salvy, Bruno Salvy, Projet Algo
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...
Philippe Flajolet, Fabrice Guillemin, Fabrice Guillemin, Projet Algo
: Classic works of Karlin-McGregor and Jones-Magnus have established a general correspondence between continuous-time birth-and-death processes and continued fractions of the Stieltjes-Jacobi type...
On Generating Functions of Generating Trees (1999)
Cyril Banderier, Mireille Bousquet-Mélou, Cyril B, Philippe Flajolet, Danièle Gardy, Dominique Gouyou-Beauchamps, ...
Generating trees are infinite trees that constitute a way to describe many classical combinatorial objects by encoding the choices leading to objects of a given size into paths in a tree of...
On Generating Functions of Generating Trees (1999)
Cyril Banderier, Mireille Bousquet-Mélou, Cyril B, Philippe Flajolet, Danièle Gardy, Cyril B, ...
Generating trees describe conveniently certain families of combinatorial objects: each node of the tree corresponds to an object, and the branch leading to the node encodes the choices made in the...
Dynamical Sources in Information Theory: A General Analysis of Trie Structures (1999)
Julien Clément, Philippe Flajolet, Brigitte Vallée, Projet Algo
Digital trees, also known as tries, are a general purpose flexible data structure that implements dictionaries built on sets of words. An analysis is given of three major representations of tries in...
Random Triangulations and Trees (1999)
Luc Devroye, Philippe Flajolet, Ferran Hurtado, Marc Noy, William Steiger, Politecnica Catalunya, ...
gulation ø of K, let d i denote the degree of vertex v i , the number of (the n \Gamma 3 internal) diagonals of ø that are incident with v i . We study \Delta n (ø) = max(d i ; i = 0; : : : ; n...
Philippe Flajolet, Fabrice Guillemin, Fabrice Guillemin
: Classic works of Karlin-McGregor and Jones-Magnus have established a general correspondence between continuous-time birth-and-death processes and continued fractions of the Stieltjes-Jacobi type...
Pierre Nicodème, Pierre Nicod Eme, Philippe Flajolet, Bruno Salvy, Bruno Salvy
: 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...
Dynamical Sources in Information Theory: A General Analysis of Trie Structures (1999)
Julien Clément, Philippe Flajolet, Brigitte Vallée
Digital trees, also known as tries, are a general purpose AEexible data structure that implements dictionaries built on sets of words. An analysis is given of three major representations of tries in...
Analytic Variations on Redundancy Rates of Renewal Processes (1998)
Flajolet, Philippe, Szpankowski, Wojtek
Csiszár and Shields have recently proved that the minimax redundancy for a class of renewal processes is $\Theta(\sqrt{n})$ where $n$ is the block length. This interesting result provides a first...
Analytic Variations on Bucket Selection and Sorting (1998)
Mahmoud, Hosam, Flajolet, Philippe, Jacquet, Philippe, Régnier, Mireille
We provide complete average-case as well as probabilistic analysis of the cost of bucket selection and sorting algorithms. Two variations of bucketing (and flavors therein) are considered:...
Singularity Analysis and Asymptotics of Bernoulli Sums (1998)
The asymptotic analysis of a class of binomial sums that arise in information theory can be performed in a simple way by means of singularity analysis of generating functions. The method developed...
The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields (1998)
Flajolet, Philippe, Gourdon, Xavier, Panario, Daniel
A unified treatment of parameters relevant to factoring polynomials over finite fields is given. The framework is based on generating functions for describing parameters of interest and on...
On Stirling Numbers for Complex Argument and Hankel Contours (1998)
Flajolet, Philippe, Prodinger, Helmut
Cauchy coefficient integrals and Hankel contours provide a natural generalization of Stirling numbers for unrestricted complex values of their arguments. Many classical identities survive such an...
Euler sums and contour integral representations (1998)
Flajolet, Philippe, Salvy, Bruno
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...
Analytic Variations on Redundancy Rates of Renewal Processes (1998)
Flajolet, Philippe, Szpankowski, Wojtek
Csiszár and Shields have recently proved that the minimax redundancy for a class of renewal processes is $\Theta(\sqrt{n})$ where $n$ is the block length. This interesting result provides a first...
Analytic Variations on Bucket Selection and Sorting (1998)
Mahmoud, Hosam, Flajolet, Philippe, Jacquet, Philippe, Regnier, Mireille
We provide complete average-case as well as probabilistic analysis of the cost of bucket selection and sorting algorithms. Two variations of bucketing (and flavors there in) are considered:...
Singularity Analysis and Asymptotics of Bernoulli Sums (1998)
The asymptotic analysis of a class of binomial sums that arise in information theory can be performed in a simple way by means of singularity analysis of generating functions. The method developed...
The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields (1998)
Flajolet, Philippe, Gourdon, Xavier, Panario, Daniel
A unified treatment of parameters relevant to factoring polynomials over finite fields is given. The framework is based on generating functions for describing parameters of interest and on...
On Stirling Numbers for Complex Argument and Hankel Contours (1998)
Flajolet, Philippe, Prodinger, Helmut
Cauchy coefficient integrals and Hankel contours provide a natural generalization of Stirling numbers for unrestricted complex values of their arguments. Many classical identities survive such an...
Analytic Variations on Redundancy Rates of Renewal Processes (1998)
Flajolet, Philippe, Szpankowski, Wojtek
Csiszár and Shields have recently proved that the minimax redundancy for a class of renewal processes is $\Theta(\sqrt{n})$ where $n$ is the block length. This interesting result provides a first...
Analytic Variations on Bucket Selection and Sorting (1998)
Mahmoud, Hosam, Flajolet, Philippe, Jacquet, Philippe, Regnier, Mireille
We provide complete average-case as well as probabilistic analysis of the cost of bucket selection and sorting algorithms. Two variations of bucketing (and flavors there in) are considered:...
Singularity Analysis and Asymptotics of Bernoulli Sums (1998)
The asymptotic analysis of a class of binomial sums that arise in information theory can be performed in a simple way by means of singularity analysis of generating functions. The method developed...
The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields (1998)
Flajolet, Philippe, Gourdon, Xavier, Panario, Daniel
A unified treatment of parameters relevant to factoring polynomials over finite fields is given. The framework is based on generating functions for describing parameters of interest and on...
On Stirling Numbers for Complex Argument and Hankel Contours (1998)
Flajolet, Philippe, Prodinger, Helmut
Cauchy coefficient integrals and Hankel contours provide a natural generalization of Stirling numbers for unrestricted complex values of their arguments. Many classical identities survive such an...
On the analysis of linear probing hashing (1998)
Philippe Flajolet, Patricio V. Poblete, Alfredo Viola
Dedicated to Don Knuth on the occasion of the 35th anniversary of his first analysis of an algorithm in 1962--1963. Abstract. This paper presents moment analyses and characterizations of limit...
Euler Sums and Contour Integral Representations (1998)
Philippe Flajolet, Bruno Salvy
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...
On Stirling numbers for complex arguments and Hankel contours (1998)
Philippe Flajolet, Helmut Prodinger, Helmut Prodinger, Helmut Prodinger
: Cauchy coefficient integrals and Hankel contours provide a natural generalization of Stirling numbers for unrestricted complex values of their arguments. Many classical identities survive such an...
On the Analysis of Linear Probing Hashing (1998)
Philippe Flajolet, Projet Algorithmes, Patricio Poblete, Patricio Poblete, Alfredo Viola, Alfredo Viola
: This paper presents moment analyses and characterizations of limit distributions for the construction cost of hash table under the linear probing strategy. Two models are considered, that of full...
Singularity analysis and asymptotics of Bernoulli sums (1998)
: The asymptotic analysis of a class of binomial sums that arise in information theory can be performed in a simple way by means of singularity analysis of generating functions. The method developed...
Analytic Variations on Redundancy Rates of Renewal Processes (1998)
Philippe Flajolet, Projet Algorithmes, Wojtek Szpankowski, Wojtek Szpankowski
Csiszár and Shields have recently proved that the minimax redundancy for a class of renewal processes is \Theta( p n) where n is the block length. This interesting result provides a first...
On Stirling numbers for complex arguments and Hankel contours (1998)
Philippe Flajolet, Helmut Prodinger, Helmut Prodinger, Helmut Prodinger
: Cauchy coefficient integrals and Hankel contours provide a natural generalization of Stirling numbers for unrestricted complex values of their arguments. Many classical identities survive such an...
Analytic Variations on Bucket Selection and Sorting (1998)
Hosam Mahmoud, Philippe Flajolet, Philippe Jacquet, Mireille Régnier, Hosam Mahmoud
: We provide complete average-case as well as probabilistic analysis of the cost of bucket selection and sorting algorithms. Two variations of bucketing (and flavors therein) are considered:...
Analytic Variations on Redundancy Rates of Renewal Processes (1998)
Philippe Flajolet, Wojciech Szpankowski, Senior Member
Csisz'ar and Shields have recently proved that the minimax redundancy for a class of renewal processes is \Theta( p n) where n is the block length. This interesting result provides a first...
The Complete Analysis of a Polynomial Factorization Algorithm Over Finite Fields (1998)
Philippe Flajolet, Xavier Gourdon, Xavier Gourdon, Xavier Gourdon, Daniel Panario, Daniel Panario, ...
: A unified treatment of parameters relevant to factoring polynomials over finite fields is given. The framework is based on generating functions for describing parameters of interest and on...
Singularity analysis and asymptotics of Bernoulli sums (1998)
: The asymptotic analysis of a class of binomial sums that arise in information theory can be performed in a simple way by means of singularity analysis of generating functions. The method developed...
Analytic Variations on Redundancy Rates of Renewal Processes (1998)
Philippe Flajolet, Projet Algorithmes, Wojtek Szpankowski, Wojtek Szpankowski
: Csisz'ar and Shields have recently proved that the minimax redundancy for a class of renewal processes is \Theta( p n) where n is the block length. This interesting result provides a first...
The Analysis of Hybrid Trie Structures (1997)
Clément, Julien, Flajolet, Philippe, Vallée, Brigitte
This paper provides a detailed analysis of various implementations of digital tries, including the «ternary search tries» of Bentley and Sedgewick. The methods employed combine symbolic uses of...
On the Analysis of Linear Probing Hashing (1997)
Flajolet, Philippe, Poblete, Patricio, Viola, Alfredo
This paper presents moment analyses and characterizations of limit distributions for the construction cost of hash table under the linear probing strategy. Two models are considered, that of full...
The SIGSAM Challenges: Symbolic Asymptotics in Practice (1997)
Flajolet, Philippe, Salvy, Bruno
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 {\em Sigsam Bulletin}. In all cases, the answer to a...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
Coffman, E. G., Flajolet, Philippe, Flatto, Leopold, Hofri, Micha
We consider a symmetric random walk of length $n$ that starts at the origin and takes steps uniformly distributed on the real interval $[-1,+1]$. We study the large-$n$ behavior of the expected...
Analytic Combinatorics of Non-crossing Configurations (1997)
This paper describes a systematic approach to the enumeration of «non-crossing» geometric configurations built on vertices of a convex $n$-gon in the plane. It relies on generating functions,...
The Average Case Analysis of Algorithms : Multivariate Asymptotics and Limit Distributions (1997)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods of «analytic combinatorics» needed in the average--case analysis of algorithms. It develops a general...
The Analysis of Hybrid Trie Structures (1997)
Clément, Julien, Flajolet, Philippe, Vallée, Brigitte
This paper provides a detailed analysis of various implementations of digital tries, including the «ternary search tries» of Bentley and Sedgewick. The methods employed combine symbolic uses of...
On the Analysis of Linear Probing Hashing (1997)
Flajolet, Philippe, Poblete, Patricio, Viola, Alfredo
This paper presents moment analyses and characterizations of limit distributions for the construction cost of hash table under the linear probing strategy. Two models are considered, that of full...
The SIGSAM Challenges: Symbolic Asymptotics in Practice (1997)
Flajolet, Philippe, Salvy, Bruno
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 {\em Sigsam Bulletin}. In all cases, the answer to a...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
Coffman, E. G., Flajolet, Philippe, Flatto, Leopold, Hofri, Micha
We consider a symmetric random walk of length $n$ that starts at the origin and takes steps uniformly distributed on the real interval $[-1,+1]$. We study the large-$n$ behavior of the expected...
Analytic Combinatorics of Non-crossing Configurations (1997)
This paper describes a systematic approach to the enumeration of «non-crossing» geometric configurations built on vertices of a convex $n$-gon in the plane. It relies on generating functions,...
The Average Case Analysis of Algorithms : Multivariate Asymptotics and Limit Distributions (1997)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods of «analytic combinatorics» needed in the average--case analysis of algorithms. It develops a general...
The Analysis of Hybrid Trie Structures (1997)
Clément, Julien, Flajolet, Philippe, Vallée, Brigitte
This paper provides a detailed analysis of various implementations of digital tries, including the «ternary search tries» of Bentley and Sedgewick. The methods employed combine symbolic uses of...
On the Analysis of Linear Probing Hashing (1997)
Flajolet, Philippe, Poblete, Patricio, Viola, Alfredo
This paper presents moment analyses and characterizations of limit distributions for the construction cost of hash table under the linear probing strategy. Two models are considered, that of full...
The SIGSAM Challenges: Symbolic Asymptotics in Practice (1997)
Flajolet, Philippe, Salvy, Bruno
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 {\em Sigsam Bulletin}. In all cases, the answer to a...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
Coffman, E. G., Flajolet, Philippe, Flatto, Leopold, Hofri, Micha
We consider a symmetric random walk of length $n$ that starts at the origin and takes steps uniformly distributed on the real interval $[-1,+1]$. We study the large-$n$ behavior of the expected...
Analytic Combinatorics of Non-crossing Configurations (1997)
This paper describes a systematic approach to the enumeration of «non-crossing» geometric configurations built on vertices of a convex $n$-gon in the plane. It relies on generating functions,...
The Average Case Analysis of Algorithms : Multivariate Asymptotics and Limit Distributions (1997)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods of «analytic combinatorics» needed in the average--case analysis of algorithms. It develops a general...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
E. G. Coffman, Philippe Flajolet, E. G. Coffman, Leopold Flatto, Leopold Flatto, Micha Hofri, ...
: We consider a symmetric random walk of length n that starts at the origin and takes steps uniformly distributed on the real interval [\Gamma1; +1]. We study the large-n behavior of the expected...
Patterns In Random Binary Search Trees (1997)
Philippe Flajolet, Xavier Gourdon
In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well...
The Average Case Analysis of Algorithms: Multivariate Asymptotics and Limit Distributions (1997)
Philippe Flajolet, Robert Sedgewick, Robert Sedgewick
. This report is part of a series whose aim is to present in a synthetic way the major methods of "analytic combinatorics" needed in the average--case analysis of algorithms. It develops a...
Patterns in Random Binary Search Trees (1997)
Philippe Flajolet, Xavier Gourdon, Conrado Martinez
In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well...
The Analysis of Hybrid Trie Structures (1997)
Julien Clément, Philippe Flajolet, Brigitte Vallée
: This paper provides a detailed analysis of various implementations of digital tries, including the "ternary search tries" of Bentley and Sedgewick. The methods employed combine symbolic...
The Maximum of a Random Walk and Its Application to Rectangle Packing (1997)
E. G. Coffman, Philippe Flajolet, Leopold Flatto, Micha Hofri
Let S 0 ; : : : ; S n be a symmetric random walk that starts at the origin (S 0 = 0), and takes steps uniformly distributed on [\Gamma1; +1]. We study the large-n behavior of the expected maximum...
The SIGSAM Challenges: Symbolic Asymptotics in Practice (1997)
Philippe Flajolet, Bruno Salvy, Bruno Salvy, Bruno Salvy
: 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...
Analytic Combinatorics of Non-crossing Configurations (1997)
Philippe Flajolet, Marc Noy, Marc Noy, Marc Noy
: This paper describes a systematic approach to the enumeration of "noncrossing " geometric configurations built on vertices of a convex n-gon in the plane. It relies on generating...
The SIGSAM challenges: Symbolic asymptotics in practice (1997)
Philippe Flajolet, Bruno Salvy
We present answers to 5 out of 10 of the “Problems, Puzzles, Challenges ” pro-posed by G. J. Fee and M. B. Monagan in the March 1997 issue of the Sigsam Bulletin. In all cases, the answer to a...
Patterns in Random Binary Search Trees (1996)
Flajolet, Philippe, Gourdon, Xavier, Martinez, Conrado
Dans un arbre binaire de recherche (ABR) de taille~$n$ construit par insertions aléatoires, chaque motif appara{î}t avec une frequence qui est en moyenne proportionnelle à~$n$. Les déviations du...
The Average Case Analysis of Algorithms: Mellin Transform Asymptotics (1996)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods of «analytic combinatorics» needed in the average--case analysis of algorithms. It reviews the use of...
Continued Fraction Algorithms, Functional Operators, and Structure Constants (1996)
Flajolet, Philippe, Vallée, Brigitte
Continued fractions lie at the heart of a number of classical algorithms like Euclid's greatest common divisor algorithm or the lattice reduction algorithm of Gauss that constitutes a 2-dimensional...
Euler Sums and Contour Integral Representations (1996)
Flajolet, Philippe, Salvy, Bruno
This paper develops an approach to the evaluation of Euler sums involving harmonic numbers either linearly or nonlinearly. We give explicit formul{æ} for certain classes of Euler sums in terms of...
Random Polynomials and Polynomial Factorization (1996)
Flajolet, Philippe, Gourdon, Xavier, Panario, Daniel
We give a precise average-case analysis of a complete polynomial factorization chain over finite fields by methods based on generating functions and singularity analysis.
An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction (1996)
Daudé, Hervé, Flajolet, Philippe, Vallée, Brigitte
The Gaussian algorithm for lattice reduction in dimension 2 is analysed under its standard version. It is found that, when applied to random inputs in a continuous model, the complexity is constant...
Patterns in Random Binary Search Trees (1996)
Flajolet, Philippe, Gourdon, Xavier, Martinez, Conrado
Dans un arbre binaire de recherche (ABR) de taille~$n$ construit par insertions aléatoires, chaque motif appara{î}t avec une frequence qui est en moyenne proportionnelle à~$n$. Les déviations du...
The Average Case Analysis of Algorithms: Mellin Transform Asymptotics (1996)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods of «analytic combinatorics» needed in the average--case analysis of algorithms. It reviews the use of...
Continued Fraction Algorithms, Functional Operators, and Structure Constants (1996)
Flajolet, Philippe, Vallée, Brigitte
Continued fractions lie at the heart of a number of classical algorithms like Euclid's greatest common divisor algorithm or the lattice reduction algorithm of Gauss that constitutes a 2-dimensional...
Euler Sums and Contour Integral Representations (1996)
Flajolet, Philippe, Salvy, Bruno
This paper develops an approach to the evaluation of Euler sums involving harmonic numbers either linearly or nonlinearly. We give explicit formul{æ} for certain classes of Euler sums in terms of...
Random Polynomials and Polynomial Factorization (1996)
Flajolet, Philippe, Gourdon, Xavier, Panario, Daniel
We give a precise average-case analysis of a complete polynomial factorization chain over finite fields by methods based on generating functions and singularity analysis.
An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction (1996)
Daudé, Hervé, Flajolet, Philippe, Vallée, Brigitte
The Gaussian algorithm for lattice reduction in dimension 2 is analysed under its standard version. It is found that, when applied to random inputs in a continuous model, the complexity is constant...
Patterns in Random Binary Search Trees (1996)
Flajolet, Philippe, Gourdon, Xavier, Martinez, Conrado
Dans un arbre binaire de recherche (ABR) de taille~$n$ construit par insertions aléatoires, chaque motif appara{î}t avec une frequence qui est en moyenne proportionnelle à~$n$. Les déviations du...
The Average Case Analysis of Algorithms: Mellin Transform Asymptotics (1996)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods of «analytic combinatorics» needed in the average--case analysis of algorithms. It reviews the use of...
Continued Fraction Algorithms, Functional Operators, and Structure Constants (1996)
Flajolet, Philippe, Vallée, Brigitte
Continued fractions lie at the heart of a number of classical algorithms like Euclid's greatest common divisor algorithm or the lattice reduction algorithm of Gauss that constitutes a 2-dimensional...
Euler Sums and Contour Integral Representations (1996)
Flajolet, Philippe, Salvy, Bruno
This paper develops an approach to the evaluation of Euler sums involving harmonic numbers either linearly or nonlinearly. We give explicit formul{æ} for certain classes of Euler sums in terms of...
Random Polynomials and Polynomial Factorization (1996)
Flajolet, Philippe, Gourdon, Xavier, Panario, Daniel
We give a precise average-case analysis of a complete polynomial factorization chain over finite fields by methods based on generating functions and singularity analysis.
An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction (1996)
Daudé, Hervé, Flajolet, Philippe, Vallée, Brigitte
The Gaussian algorithm for lattice reduction in dimension 2 is analysed under its standard version. It is found that, when applied to random inputs in a continuous model, the complexity is constant...
Patterns in Random Binary Search Trees (1996)
Philippe Flajolet, Xavier Gourdon, Xavier Gourdon, Conrado Martinez, Conrado Martinez
. In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well...
Random Triangulations (Extended Abstract) (1996)
Luc Devroye, Philippe Flajolet, Inria Rocquencourt, Ferran Hurtado, Marc Noy, William Steiger
) 3 Luc Devroye McGill University luc@kriek.cs.mcgill.ca Philippe Flajolet INRIA - Rocquencourt Philippe.Flajolet@inria.fr Ferran Hurtado Universitat Politecnica de Catalunya hurtado@ma2.upc.es Marc...
The Average Case Analysis of Algorithms: Mellin Transform Asymptotics (1996)
Philippe Flajolet, Robert Sedgewick, Robert Sedgewick
. This report is part of a series whose aim is to present in a synthetic way the major methods of "analytic combinatorics" needed in the average--case analysis of algorithms. It reviews the...
Continued Fraction Algorithms, Functional Operators, and Structure Constants (1996)
Philippe Flajolet, Brigitte Vallee
Continued fractions lie at the heart of a number of classical algorithms like Euclid's greatest common divisor algorithm or the lattice reduction algorithm of Gauss that constitutes a...
An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction (1996)
Hervé Daude, Philippe Flajolet, Brigitte Vallée
.The Gaussian algorithm for lattice reduction in dimension 2 is analysed under its standard version. It is found that, when applied to random inputs in a continuous model, the complexity is constant...
Continued Fraction Algorithms, Functional Operators, and Structure Constants (1996)
Philippe Flajolet, Brigitte Vallée
. Continued fractions lie at the heart of a number of classical algorithms like Euclid's greatest common divisor algorithm or the lattice reduction algorithm of Gauss that constitutes a...
Random Polynomials and Polynomial Factorization (1996)
Philippe Flajolet, Xavier Gourdon, Xavier Gourdon, Daniel Panario, Daniel Panario
We give a precise average-case analysis of a complete polynomial factorization chain over finite fields by methods based on generating functions and singularity analysis. Polynomes al'eatoires...
Euler Sums and Contour Integral Representations (1996)
Philippe Flajolet, Bruno Salvy, Bruno Salvy, Bruno Salvy
This paper develops an approach to the evaluation of Euler sums involving harmonic numbers either linearly or nonlinearly. We give explicit formulae for certain classes of Euler sums in terms of...
The Average Case Analysis of Algorithms: Mellin Transform Asymptotics (1996)
Philippe Flajolet, Mellin Transform Asymptotics, Robert Sedgewick, Robert Sedgewick
. This report is part of a series whose aim is to present in a synthetic way the major methods of "analytic combinatorics" needed in the average--case analysis of algorithms. It reviews the...
Computer Algebra Libraries for Combinatorial Structures (1995)
Flajolet, Philippe, Salvy, Bruno
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,...
Computer Algebra Libraries for Combinatorial Structures (1995)
Flajolet, Philippe, Salvy, Bruno
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,...
Computer Algebra Libraries for Combinatorial Structures (1995)
Flajolet, Philippe, Salvy, Bruno
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,...
On The Gauss-Kuzmin-Wirsing Constant (1995)
Philippe Flajolet, Brigitte Vallée
. We give strong supporting evidence for the fact that the Gauss-Kuzmin-Wirsing constant is j 2 j = 0:30366 30028 98732 6585974481 21901 55623 \Sigma 10 \Gamma31 : If x 0 is uniformly distributed in...
Mellin Transforms And Asymptotics: Harmonic Sums (1995)
Philippe Flajolet, Xavier Gourdon, Philippe Dumas, Hjalmar Mellin
. This survey presents a unified and essentially self-contained approach to the asymptotic analysis of a large class of sums that arise in combinatorial mathematics, discrete probabilistic models,...
Mellin Transforms And Asymptotics: Finite Differences And Rice's Integrals (1995)
Philippe Flajolet, Robert Sedgewick
. High order differences of simple number sequences may be analysed asymptotically by means of integral representations, residue calculus, and contour integration. This technique, akin to Mellin...
Computer Algebra Libraries for Combinatorial Structures (1995)
Philippe Flajolet, Bruno Salvy, Bruno Salvy, Bruno Salvy
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,...
Mellin Transforms and Asymptotics: Harmonic Sums (1994)
Flajolet, Philippe, Gourdon, Xavier, Dumas, Philippe
This survey presents a unified and essentially self-contained approach to the asymptotic analysis of a large class of sums that arise in combinatorial mathematics, discrete probabilistic models, and...
The average case analysis of algorithms : Saddle Point Asymptotics (1994)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods of ``analytic combinatorics'' needed in the average--case analysis of algorithms. It reviews the use of...
Mellin Transforms and Asymptotics: Harmonic Sums (1994)
Flajolet, Philippe, Gourdon, Xavier, Dumas, Philippe
This survey presents a unified and essentially self-contained approach to the asymptotic analysis of a large class of sums that arise in combinatorial mathematics, discrete probabilistic models, and...
The average case analysis of algorithms : Saddle Point Asymptotics (1994)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods of ``analytic combinatorics'' needed in the average--case analysis of algorithms. It reviews the use of...
An Analysis of the gaussian algorithm for lattice reduction (1994)
Daude, H., Flajolet, Philippe, Vallee, B.
Résumé disponible dans le fichier PDF
Hypergeometrics and the cost structure of quadtrees (1994)
Flajolet, Philippe, Labelle, G., Laforest, L., Salvy, Bruno
Résumé disponible dans le fichier PDF
Mellin transforms and asymptotics : finite differences and Rice's integrals (1994)
Flajolet, Philippe, Sedgewick, R.
Résumé disponible dans le fichier PDF
Asymptotique des recurrences mahleriennes : le cas cyclotomique (1994)
Flajolet, Philippe, Dumas, Philippe
Résumé disponible dans le fichier PDF
Mellin Transforms and Asymptotics: Harmonic Sums (1994)
Flajolet, Philippe, Gourdon, Xavier, Dumas, Philippe
This survey presents a unified and essentially self-contained approach to the asymptotic analysis of a large class of sums that arise in combinatorial mathematics, discrete probabilistic models, and...
The average case analysis of algorithms : Saddle Point Asymptotics (1994)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a series whose aim is to present in a synthetic way the major methods of ``analytic combinatorics'' needed in the average--case analysis of algorithms. It reviews the use of...
An Analysis of the gaussian algorithm for lattice reduction (1994)
Daude, H., Flajolet, Philippe, Vallee, B.
Résumé disponible dans le fichier PDF
Hypergeometrics and the cost structure of quadtrees (1994)
Flajolet, Philippe, Labelle, G., Laforest, L., Salvy, Bruno
Résumé disponible dans le fichier PDF
Mellin transforms and asymptotics : finite differences and Rice's integrals (1994)
Flajolet, Philippe, Sedgewick, R.
Résumé disponible dans le fichier PDF
Asymptotique des recurrences mahleriennes : le cas cyclotomique (1994)
Flajolet, Philippe, Dumas, Philippe
Résumé disponible dans le fichier PDF
Search Costs in Quadtrees and Singularity Perturbation Asymptotics (1994)
Philippe Flajolet, Thomas Lafforgue
Quadtrees constitute a classical data structure for storing and accessing collections of points in multidimensional space. It is proved that, in any dimension, the cost of a random search in a...
Mellin Transforms and Asymptotics: The Mergesort Recurrence (1994)
Philippe Flajolet, Inria Rocquencourt, Mordecai Golin
. Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide--and--conquer algorithms. This note illustrates the techniques by providing a...
The Average Case Analysis Of Algorithms - Saddle Point Asymptotics (1994)
Philippe Flajolet, Rocquencourt Princeton, Robert Sedgewick, Robert Sedgewick
This report is part of a series whose aim is to present in a synthetic way the major methods of "analytic combinatorics" needed in the average--case analysis of algorithms. The series...
Hypergeometrics and the Cost Structure of Quadtrees (1994)
Philippe Flajolet, Gilbert Labelle, Gilbert Labelle, Louise Laforest, Louise Laforest, Louise Laforest, ...
. 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...
The Average case analysis of algorithms : complex asymptotics and generating functions (1993)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a projected series whose aim is to present in a synthetic way the major methods and models in the average-case analysis of algorithms. The present work - complex asymptotics...
The Average case analysis of algorithms : counting and generating functions (1993)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a projected series whose aim is to present in a synthetic way the major methods and models in the average-case analysis of algorithms. The present work (counting and generating...
Mellin transforms and asymptotics : the mergesort recurrence (1993)
Flajolet, Philippe, Golin, Mordecai J.
Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise...
The Average case analysis of algorithms : complex asymptotics and generating functions (1993)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a projected series whose aim is to present in a synthetic way the major methods and models in the average-case analysis of algorithms. The present work - complex asymptotics...
The Average case analysis of algorithms : counting and generating functions (1993)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a projected series whose aim is to present in a synthetic way the major methods and models in the average-case analysis of algorithms. The present work (counting and generating...
Sur une famille de polynomes issus de l'analyse numerique (1993)
Flajolet, Philippe, Gourdon, Xavier, Salvy, Bruno
Disponible dans les fichiers attachés à ce document
Search costs in quadtrees and singularity perturbation asymptotics (1993)
Flajolet, Philippe, Lafforgue, T.
Résumé disponible dans le fichier PDF
A Calculus for the random generation of combinatorial structures (1993)
Flajolet, Philippe, Zimmermann, Paul, Van Custem, B.
Résumé disponbile dans les fichiers attachés
The Average case analysis of algorithms : complex asymptotics and generating functions (1993)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a projected series whose aim is to present in a synthetic way the major methods and models in the average-case analysis of algorithms. The present work - complex asymptotics...
The Average case analysis of algorithms : counting and generating functions (1993)
Flajolet, Philippe, Sedgewick, Robert
This report is part of a projected series whose aim is to present in a synthetic way the major methods and models in the average-case analysis of algorithms. The present work (counting and generating...
Sur une famille de polynomes issus de l'analyse numerique (1993)
Flajolet, Philippe, Gourdon, Xavier, Salvy, Bruno
Disponible dans les fichiers attachés à ce document
Search costs in quadtrees and singularity perturbation asymptotics (1993)
Flajolet, Philippe, Lafforgue, T.
Résumé disponible dans le fichier PDF
A Calculus for the random generation of combinatorial structures (1993)
Flajolet, Philippe, Zimmermann, Paul, Van Custem, B.
Résumé disponbile dans les fichiers attachés
Mellin Transforms And Asymptotics: Digital Sums (1993)
Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger, Robert F. Tichy
Arithmetic functions related to number representation systems exhibit various periodicity phenomena. For instance, a well known theorem of Delange expresses the total number of ones in the binary...
A Calculus for the Random Generation of Combinatorial Structures (1993)
Philippe Flajolet, Ite De Recherche, Et En Automatique, Domaine De Voluceau, Paul Zimmermann, Paul Zimmermann, ...
. A systematic approach to the random generation of labelled combinatorial objects is presented. It applies to structures that are decomposable, i.e., formally speci#able by grammars involving set,...
The Average Case Analysis Of Algorithms (1993)
Philippe Flajolet, Robert Sedgewick, Rocquencourt Princeton
This report is part of a projected series whose aim is to present in a synthetic way the major methods and models in the average--case analysis of algorithms. The following items are to be treated in...
A Calculus for the Random Generation of Combinatorial Structures (1993)
Philippe Flajolet, E De Recherche, Et En Automatique, Domaine De Voluceau, Paul Zimmermann, Paul Zimmermann, ...
. A systematic approach to the random generation of labelled combinatorial objects is presented. It applies to structures that are decomposable, i.e., formally specifiable by grammars involving set,...
Algorithms seminar, 1991-1992 (1992)
Flajolet, Philippe, Zimmermann, P.
These seminar notes represent the proceedings, consisting of 36 brief articles (some in french), of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include...
On Ramanujan's Q-function (1992)
Flajolet, Philippe, Grabner, P.J., Kirschenhofer, P., Prodinger, H.
This study provides a detailed analysis of a function which Knuth discovered to play a central role in the analysis of hashing with linear probing. The function, named after Knuth Q(n), is related to...
The Distribution of heights of binary trees and other simple trees (1992)
Flajolet, Philippe, Gao, Z., Odlyzko, A., Richmond, B.
The number of binary trees of fixed size and given height is estimated asymptotically near the peak of the distribution. There, a local limit theorem with convergence to a theta law is established....
Analytic analysis of algorithms (1992)
The average case analysis of algorithms can avail itself of the development of synthetic methods in combinatorial enumerations and in asymptotic analysis. Symbolic methods in combinatorial analysis...
Mellin transforms and asymptotics: the mergesort recurrence (1992)
Flajolet, Philippe, Golin, Mordecai
Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise...
Algorithms seminar, 1991-1992 (1992)
Flajolet, Philippe, Zimmermann, Paul
These seminar notes represent the proceedings, consisting of 36 brief articles (some in french), of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include...
On Ramanujan's Q-function (1992)
Flajolet, Philippe, Grabner, P.J., Kirschenhofer, P., Prodinger, H.
This study provides a detailed analysis of a function which Knuth discovered to play a central role in the analysis of hashing with linear probing. The function, named after Knuth Q(n), is related to...
The Distribution of heights of binary trees and other simple trees (1992)
Flajolet, Philippe, Gao, Zhicheng, Odlyzko, Andrew M., Richmond, Bruce
The number of binary trees of fixed size and given height is estimated asymptotically near the peak of the distribution. There, a local limit theorem with convergence to a theta law is established....
Analytic analysis of algorithms (1992)
The average case analysis of algorithms can avail itself of the development of synthetic methods in combinatorial enumerations and in asymptotic analysis. Symbolic methods in combinatorial analysis...
Mellin transforms and asymptotics: the mergesort recurrence (1992)
Flajolet, Philippe, Golin, Mordecai
Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise...
Varieties of increasing trees (1992)
Bergeron, F., Flajolet, Philippe, Salvy, Bruno
Résumé disponible dans les fichiers attachés
Algorithms seminar, 1991-1992 (1992)
Flajolet, Philippe, Zimmermann, Paul
These seminar notes represent the proceedings, consisting of 36 brief articles (some in french), of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include...
On Ramanujan's Q-function (1992)
Flajolet, Philippe, Grabner, P.J., Kirschenhofer, P., Prodinger, H.
This study provides a detailed analysis of a function which Knuth discovered to play a central role in the analysis of hashing with linear probing. The function, named after Knuth Q(n), is related to...
The Distribution of heights of binary trees and other simple trees (1992)
Flajolet, Philippe, Gao, Zhicheng, Odlyzko, Andrew M., Richmond, Bruce
The number of binary trees of fixed size and given height is estimated asymptotically near the peak of the distribution. There, a local limit theorem with convergence to a theta law is established....
Analytic analysis of algorithms (1992)
The average case analysis of algorithms can avail itself of the development of synthetic methods in combinatorial enumerations and in asymptotic analysis. Symbolic methods in combinatorial analysis...
Mellin transforms and asymptotics: the mergesort recurrence (1992)
Flajolet, Philippe, Golin, Mordecai
Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise...
Varieties of increasing trees (1992)
Bergeron, F., Flajolet, Philippe, Salvy, Bruno
Résumé disponible dans les fichiers attachés
On Ramanujan's Q-Function (1992)
Philippe Flajolet, Peter J. Grabner, Peter Kirschenhofer, Helmut Prodinger
. This study provides a detailed analysis of a function which Knuth discovered to play a central role in the analysis of hashing with linear probing. The function, named after Knuth Q(n), is related...
Generalized Digital Trees and their Difference-differential Equations (1992)
Philippe Flajolet, Bruce Richmond
. Consider a tree partitioning process in which n elements are split into b at the root of a tree (b a design parameter), the rest going recursively into two subtrees with a binomial probability...
Page Usage in a Quadtree Index (1992)
Mamoru Hoshi, Philippe Flajolet
. This paper provides a characterization of the storage needs of a quadtree when used as an index to access large volumes of 2--dimensional data. It is shown that the page occupancy for data in...
Analytic Analysis of Algorithms (1992)
. The average case analysis of algorithms can avail itself of the development of synthetic methods in combinatorial enumerations and in asymptotic analysis. Symbolic methods in combinatorial analysis...
Algorithms Seminar, 1991-1992 (1992)
Philippe Flajolet, E De Recherche, Et En Automatique, Domaine De Voluceau, Paul Zimmermann, Paul Zimmermann
. These seminar notes represent the proceedings, consisting of 36 brief articles (some in French), of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include...
Mellin transforms and asymptotics : digital sums (1991)
Flajolet, Philippe, Grabner, Peter, Prodinger, Helmut, Tichy, Robert F., Kirschenhofer, Peter
Résumé disponible dans le fichier PDF
Page usage in quadtree indexes (1991)
Résumé disponible dans le fichier PDF
Generalized digital trees and their difference-differential equations (1991)
Flajolet, Philippe, Richmond, Bruce
Résumé disponible dans le fichier PDF
Mellin transforms and asymptotics : digital sums (1991)
Flajolet, Philippe, Grabner, Peter, Prodinger, Helmut, Tichy, Robert F., Kirschenhofer, Peter
Résumé disponible dans le fichier PDF
Page usage in quadtree indexes (1991)
Résumé disponible dans le fichier PDF
Generalized digital trees and their difference-differential equations (1991)
Flajolet, Philippe, Richmond, Bruce
Résumé disponible dans le fichier PDF
The Average Case Analysis Of Algorithms - Complex Asymptotics and Generating Functions (1991)
Philippe Flajolet, Robert Sedgewick, Rocquencourt Princeton
This report is part of a projected series whose aim is to present in a synthetic way the major methods and models in the average--case analysis of algorithms. The following items are to be treated in...
Automatic Average-Case Analysis Of Algorithms (1991)
Philippe Flajolet, E De Recherche, Et En Automatique, Domaine De Voluceau, Bruno Salvy, Bruno Salvy, ...
. 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...
Philippe Flajolet, Inria Rocquencourt
This note proposes a natural combinatorial setting for results stated by P'olya regarding the enumeration of `diagonally convex lattice polygons ' also known as parallelogram polyominoes,...
Philippe Flajolet, Michèle Soria, Mich Ele Soriay, Le Chesnay (france
. We give a direct generating function construction for cycles of combinatorial structures. Let A be a class of combinatorial structures, with A(z) its corresponding ordinary generating function:...
Analytic Variations on Quad-Trees (1991)
Philippe Flajolet, Gaston Gonnet, Claude Puech, J. M. Robson
. Quadtrees constitute a hierarchical data structure which permits fast access to multidimensional data. This paper presents the analysis of the expected cost of various types of searches in...
The analysis of multidimensional searching in quad-trees (1990)
Flajolet, Philippe, Puech, Claude, Robson, J.M., Gonnet, Gaston
Résumé disponible dans les fichiers attachés
Automatic average-case analysis of algorithms (1990)
Flajolet, Philippe, Zimmermann, Paul, Salvy, Bruno
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...
Analytic variations on the common subexpression problem (1990)
Flajolet, Philippe, Steyaert, Jean-Marc, Sipala, Paola
ou la constante C se relie explicitement au type d'arbre compacte et au modele statistique refletant l'utilisation des arbres. En particulier, il apparait que le gain apporte par la compactification...
The analysis of multidimensional searching in quad-trees (1990)
Flajolet, Philippe, Puech, Claude, Robson, J.M., Gonnet, Gaston
Résumé disponible dans les fichiers attachés
Automatic average-case analysis of algorithms (1990)
Flajolet, Philippe, Zimmermann, Paul, Salvy, Bruno
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...
Analytic variations on the common subexpression problem (1990)
Flajolet, Philippe, Steyaert, Jean-Marc, Sipala, Paola
ou la constante C se relie explicitement au type d'arbre compacte et au modele statistique refletant l'utilisation des arbres. En particulier, il apparait que le gain apporte par la compactification...
General Combinatorial Schemas: Gaussian Limit Distributions and Exponential Tails (1990)
Philippe Flajolet, Michèle Soria, Aviezri S. Fraenkel
. Under general conditions, the number of components in combinatorial structures defined as sequences, cycles or sets of components, admits a Gaussian limit distribution together with an exponential...
Analytic Variations On The Common Subexpression Problem (1990)
Philippe Flajolet, Inria Rocquencourt, Paolo Sipala, Jean-marc Steyaert
. Any tree can be represented in a maximally compact form as a directed acyclic graph where common subtrees are factored and shared, being represented only once. Such a compaction can be effected in...
Random Mapping Statistics (1990)
Philippe Flajolet, Andrew M. Odlyzko
. Random mappings from a finite set into itself are either a heuristic or an exact model for a variety of applications in random number generation, computational number theory, cryptography, and the...
. We analyze the storage/accuracy trade--off of an adaptive sampling algorithm due to Wegman that makes it possible to evaluate probabilistically the number of distinct elements in a large file...
Random mapping statistics (1989)
Flajolet, Philippe, Odlyzko, Andrew M.
Random mappings from a finite set into itself are either a heuristic or an exact model for a variety of applications in random number generation, computational number theory, cryptography, and the...
Non overlapping partitions, continued fractions, Bessel functions and a divergent series (1989)
Flajolet, Philippe, Schott, René
Résumé disponible dans les fichiers attachés
Lambda-Upsilon-Omega the 1989 cookbook (1989)
Flajolet, Philippe, Zimmermann, Paul, Salvy, Bruno
Résumé disponible dans les fichiers attachés
General combinatorial schemas with Gaussian limit distributions and exponential tails (1989)
Flajolet, Philippe, Soria, Michèle
Résumé disponible dans les fichiers attachés
Random mapping statistics (1989)
Flajolet, Philippe, Odlyzko, Andrew M.
Random mappings from a finite set into itself are either a heuristic or an exact model for a variety of applications in random number generation, computational number theory, cryptography, and the...
Non overlapping partitions, continued fractions, Bessel functions and a divergent series (1989)
Flajolet, Philippe, Schott, René
Résumé disponible dans les fichiers attachés
Lambda-Upsilon-Omega the 1989 cookbook (1989)
Flajolet, Philippe, Zimmermann, Paul, Salvy, Bruno
Résumé disponible dans les fichiers attachés
General combinatorial schemas with Gaussian limit distributions and exponential tails (1989)
Flajolet, Philippe, Soria, Michèle
Résumé disponible dans les fichiers attachés
Lambda-Upsilon-Omega: An Assistant Algorithms Analyzer (1989)
Philippe Flajolet, Bruno Salvy, Paul Zimmermann
. Lambda-Upsilon-Omega, \Upsilon\Omega , is a system designed to perform automatic analysis of well-defined classes of algorithms operating over "decomposable" data structures. It consists...
Lambda-Upsilon-Omega - The 1989 Cookbook (1989)
Philippe Flajolet, E De Recherche, Et En Automatique, Domaine De Voluceau, Bruno Salvy, Paul Zimmermann, ...
. Lambda--Upsilon--Omega ( \Upsilon\Omega ) 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...
Elliptic functions, continued fractions and doubled permutations (1989)
Philippe Flajolet, Jean Francon
The Taylor coefficients of the Jacobian elliptic functions are shown to count classes of permu-tations with a simple repetitive order pattern. The proof relies on the use of enumerative properties of...
Average cost of orthogonal range queries in multiattribute trees (1988)
Gardy, Danièle, Flajolet, Philippe, Puech, Claude
Résumé disponible dans les fichiers attachés
The first cycles in an evolving graph (1988)
Flajolet, Philippe, Pittel, Boris, Knuth, Donald E.
Résumé disponible dans les fichiers attachés
Lambda-Upsilon-Omega : an assistant algorithms analyzer (1988)
Flajolet, Philippe, Zimmermann, Paul, Salvy, Bruno
Résumé disponible dans les fichiers attachés
Singularity analysis of generating functions (1988)
Flajolet, Philippe, Odlyzko, Andrew M.
Résumé disponible dans les fichiers attachés
Gaussian limiting distributions for the number of components in combinatorial structures (1988)
Flajolet, Philippe, Soria, Michèle
Résumé disponible dans les fichiers attachés
Average cost of orthogonal range queries in multiattribute trees (1988)
Gardy, Danièle, Flajolet, Philippe, Puech, Claude
Résumé disponible dans les fichiers attachés
The first cycles in an evolving graph (1988)
Flajolet, Philippe, Pittel, Boris, Knuth, Donald E.
Résumé disponible dans les fichiers attachés
Lambda-Upsilon-Omega : an assistant algorithms analyzer (1988)
Flajolet, Philippe, Zimmermann, Paul, Salvy, Bruno
Résumé disponible dans les fichiers attachés
Singularity analysis of generating functions (1988)
Flajolet, Philippe, Odlyzko, Andrew M.
Résumé disponible dans les fichiers attachés
Gaussian limiting distributions for the number of components in combinatorial structures (1988)
Flajolet, Philippe, Soria, Michèle
Résumé disponible dans les fichiers attachés
Elliptic functions, continued fractions and doubled permutations (1987)
Flajolet, Philippe, Françon, Jean
Résumé disponible dans les fichiers attachés
Average-case analysis of algorithms and data structures (1987)
Flajolet, Philippe, Vitter, J.S.
Résumé disponible dans les fichiers attachés
Deviations from normality in random strings (1987)
Flajolet, Philippe, Tichy, Robert F., Kirschenhofer, Peter
Résumé disponible dans les fichiers attachés
Birthday paradox,coupon collectors,caching algorithms and self-organizing search (1987)
Flajolet, Philippe, Thimonier, Loÿs, Gardy, Danièle
Résumé disponible dans les fichiers attachés
Analytic models for tree communication protocols (1987)
Flajolet, Philippe, Jacquet, Philippe
Résumé disponible dans les fichiers attachés
Elliptic functions, continued fractions and doubled permutations (1987)
Flajolet, Philippe, Françon, Jean
Résumé disponible dans les fichiers attachés
Average-case analysis of algorithms and data structures (1987)
Flajolet, Philippe, Vitter, J.S.
Résumé disponible dans les fichiers attachés
Deviations from normality in random strings (1987)
Flajolet, Philippe, Tichy, Robert F., Kirschenhofer, Peter
Résumé disponible dans les fichiers attachés
Birthday paradox,coupon collectors,caching algorithms and self-organizing search (1987)
Flajolet, Philippe, Thimonier, Loÿs, Gardy, Danièle
Résumé disponible dans les fichiers attachés
Analytic models for tree communication protocols (1987)
Flajolet, Philippe, Jacquet, Philippe
Résumé disponible dans les fichiers attachés
Prefixes of infinite words and ambiguous context-free languages (1986)
Autebert, Jean-Michel, Flajolet, Philippe, Gabarro, Joaquim
Résumé disponible dans les fichiers attachés
Level number sequences for trees (1986)
Flajolet, Philippe, Prodinger, Helmut
Résumé disponible dans les fichiers attachés
Prefixes of infinite words and ambiguous context-free languages (1986)
Autebert, Jean-Michel, Flajolet, Philippe, Gabarro, Joaquim
Résumé disponible dans les fichiers attachés
Level number sequences for trees (1986)
Flajolet, Philippe, Prodinger, Helmut
Résumé disponible dans les fichiers attachés
Some uses of the Mellin integral transform in the analysis of algorithms (1985)
Flajolet, Philippe, Sedgewick, Robert, Regnier, Mireille
Résumé disponible dans les fichiers attachés
Some uses of the Mellin integral transform in the analysis of algorithms (1985)
Flajolet, Philippe, Sedgewick, Robert, Regnier, Mireille
Résumé disponible dans les fichiers attachés
Approximate counting: A detailed analysis (1985)
Approximate counting is an algorithm proposed by R. Morris which makes it possible to keep approximate counts of large numbers in small counters. The algorithm is useful for gathering statistics of a...
Estimating the multiplicities of conflicts in multiple access channels (1984)
Greenberg, Albert, Flajolet, Philippe, Ladner, Richard E.
Résumé disponible dans les fichiers attachés
Digital search trees revisited (1984)
Flajolet, Philippe, Sedgewick, Robert
Résumé disponible dans les fichiers attachés
Probabilistic counting algorithms for data base applications (1984)
Flajolet, Philippe, Martin, G. Nigel
Résumé disponible dans les fichiers attachés
Algebraic methods for trie statistics (1984)
Flajolet, Philippe, Sotteau, Dominique, Regnier, Mireille
Résumé disponible dans les fichiers attachés
Flajolet, Philippe, Odlyzko, Andrew M.
Résumé disponible dans les fichiers attachés
Register allocation for unary-binary trees (1984)
Flajolet, Philippe, Prodinger, Helmut
Résumé disponible dans les fichiers attachés
Estimating the multiplicities of conflicts in multiple access channels (1984)
Greenberg, Albert, Flajolet, Philippe, Ladner, Richard E.
Résumé disponible dans les fichiers attachés
Digital search trees revisited (1984)
Flajolet, Philippe, Sedgewick, Robert
Résumé disponible dans les fichiers attachés
Probabilistic counting algorithms for data base applications (1984)
Flajolet, Philippe, Martin, G. Nigel
Résumé disponible dans les fichiers attachés
Algebraic methods for trie statistics (1984)
Flajolet, Philippe, Sotteau, Dominique, Regnier, Mireille
Résumé disponible dans les fichiers attachés
Flajolet, Philippe, Odlyzko, Andrew M.
Résumé disponible dans les fichiers attachés
Register allocation for unary-binary trees (1984)
Flajolet, Philippe, Prodinger, Helmut
Résumé disponible dans les fichiers attachés
Philippe Flajolet, G. Nigel Martin
This paper introduces a class of probabilistic counting algorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large file stored on disk) in...
A complexity calculus for recursive tree algorithms (1983)
Flajolet, Philippe, Steyaert, Jean-Marc
Résumé disponible dans les fichiers attachés
The analysis of simple list structures (1983)
Flajolet, Philippe, Vuillemin, J., Puech, Claude
Résumé disponible dans les fichiers attachés
Fayolle, Guy, Flajolet, Philippe, Jacquet, Philippe, Hofri, Micha
Résumé disponible dans les fichiers attachés
Partial match retrieval of multidimensional data (1983)
Flajolet, Philippe, Puech, Claude
Résumé disponible dans les fichiers attachés
A complexity calculus for recursive tree algorithms (1983)
Flajolet, Philippe, Steyaert, Jean-Marc
Résumé disponible dans les fichiers attachés
The analysis of simple list structures (1983)
Flajolet, Philippe, Vuillemin, J., Puech, Claude
Résumé disponible dans les fichiers attachés
Fayolle, Guy, Flajolet, Philippe, Jacquet, Philippe, Hofri, Micha
Résumé disponible dans les fichiers attachés
Partial match retrieval of multidimensional data (1983)
Flajolet, Philippe, Puech, Claude
Résumé disponible dans les fichiers attachés
The complexity of generating an exponentially distributed variate (1982)
Flajolet, Philippe, Saheb, Nasser
Résumé disponible dans les fichiers attachés
Fayolle, Guy, Flajolet, Philippe, Hofri, Micha
Résumé disponible dans les fichiers attachés
The complexity of generating an exponentially distributed variate (1982)
Flajolet, Philippe, Saheb, Nasser
Résumé disponible dans les fichiers attachés
Fayolle, Guy, Flajolet, Philippe, Hofri, Micha
Résumé disponible dans les fichiers attachés
Analyse de structures de données dynamiques et histoires de fichiers (1981)
Flajolet, Philippe, Puech, Claude
La théorie des histoires de fichiers permet d'analyser le coût de suites d'opérations portant sur des fichiers dont la taille varie avec le temps; elle permet donc de comparer, vis à vis de...
Analyse de structures de données dynamiques et histoires de fichiers (1981)
Flajolet, Philippe, Puech, Claude
La théorie des histoires de fichiers permet d'analyser le coût de suites d'opérations portant sur des fichiers dont la taille varie avec le temps; elle permet donc de comparer, vis à vis de...
The average height of binary trees and other simple trees (1981)
Flajolet, Philippe, Odlyzko, Andrew M.
Résumé disponible dans les fichiers attachés
The average height of binary trees and other simple trees (1981)
Flajolet, Philippe, Odlyzko, Andrew M.
Résumé disponible dans les fichiers attachés
Analyse de structures de données dynamiques et histoires de fichiers (1981)
Flajolet, Philippe, Puech, Claude
La théorie des histoires de fichiers permet d'analyser le coût de suites d'opérations portant sur des fichiers dont la taille varie avec le temps; elle permet donc de comparer, vis à vis de...
Philippe Flajolet, Andrew Odlyzko
The average height of a binary tree with n internal nodes is shown to be asymptotic to 2 6. This represents the average stack height of the simplest recursive tree traversal algorithm. The method...
Une formalisation de la notion d'algorithme de tri non récurrent / (1973)
Flajolet, Philippe., Steyaert, Jean-Marc.
Thèse--Université Paris VII.
Philippe Flajolet, Guy Louchard
Abstract. The Airy distribution (of the \area " type) occurs as limit distribution of cumulative parameters in a number of combinatorial structures, like path length in trees, area below...
Philippe Flajolet, Guy Louchard
Abstract. The Airy distribution (of the \area " type) occurs as limit distribution of cumulative parameters in a number of combinatorial structures, like path length in trees, area below...
The Complete Analysis of a Polynomial Factorization Algorithm Over Finite Fields
Philippe Flajolet, Xavier Gourdon, Xavier Gourdon, Xavier Gourdon, Daniel Panario, Daniel Panario, ...
: A unified treatment of parameters relevant to factoring polynomials over finite fields is given. The framework is based on generating functions for describing parameters of interest and on...