6.   Singularity Analysis of Generating Functions



VI.1 A glimpse of basic singularity analysis theory


VI.2 Coefficient asymptotics for the standard scale


VI.3 Transfers


VI.4 The process of singularity analysis


VI.5 Multiple singularities


VI.6 Intermezzo: functions amenable to singularity analysis


VI.7 Inverse functions


VI.8 Polylogarithms


VI.9 Functional composition


VI.10 Closure properties


VI.11 Tauberian theory and Darboux’s method


VI.12 Perspective


Web Exercises

VI.1

Use the standard function scale to directly derive an asymptotic expression for the number of strings
in this following CFG: S = E + U×Z×S + D×Z×S, U = Z + U×U×Z, D = Z + D×D×Z.


VI.2

Give an asymptotic expression for the number of rooted ordered trees for which every node has 0, 2, or 3 children. How many bits are necessary to represent such a tree?



Selected Experiments

Program VI.1

In the style of the plots in Lecture 6, do $r$- and $\theta$-plots of $1/\Gamma(z)$ in the unit square
 of size 10 centered at the origin. Click here for access to the Java code used for the lecture.