No CrossRef data available.
Article contents
Formulae and Asymptotics for Coefficients of Algebraic Functions
Published online by Cambridge University Press: 11 December 2014
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
We study the coefficients of algebraic functions∑n≥0f nzn. First, we recall the too-little-known fact that these coefficientsf n always admit a closed form. Then we study their asymptotics, known to beof the type f n ~ CA nn α. When the function is a power seriesassociated to a context-free grammar, we solve a folklore conjecture: thecritical exponents α cannot be 1/3 or −5/2; they in factbelong to a proper subset of the dyadic numbers. We initiate the study of theset of possible values for A. We extend what Philippe Flajoletcalled the Drmota–Lalley–Woods theorem (which states thatα=−3/2 when the dependency graph associated to thealgebraic system defining the function is strongly connected). We fullycharacterize the possible singular behaviours in the non-strongly connectedcase. As a corollary, the generating functions of certain lattice paths andplanar maps are not determined by a context-free grammar (i.e.,their generating functions are not ℕ-algebraic). We give examples ofGaussian limit laws (beyond the case of theDrmota–Lalley–Woods theorem), and examples of non-Gaussianlimit laws. We then extend our work to systems involving non-polynomial entirefunctions (non-strongly connected systems, fixed points of entire functions withpositive coefficients). We give several closure properties forℕ-algebraic functions. We end by discussing a few extensions of ourresults (infinite systems of equations, algorithmic aspects).
Information
- 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
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
[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
[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
[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
[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
You have
Access
- 36
- Cited by