Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T23:44:07.392Z Has data issue: false hasContentIssue false
  • English
  • Français

Formulae and Asymptotics for Coefficients of Algebraic Functions

Published online by Cambridge University Press:  11 December 2014

CYRIL BANDERIER  and
MICHAEL DRMOTA
CYRIL BANDERIER
Affiliation:
CNRS – Université Paris 13, 93430 Villetaneuse, France (e-mail: [email protected], http://lipn.univ-paris13.fr/~banderier)
MICHAEL DRMOTA
Affiliation:
Institut für Diskrete Mathematik und Geometrie, TU Wien, A1040 Wien, Austria (e-mail: [email protected], http://dmg.tuwien.ac.at/drmota/)
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the coefficients of algebraic functions ∑n≥0fnzn. First, we recall the too-little-known fact that these coefficients fn always admit a closed form. Then we study their asymptotics, known to be of the type fn ~ CAnnα. When the function is a power series associated to a context-free grammar, we solve a folklore conjecture: the critical exponents α cannot be 1/3 or −5/2; they in fact belong to a proper subset of the dyadic numbers. We initiate the study of the set of possible values for A. We extend what Philippe Flajolet called the Drmota–Lalley–Woods theorem (which states that α=−3/2 when the dependency graph associated to the algebraic system defining the function is strongly connected). We fully characterize the possible singular behaviours in the non-strongly connected case. As a corollary, the generating functions of certain lattice paths and planar maps are not determined by a context-free grammar (i.e., their generating functions are not ℕ-algebraic). We give examples of Gaussian limit laws (beyond the case of the Drmota–Lalley–Woods theorem), and examples of non-Gaussian limit laws. We then extend our work to systems involving non-polynomial entire functions (non-strongly connected systems, fixed points of entire functions with positive coefficients). We give several closure properties for ℕ-algebraic functions. We end by discussing a few extensions of our results (infinite systems of equations, algorithmic aspects).

Keywords

Primary 05A1505A16Secondary 68Q4568R15
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Special Issue 1: Honouring the Memory of Philippe Flajolet - Part 3 , January 2015 , pp. 1 - 53
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Abel, N. H. (1992) Œuvres Complètes, Vol. II, Éditions J. Gabay, Sceaux. Reprint of the second edition of 1881.Google Scholar
[2] Adamczewski, B. and Bell, J. P. (2012) On vanishing coefficients of algebraic power series over fields of positive characteristic. Inventio Math. 187 343–393.Google Scholar
[3] Albert, M. H. and Atkinson, M. D. (2005) Simple permutations and pattern restricted permutations. Discrete Math. 300 1–15.CrossRefGoogle Scholar
[4] Allouche, J.-P. and Shallit, J. (2003) Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press.Google Scholar
[5] Autebert, J.-M., Flajolet, P. and Gabarró, J. (1987) Prefixes of infinite words and ambiguous context-free languages. Inform. Process. Lett. 25 211–216.Google Scholar
[6] Banderier, C. (2001) Combinatoire analytique des chemins et des cartes. PhD thesis, Université Paris-VI.Google Scholar
[7] Banderier, C. (2002) Limit laws for basic parameters of lattice paths with unbounded jumps. In Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities (Chauvin, B. et al., eds), Trends in Mathematics, Birkhäuser, pp. 33–47.Google Scholar
[8] Banderier, C., Bodini, O., Ponty, Y. and Tafat, H. (2012) On the diversity of pattern distributions in combinatorial systems. In Proc. Analytic Algorithmics and Combinatorics: ANALCO'12, SIAM, pp. 107–116.Google Scholar
[9] Banderier, C., Bousquet-Mélou, M., Denise, A., Flajolet, P., Gardy, G. and Gouyou-Beauchamps, D. (2002) Generating functions for generating trees. Discrete Math. 246 29–55.Google Scholar
[10] Banderier, C. and Flajolet, P. (2002) Basic analytic combinatorics of directed lattice paths. Theoret. Comput. Sci. 281 37–80.Google Scholar
[11] Banderier, C., Flajolet, P., Schaeffer, G. and Soria, M. (2001) Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Struct. Alg. 19 194–246.Google Scholar
[12] Banderier, C. and Gittenberger, B. (2006) Analytic combinatorics of lattice paths: Enumeration and asymptotics for the area. In Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proc. AG, pp. 345–355.Google Scholar
[13] Banderier, C. and Hitczenko, P. (2012) Enumeration and asymptotics of restricted compositions having the same number of parts. Discrete Appl. Math. 160 2542–2554.Google Scholar
[14] Banderier, C. and Merlini, D. (2002) Lattice paths with an infinite set of jumps. In Proc. FPSAC 2002.Google Scholar
[15] Banderier, C. and Schwer, S. (2005) Why Delannoy numbers? J. Statist. Plann. Inference 135 40–54.Google Scholar
[16] Barcucci, E., Del Lungo, A., Frosini, A. and Rinaldi, S. (2001) A technology for reverse-engineering a combinatorial problem from a rational generating function. Adv. Appl. Math. 26 129–153.Google Scholar
[17] Bassino, F., Bouvel, M., Pivoteau, C., Pierrot, A. and Rossin, D. (2012) Combinatorial specification of permutation classes. In Proc. FPSAC '2012, DMTCS Proc. AR, pp. 791–802.Google Scholar
[18] Béal, M.-P., Blocklet, M. and Dima, C. (2014) Zeta functions of finite-type-Dyck shifts are ℕ-algebraic. In Proc. 2014 Information Theory and Applications Workshop, IEEE.Google Scholar
[19] Bell, J. P., Burris, S. N. and Yeats, K. (2012) On the set of zero coefficients of a function satisfying a linear differential equation. Math. Proc. Cambridge Philos. Soc. 153 235–247.Google Scholar
[20] Bergeron, F., Labelle, G. and Leroux, P. (1998) Combinatorial Species and Tree-Like Structures, Vol. 67 of Encyclopedia of Mathematics and its Applications, Cambridge University Press. Translated from the 1994 French original by Margaret Readdy.Google Scholar
[21] Berstel, J. (1971) Sur les pôles et le quotient de Hadamard de séries ℕ-rationnelles. CR Acad. Sci. Paris Sér. A–B 272 A1079–A1081.Google Scholar
[22] Berstel, J. and Boasson, L. (1996) Towards an algebraic theory of context-free languages. Fund. Inform. 25 217–239.Google Scholar
[23] Berstel, J. and Reutenauer, C. (2011) Noncommutative Rational Series with Applications, Vol. 137 of Encyclopedia of Mathematics and its Applications, Cambridge University Press.Google Scholar
[24] Bertoni, A., Goldwurm, M. and Santini, M. (2001) Random generation for finitely ambiguous context-free languages. Theor. Inform. Appl. 35 499–512.Google Scholar
[25] Beukers, F. and Heckman, G. (1989) Monodromy for the hypergeometric function n F n–1 . Inventio Math. 95 325–354.Google Scholar
[26] Bodini, O., Darrasse, A. and Soria, M. (2008) Distances in random Apollonian network structures. In 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics: FPSAC 2008, DMTCS Proc. AJ, pp. 307–318.Google Scholar
[27] Bodini, O. and Ponty, Y. (2010) Multi-dimensional Boltzmann sampling of languages. In 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms: AofA'10, DMTCS Proc. AM, pp. 49–64.Google Scholar
[28] Bostan, A., Chyzak, F., Lecerf, G., Salvy, B. and Schost, E. (2007) Differential equations for algebraic functions. In Proc. ISSAC 2007, ACM, pp. 25–32.Google Scholar
[29] Bostan, A. and Kauers, M. (2009) Automatic classification of restricted lattice walks. In Proc. FPSAC '09 (Krattenthaler, C., Strehl, V. and Kauers, M., eds), pp. 201–215.Google Scholar
[30] Bostan, A. and Kauers, M. (2010) The complete generating function for Gessel walks is algebraic. Proc. Amer. Math. Soc. 138 3063–3078.Google Scholar
[31] Bostan, A., Lairez, P. and Salvy, B. (2014) Integral representations of binomial sums. In preparation.Google Scholar
[32] Bousquet-Mélou, M. (2006) Rational and algebraic series in combinatorial enumeration. In Proc. International Congress of Mathematicians, Vol. III, European Mathematical Society, pp. 789–826.Google Scholar
[33] Bousquet-Mélou, M. and Jehanne, A. (2006) Polynomial equations with one catalytic variable, algebraic series and map enumeration. J. Combin. Theory Ser. B 96 623–672.Google Scholar
[34] Bousquet-Mélou, M. and Schaeffer, G. (2002) Walks on the slit plane. Probab. Theory Rel. Fields 124 305–344.Google Scholar
[35] Canou, B. and Darrasse, A. (2009) Fast and sound random generation for automated testing and benchmarking in objective Caml. In Proc. 2009 ACM SIGPLAN Workshop on ML: ML'09, pp. 61–70.Google Scholar
[36] Ceccherini-Silberstein, T. and Woess, W. (2002) Growth and ergodicity of context-free languages. Trans. Amer. Math. Soc. 354 4597–4625.Google Scholar
[37] Ceccherini-Silberstein, T. and Woess, W. (2003) Growth-sensitivity of context-free languages. Theoret. Comput. Sci. 307 103–116.Google Scholar
[38] Ceccherini-Silberstein, T. and Woess, W. (2012) Context-free pairs of groups I: Context-free pairs and graphs. European J. Combin. 33 1449–1466.Google Scholar
[39] Chomsky, N. and Schützenberger, M.-P. (1963) The algebraic theory of context-free languages. Computer Programming and Formal Systems, Vol. 26 of Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 118–161.Google Scholar
[40] Christol, G., Kamae, T., Mendès France, M. and Rauzy, G. (1980) Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108 401–419.Google Scholar
[41] Chudnovsky, D. V. and Chudnovsky, G. V. (1987) On expansion of algebraic functions in power and Puiseux series II. J. Complexity 3 1–25.Google Scholar
[42] Clote, P., Ponty, Y. and Steyaert, J.-M. (2012) Expected distance between terminal nucleotides of RNA secondary structures. J. Math. Biol. 65 581–599.Google Scholar
[43] Cockle, J. (1861) On transcendental and algebraic solution. Philos. Mag. XXI 379–383.Google Scholar
[44] Comtet, L. (1964) Calcul pratique des coefficients de Taylor d'une fonction algébrique. Enseignement Math. (2) 10 267–270.Google Scholar
[45] Comtet, L. (1974) Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel. Enlarged edition of the two volumes Analyse Combinatoire published in French in 1970 by Presses Universitaires de France.Google Scholar
[46] Darrasse, A. (2008) Random XML sampling the Boltzmann way. arXiv:0807.0992v1 Google Scholar
[47] Delest, M. (1996) Algebraic languages: A bridge between combinatorics and computer science. In Formal Power Series and Algebraic Combinatorics 1994, Vol. 24 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, pp. 71–87.Google Scholar
[48] Delest, M.-P. and Viennot, G. (1984) Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci. 34 169–206.Google Scholar
[49] Denef, J. and Lipshitz, L. (1984) Power series solutions of algebraic differential equations. Math. Ann. 267 213–238.Google Scholar
[50] Denise, A., Ponty, Y. and Termier, M. (2003) Random generation of structured genomic sequences (poster). RECOMB'2003, Berlin, April 2003.Google Scholar
[51] Denise, A. and Zimmermann, P. (1999) Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci. 218 233–248.Google Scholar
[52] Drmota, M. (1994) Asymptotic distributions and a multivariate Darboux method in enumeration problems. J. Combin. Theory Ser. A 67 169–184.Google Scholar
[53] Drmota, M. (1997) Systems of functional equations. Random Struct. Alg. 10 103–124.Google Scholar
[54] Drmota, M. (2009) Random Trees: An Interplay Between Combinatorics and Probability, Springer.Google Scholar
[55] Drmota, M., Gittenberger, B. and Morgenbesser, J. F. (2012) Infinite systems of functional equations and Gaussian limiting distributions. In 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms: AofA'12, DMTCS Proc. AQ, pp. 453–478.Google Scholar
[56] Drmota, M. and Soria, M. (1995) Marking in combinatorial constructions: Generating functions and limiting distributions. Theor. Comput. Sci. 144 67–99.Google Scholar
[57] Droste, M., Kuich, W. and Vogler, H., eds (2009) Handbook of Weighted Automata, Monographs in Theoretical Computer Science, Springer.Google Scholar
[58] Duchon, P. (1999) q-grammars and wall polyominoes. Ann. Combin. 3 311–321.Google Scholar
[59] Duchon, P. (2000) On the enumeration and generation of generalized Dyck words. Discrete Math. 225 121–135.Google Scholar
[60] Duchon, P., Flajolet, P., Louchard, G. and Schaeffer, G. (2004) Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput. 13 577–625.Google Scholar
[61] Flajolet, P. (1987) Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci. 49 283–309.Google Scholar
[62] Flajolet, P. and Noy, M. (1999) Analytic combinatorics of non-crossing configurations. Discrete Math. 204 203–229.Google Scholar
[63] Flajolet, P. and Odlyzko, A. (1990) Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216–240.Google Scholar
[64] Flajolet, P., Pelletier, M. and Soria, M. (2011) On Buffon machines and numbers. In Proc. Twenty-Second Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, pp. 172–183.Google Scholar
[65] Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[66] Flajolet, P., Zimmerman, P. and Van Cutsem, B. (1994) A calculus for the random generation of labelled combinatorial structures. Theoret. Comput. Sci. 132 1–35.Google Scholar
[67] Furstenberg, H. (1967) Algebraic functions over finite fields. J. Algebra 7 271–277.Google Scholar
[68] Goulden, I. P and Jackson, D. M. (2004) Combinatorial Enumeration, Dover. Reprint of the 1983 original.Google Scholar
[69] Grigorchuk, R. and de la Harpe, P. (1997) On problems related to growth, entropy, and spectrum in group theory. J. Dynam. Control Systems 3 51–89.Google Scholar
[70] Harley, R. (1862) On the theory of the transcendental solution of algebraic equations. Quart. J. Pure Appl. Math. 5 337–361.Google Scholar
[71] Harris, W. A. Jr and Sibuya, Y. (1985) The reciprocals of solutions of linear ordinary differential equations. Adv. Math. 58 119–132.CrossRefGoogle Scholar
[72] Hickey, T. and Cohen, J. (1983) Uniform random generation of strings in a context-free language. SIAM J. Comput. 12 645–655.Google Scholar
[73] Joyal, A. (1981) Une théorie combinatoire des séries formelles. Adv. Math. 42 1–82.Google Scholar
[74] Jungen, R. (1931) Sur les séries de Taylor n'ayant que des singularités algébrico-logarithmiques sur leur cercle de convergence. Comment. Math. Helv. 3 266–306.Google Scholar
[75] Kauers, M., Jaroschek, M. and Johansson, F. (2014) Ore polynomials in Sage. arXiv:1306.4263 In: Computer Algebra and Polynomials, Jaime Gutierrez, Josef Schicho, Martin Weimann (ed.), Lecture Notes in Computer Science, to appear.Google Scholar
[76] Kauers, M. and Pillwein, V. (2010) When can we decide that a p-finite sequence is positive? In Proc. ISSAC'10, pp. 195–202. arXiv:1005.0600 Google Scholar
[77] Kemp, R. (1980) A note on the density of inherently ambiguous context-free languages. Acta Inform. 14 295–298.CrossRefGoogle Scholar
[78] Kemp, R. (1993) Random multidimensional binary trees. J. Information Processing and Cybernetics (Elektron. Inform. Kybernet.) 29 9–36.Google Scholar
[79] Kleene, S. C. (1956) Representation of events in nerve nets and finite automata. In Automata Studies, Vol. 34 of Annals of Mathematics Studies, Princeton University Press, pp. 3–41.Google Scholar
[80] Knuth, D. E. (1998) The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, third edition, Addison-Wesley.Google Scholar
[81] Kontsevich, M. (2011) Noncommutative identities. arXiv:1109.2469v1 Google Scholar
[82] Koutschan, C. (2008) Regular languages and their generating functions: The inverse problem. Theoret. Comput. Sci. 391 65–74.Google Scholar
[83] Lagrange, J.-L. (1770) Nouvelle méthode pour résoudre les équations littérales par le moyen des séries. Histoire de l'Académie Royale des Sciences et des Belles Lettres de Berlin avec les Mémoires Tirez des Registres de Cette Académie XXIV 251–326. Reprinted in Joseph Louis de Lagrange: Œuvres Complètes, Vol. 3, Gauthier-Villars (1869), pp. 5–73.Google Scholar
[84] Lalley, S. P. (1993) Finite range random walk on free groups and homogeneous trees. Ann. Probab. 21 571–599.Google Scholar
[85] Lalley, S. P. (2004) Algebraic systems of generating functions and return probabilities for random walks. In Dynamics and Randomness II, Vol. 10 of Nonlinear Phenom. Complex Systems, Kluwer, pp. 81–122.Google Scholar
[86] Lang, W. (2000) On generalizations of the Stirling number triangles. J. Integer Seq. 3 #00.2.4.Google Scholar
[87] Lothaire, M. (2005) Applied Combinatorics on Words, Vol. 105 of Encyclopedia of Mathematics and its Applications, Cambridge University Press.Google Scholar
[88] Mansour, T. and Shattuck, M. (2011) Pattern avoiding partitions, sequence A054391 and the kernel method. Appl. Appl. Math. 6 397–411.Google Scholar
[89] Meir, A. and Moon, J. W. (1978) On the altitude of nodes in random trees. Canad. J. Math. 30 997–1015.Google Scholar
[90] Morcrette, B. (2012) Fully analyzing an algebraic Pólya urn model. In Proc. LATIN 2012, Vol. 7256 of Lecture Notes in Computer Science, Springer, pp. 568–581.Google Scholar
[91] Morgenbesser, J. F. (2010) Square root singularities of infinite systems of functional equations. In 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms: AofA'10, DMTCS Proc. AM, pp. 513–525.Google Scholar
[92] Muller, D. E. and Schupp, P. E. (1981) Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems. Bull. Amer. Math. Soc. (NS) 4 331–334.Google Scholar
[93] Pak, I. and Garrabrant, S. (2014) Counting with irrational tiles. Preprint.Google Scholar
[94] Panholzer, A. (2005) Gröbner bases and the defining polynomial of a context-free grammar generating function. J. Autom. Lang. Combin. 10 79–97.Google Scholar
[95] Petre, I. and Salomaa, A. (2009) Algebraic systems and pushdown automata. Chapter 7 of Handbook of Weighted Automata (Droste, M. et al., eds), Monographs in Theoretical Computer Science, Springer, pp. 257–289.Google Scholar
[96] Pevzner, P. A. and Waterman, M. S. (1995) Open combinatorial problems in computational molecular biology. In Third Israel Symposium on the Theory of Computing and Systems, IEEE Computer Society Press, pp. 158–173.Google Scholar
[97] Pivoteau, C., Salvy, B. and Soria, M. (2012) Algorithms for combinatorial structures: Well-founded systems and Newton iterations. J. Combin. Theory Ser. A 119 1711–1773.Google Scholar
[98] Reutenauer, C. and Robado, M. (2012) On an algebraicity theorem of Kontsevich. In Proc. FPSAC '2012, DMTCS Proc. AR, pp. 239–246.Google Scholar
[99] Richard, C. (2009) Limit distributions and scaling functions. Polygons, Polyominoes and Polycubes, Vol. 775 of Lecture Notes in Physics, Springer, pp. 247–299.Google Scholar
[100] Rozenberg, G. and Salomaa, A., eds (1997) Handbook of Formal Languages (three volumes), Springer.Google Scholar
[101] Salomaa, A. (1990) Formal languages and power series. In Handbook of Theoretical Computer Science, Vol. B, Elsevier, pp. 103–132.Google Scholar
[102] Salomaa, A. and Soittola, M. (1978) Automata-Theoretic Aspects of Formal Power Series, Texts and Monographs in Computer Science, Springer.Google Scholar
[103] Schneider, C. (2010) A symbolic summation approach to find optimal nested sum representations. In Motives, Quantum Field Theory, and Pseudodifferential Operators, Vol. 12 of Clay Mathematics Proceedings, AMS, pp. 285–308.Google Scholar
[104] Schützenberger, M.-P. (1962) On a theorem of R. Jungen. Proc. Amer. Math. Soc. 13 885–890.Google Scholar
[105] Schwarz, H. A. (1872) On these cases in which the Gaussian hypergeometric series represents an algebraic function of its fourth element. (Ueber diejenigen Fälle, in welchen die Gauss'sche hypergeometrische Reihe eine algebraische Function ihres vierten Elementes darstellt.) J. Reine Angewandte Mathematik LXXV 292–335.Google Scholar
[106] Singer, M. F. (1980) Algebraic solutions of nth order linear differential equations. In Proc. Queen's Number Theory Conference 1979, Vol. 54 of Queen's Papers in Pure and Applied Mathematics, Queen's University, Kingston, Ontario, pp. 379–420.Google Scholar
[107] Singer, M. F. (1986) Algebraic relations among solutions of linear differential equations. Trans. Amer. Math. Soc. 295 753–763.CrossRefGoogle Scholar
[108] Soittola, M. (1976) Positive rational sequences. Theoret. Comput. Sci. 2 317–322.Google Scholar
[109] Sokal, A. D. (2009/10) A ridiculously simple and explicit implicit function theorem. Sém. Lothar. Combin. 61A #B61Ad, 21.Google Scholar
[110] Stanley, R. P. (1999) Enumerative Combinatorics 2, Vol. 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[111] Sturmfels, B. (2002) Solving Systems of Polynomial Equations, Vol. 97 of CBMS Regional Conference Series in Mathematics, Conference Board of the Mathematical Sciences.Google Scholar
[112] Tafat Bouzid, H. (2012) Combinatoire analytique des langages réguliers et algébriques. PhD thesis, Université Paris-XIII.Google Scholar
[113] Tannery, J. (1874) Propriétés des intégrales des équations différentielles linéaires à coefficients variables. Doctoral thesis, Faculté des Sciences de Paris. http://gallica.bnf.fr Google Scholar
[114] Trèves, F. (2006) Topological Vector Spaces, Distributions and Kernels, Dover. Unabridged republication of the 1967 original.Google Scholar
[115] van der Poorten, A. J. (1989) Some facts that should be better known, especially about rational functions. In Number Theory and Applications 1988, Vol. 265 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Kluwer, pp. 497–528.Google Scholar
[116] van Leeuwen, J., ed. (1990) Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics, Elsevier.Google Scholar
[117] Viennot, G. (1985) Enumerative combinatorics and algebraic languages. In Fundamentals of Computation Theory 1985, Vol. 199 of Lecture Notes in Computer Science, Springer, pp. 450–464.Google Scholar
[118] Waterman, M. S. (1995) Applications of combinatorics to molecular biology. Chapter 39 of Handbook of Combinatorics, Vols 1, 2, Elsevier, pp. 1983–2001.Google Scholar
[119] Weinberg, F. and Nebel, M. E. (2010) Extending stochastic context-free grammars for an application in bioinformatics. In Language and Automata Theory and Applications, Vol. 6031 of Lecture Notes in Computer Science, Springer, pp. 585–595.Google Scholar
[120] Woess, W. (2012) Context-free pairs of groups II: Cuts, tree sets, and random walks. Discrete Math. 312 157–173.Google Scholar
[121] Woods, A. R. (1997) Coloring rules for finite trees, and probabilities of monadic second order sentences. Random Struct. Alg. 10 453–485.Google Scholar