×

Formulae and asymptotics for coefficients of algebraic functions. (English) Zbl 1371.05009

Summary: We study the coefficients of algebraic functions \(\sum_{n\geq0}f_nz^n\). First, we recall the too-little-known fact that these coefficients \(f_n\) always admit a closed form. Then we study their asymptotics, known to be of the type \(f_n\sim {CA}^nn^\alpha\). When the function is a power series associated to a context-free grammar, we solve a folklore conjecture: the critical exponents \(\alpha\) 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 \(\alpha=-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 \(\mathbb{N}\)-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 \(\mathbb{N}\)-algebraic functions. We end by discussing a few extensions of our results (infinite systems of equations, algorithmic aspects).

MSC:

05A15 Exact enumeration problems, generating functions
05A16 Asymptotic enumeration
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [1]AbelN. H. (1992) Œuvres Complètes, Vol. II, Éditions J. Gabay, Sceaux. Reprint of the second edition of 1881.
[2] [2]AdamczewskiB. and BellJ. P. (2012) On vanishing coefficients of algebraic power series over fields of positive characteristic. Inventio Math.187343-393.10.1007/s00222-011-0337-4 · Zbl 1257.11027 · doi:10.1007/s00222-011-0337-4
[3] [3]AlbertM. H. and AtkinsonM. D. (2005) Simple permutations and pattern restricted permutations. Discrete Math.3001-15.10.1016/j.disc.2005.06.016 · Zbl 1073.05002 · doi:10.1016/j.disc.2005.06.016
[4] [4]AlloucheJ.-P. and ShallitJ. (2003) Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press. · Zbl 1086.11015
[5] [5]AutebertJ.-M., FlajoletP. and GabarróJ. (1987) Prefixes of infinite words and ambiguous context-free languages. Inform. Process. Lett.25211-216.10.1016/0020-0190(87)90162-1 · Zbl 0653.68076 · doi:10.1016/0020-0190(87)90162-1
[6] [6]BanderierC. (2001) Combinatoire analytique des chemins et des cartes. PhD thesis, Université Paris-VI.
[7] [7]BanderierC. (2002) Limit laws for basic parameters of lattice paths with unbounded jumps. In Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities (B.Chauvinet al., eds), Trends in Mathematics, Birkhäuser, pp. 33-47.10.1007/978-3-0348-8211-8 · Zbl 1024.60004 · doi:10.1007/978-3-0348-8211-8
[8] [8]BanderierC., BodiniO., PontyY. and TafatH. (2012) On the diversity of pattern distributions in combinatorial systems. In Proc. Analytic Algorithmics and Combinatorics: ANALCO’12, SIAM, pp. 107-116.
[9] [9]BanderierC., Bousquet-MélouM., DeniseA., FlajoletP., GardyG. and Gouyou-BeauchampsD. (2002) Generating functions for generating trees. Discrete Math.24629-55.10.1016/S0012-365X(01)00250-3 · Zbl 0997.05007 · doi:10.1016/S0012-365X(01)00250-3
[10] [10]BanderierC. and FlajoletP. (2002) Basic analytic combinatorics of directed lattice paths. Theoret. Comput. Sci.28137-80.10.1016/S0304-3975(02)00007-5 · Zbl 0996.68126 · doi:10.1016/S0304-3975(02)00007-5
[11] [11]BanderierC., FlajoletP., SchaefferG. and SoriaM. (2001) Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Struct. Alg.19194-246.10.1002/rsa.10021 · Zbl 1016.68179 · doi:10.1002/rsa.10021
[12] [12]BanderierC. and GittenbergerB. (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. · Zbl 1190.05003
[13] [13]BanderierC. and HitczenkoP. (2012) Enumeration and asymptotics of restricted compositions having the same number of parts. Discrete Appl. Math.1602542-2554.10.1016/j.dam.2011.12.011 · Zbl 1254.05012 · doi:10.1016/j.dam.2011.12.011
[14] [14]BanderierC. and MerliniD. (2002) Lattice paths with an infinite set of jumps. In Proc. FPSAC 2002.
[15] [15]BanderierC. and SchwerS. (2005) Why Delannoy numbers?J. Statist. Plann. Inference13540-54.10.1016/j.jspi.2005.02.004 · Zbl 1074.01012 · doi:10.1016/j.jspi.2005.02.004
[16] [16]BarcucciE., Del LungoA., FrosiniA. and RinaldiS. (2001) A technology for reverse-engineering a combinatorial problem from a rational generating function. Adv. Appl. Math.26129-153.10.1006/aama.2000.0711 · Zbl 0984.05005 · doi:10.1006/aama.2000.0711
[17] [17]BassinoF., BouvelM., PivoteauC., PierrotA. and RossinD. (2012) Combinatorial specification of permutation classes. In Proc. FPSAC ’2012, DMTCS Proc. AR, pp. 791-802.
[18] [18]BéalM.-P., BlockletM. and DimaC. (2014) Zeta functions of finite-type-Dyck shifts are ℕ-algebraic. In Proc. 2014 Information Theory and Applications Workshop, IEEE.
[19] [19]BellJ. P., BurrisS. N. and YeatsK. (2012) On the set of zero coefficients of a function satisfying a linear differential equation. Math. Proc. Cambridge Philos. Soc.153235-247.10.1017/S0305004112000114 · Zbl 1264.11005 · doi:10.1017/S0305004112000114
[20] [20]BergeronF., LabelleG. and LerouxP. (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. · Zbl 0888.05001
[21] [21]BerstelJ. (1971) Sur les pôles et le quotient de Hadamard de séries ℕ-rationnelles. CR Acad. Sci. Paris Sér. A-B272A1079-A1081. · Zbl 0263.13004
[22] [22]BerstelJ. and BoassonL. (1996) Towards an algebraic theory of context-free languages. Fund. Inform.25217-239. · Zbl 0843.68050
[23] [23]BerstelJ. and ReutenauerC. (2011) Noncommutative Rational Series with Applications, Vol. 137 of Encyclopedia of Mathematics and its Applications, Cambridge University Press. · Zbl 1250.68007
[24] [24]BertoniA., GoldwurmM. and SantiniM. (2001) Random generation for finitely ambiguous context-free languages. Theor. Inform. Appl.35499-512.10.1051/ita:2001128 · Zbl 1005.68091 · doi:10.1051/ita:2001128
[25] [25]BeukersF. and HeckmanG. (1989) Monodromy for the hypergeometric function_nF_n-1. Inventio Math.95325-354.10.1007/BF01393900 · Zbl 0663.30044 · doi:10.1007/BF01393900
[26] [26]BodiniO., DarrasseA. and SoriaM. (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. · Zbl 1393.05247
[27] [27]BodiniO. and PontyY. (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. · Zbl 1355.68151
[28] [28]BostanA., ChyzakF., LecerfG., SalvyB. and SchostE. (2007) Differential equations for algebraic functions. In Proc. ISSAC 2007, ACM, pp. 25-32. · Zbl 1190.68085
[29] [29]BostanA. and KauersM. (2009) Automatic classification of restricted lattice walks. In Proc. FPSAC ’09 (C.Krattenthaler, V.Strehl and M.Kauers, eds), pp. 201-215. · Zbl 1391.05026
[30] [30]BostanA. and KauersM. (2010) The complete generating function for Gessel walks is algebraic. Proc. Amer. Math. Soc.1383063-3078.10.1090/S0002-9939-2010-10398-2 · Zbl 1206.05013 · doi:10.1090/S0002-9939-2010-10398-2
[31] [31]BostanA., LairezP. and SalvyB. (2014) Integral representations of binomial sums. In preparation.
[32] [32]Bousquet-MélouM. (2006) Rational and algebraic series in combinatorial enumeration. In Proc. International Congress of Mathematicians, Vol. III, European Mathematical Society, pp. 789-826. · Zbl 1101.05004
[33] [33]Bousquet-MélouM. and JehanneA. (2006) Polynomial equations with one catalytic variable, algebraic series and map enumeration. J. Combin. Theory Ser. B96623-672.10.1016/j.jctb.2005.12.003 · Zbl 1099.05043 · doi:10.1016/j.jctb.2005.12.003
[34] [34]Bousquet-MélouM. and SchaefferG. (2002) Walks on the slit plane. Probab. Theory Rel. Fields124305-344.10.1007/s004400200205 · Zbl 1008.05006 · doi:10.1007/s004400200205
[35] [35]CanouB. and DarrasseA. (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.
[36] [36]Ceccherini-SilbersteinT. and WoessW. (2002) Growth and ergodicity of context-free languages. Trans. Amer. Math. Soc.3544597-4625.10.1090/S0002-9947-02-03048-9 · Zbl 1016.68047 · doi:10.1090/S0002-9947-02-03048-9
[37] [37]Ceccherini-SilbersteinT. and WoessW. (2003) Growth-sensitivity of context-free languages. Theoret. Comput. Sci.307103-116.10.1016/S0304-3975(03)00095-1 · Zbl 1059.68056 · doi:10.1016/S0304-3975(03)00095-1
[38] [38]Ceccherini-SilbersteinT. and WoessW. (2012) Context-free pairs of groups I: Context-free pairs and graphs. European J. Combin.331449-1466.10.1016/j.ejc.2012.03.011 · Zbl 1279.68140 · doi:10.1016/j.ejc.2012.03.011
[39] [39]ChomskyN. and SchützenbergerM.-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. · Zbl 0148.00804
[40] [40]ChristolG., KamaeT., Mendès FranceM. and RauzyG. (1980) Suites algébriques, automates et substitutions. Bull. Soc. Math. France108401-419. · Zbl 0472.10035
[41] [41]ChudnovskyD. V. and ChudnovskyG. V. (1987) On expansion of algebraic functions in power and Puiseux series II. J. Complexity31-25.10.1016/0885-064X(87)90002-1 · Zbl 0656.34003 · doi:10.1016/0885-064X(87)90002-1
[42] [42]CloteP., PontyY. and SteyaertJ.-M. (2012) Expected distance between terminal nucleotides of RNA secondary structures. J. Math. Biol.65581-599.10.1007/s00285-011-0467-821984358 · Zbl 1304.05073 · doi:10.1007/s00285-011-0467-8
[43] [43]CockleJ. (1861) On transcendental and algebraic solution. Philos. Mag.XXI379-383.
[44] [44]ComtetL. (1964) Calcul pratique des coefficients de Taylor d’une fonction algébrique. Enseignement Math.(2)10267-270. · Zbl 0166.41702
[45] [45]ComtetL. (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. · Zbl 0283.05001
[46] [46]DarrasseA. (2008) Random XML sampling the Boltzmann way. arXiv:0807.0992v1
[47] [47]DelestM. (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. · Zbl 0841.05003
[48] [48]DelestM.-P. and ViennotG. (1984) Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci.34169-206.10.1016/0304-3975(84)90116-6 · Zbl 0985.68516 · doi:10.1016/0304-3975(84)90116-6
[49] [49]DenefJ. and LipshitzL. (1984) Power series solutions of algebraic differential equations. Math. Ann.267213-238.10.1007/BF01579200 · Zbl 0518.12015 · doi:10.1007/BF01579200
[50] [50]DeniseA., PontyY. and TermierM. (2003) Random generation of structured genomic sequences (poster). RECOMB’2003, Berlin, April 2003.
[51] [51]DeniseA. and ZimmermannP. (1999) Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci.218233-248.10.1016/S0304-3975(98)00323-5 · Zbl 0933.68154 · doi:10.1016/S0304-3975(98)00323-5
[52] [52]DrmotaM. (1994) Asymptotic distributions and a multivariate Darboux method in enumeration problems. J. Combin. Theory Ser. A67169-184.10.1016/0097-3165(94)90011-6 · Zbl 0801.60016 · doi:10.1016/0097-3165(94)90011-6
[53] [53]DrmotaM. (1997) Systems of functional equations. Random Struct. Alg.10103-124.10.1002/(SICI)1098-2418(199701/03)10:1/2<103::AID-RSA5>3.3.CO;2-0 · Zbl 0869.39010 · doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<103::AID-RSA5>3.3.CO;2-0
[54] [54]DrmotaM. (2009) Random Trees: An Interplay Between Combinatorics and Probability, Springer. · Zbl 1170.05022
[55] [55]DrmotaM., GittenbergerB. and MorgenbesserJ. 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. · Zbl 1296.60011
[56] [56]DrmotaM. and SoriaM. (1995) Marking in combinatorial constructions: Generating functions and limiting distributions. Theor. Comput. Sci.14467-99.10.1016/0304-3975(94)00294-S · Zbl 0874.68143 · doi:10.1016/0304-3975(94)00294-S
[57] [57]DrosteM., KuichW. and VoglerH., eds (2009) Handbook of Weighted Automata, Monographs in Theoretical Computer Science, Springer. · Zbl 1200.68001
[58] [58]DuchonP. (1999) q-grammars and wall polyominoes. Ann. Combin.3311-321.10.1007/BF01608790 · Zbl 0939.05025 · doi:10.1007/BF01608790
[59] [59]DuchonP. (2000) On the enumeration and generation of generalized Dyck words. Discrete Math.225121-135.10.1016/S0012-365X(00)00150-3 · Zbl 0971.68090 · doi:10.1016/S0012-365X(00)00150-3
[60] [60]DuchonP., FlajoletP., LouchardG. and SchaefferG. (2004) Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput.13577-625.10.1017/S0963548304006315 · Zbl 1081.65007 · doi:10.1017/S0963548304006315
[61] [61]FlajoletP. (1987) Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci.49283-309.10.1016/0304-3975(87)90011-9 · Zbl 0612.68069 · doi:10.1016/0304-3975(87)90011-9
[62] [62]FlajoletP. and NoyM. (1999) Analytic combinatorics of non-crossing configurations. Discrete Math.204203-229.10.1016/S0012-365X(98)00372-0 · Zbl 0939.05005 · doi:10.1016/S0012-365X(98)00372-0
[63] [63]FlajoletP. and OdlyzkoA. (1990) Singularity analysis of generating functions. SIAM J. Discrete Math.3216-240.10.1137/0403019 · Zbl 0712.05004 · doi:10.1137/0403019
[64] [64]FlajoletP., PelletierM. and SoriaM. (2011) On Buffon machines and numbers. In Proc. Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp. 172-183. · Zbl 1373.68219
[65] [65]FlajoletP. and SedgewickR. (2009) Analytic Combinatorics, Cambridge University Press. · Zbl 1165.05001
[66] [66]FlajoletP., ZimmermanP. and Van CutsemB. (1994) A calculus for the random generation of labelled combinatorial structures. Theoret. Comput. Sci.1321-35.10.1016/0304-3975(94)90226-7 · Zbl 0799.68143 · doi:10.1016/0304-3975(94)90226-7
[67] [67]FurstenbergH. (1967) Algebraic functions over finite fields. J. Algebra7271-277.10.1016/0021-8693(67)90061-0 · Zbl 0175.03903 · doi:10.1016/0021-8693(67)90061-0
[68] [68]GouldenI. P and JacksonD. M. (2004) Combinatorial Enumeration, Dover. Reprint of the 1983 original.
[69] [69]GrigorchukR. and de la HarpeP. (1997) On problems related to growth, entropy, and spectrum in group theory. J. Dynam. Control Systems351-89.10.1007/BF02471762 · Zbl 0949.20033 · doi:10.1007/BF02471762
[70] [70]HarleyR. (1862) On the theory of the transcendental solution of algebraic equations. Quart. J. Pure Appl. Math.5337-361.
[71] [71]HarrisW. A.Jr and SibuyaY. (1985) The reciprocals of solutions of linear ordinary differential equations. Adv. Math.58119-132.10.1016/0001-8708(85)90113-6 · Zbl 0581.12013 · doi:10.1016/0001-8708(85)90113-6
[72] [72]HickeyT. and CohenJ. (1983) Uniform random generation of strings in a context-free language. SIAM J. Comput.12645-655. · Zbl 0524.68046
[73] [73]JoyalA. (1981) Une théorie combinatoire des séries formelles. Adv. Math.421-82.10.1016/0001-8708(81)90052-9 · Zbl 0491.05007 · doi:10.1016/0001-8708(81)90052-9
[74] [74]JungenR. (1931) Sur les séries de Taylor n’ayant que des singularités algébrico-logarithmiques sur leur cercle de convergence. Comment. Math. Helv.3266-306.10.1007/BF01601817 · Zbl 0003.11901 · doi:10.1007/BF01601817
[75] [75]KauersM., JaroschekM. and JohanssonF. (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.
[76] [76]KauersM. and PillweinV. (2010) When can we decide that a p-finite sequence is positive? In Proc. ISSAC’10, pp. 195-202. arXiv:1005.0600
[77] [77]KempR. (1980) A note on the density of inherently ambiguous context-free languages. Acta Inform.14295-298.10.1007/BF00264258 · Zbl 0441.68085 · doi:10.1007/BF00264258
[78] [78]KempR. (1993) Random multidimensional binary trees. J. Information Processing and Cybernetics (Elektron. Inform. Kybernet.)299-36. · Zbl 0787.68026
[79] [79]KleeneS. 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.
[80] [80]KnuthD. E. (1998) The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, third edition, Addison-Wesley. · Zbl 0895.65001
[81] [81]KontsevichM. (2011) Noncommutative identities. arXiv:1109.2469v1
[82] [82]KoutschanC. (2008) Regular languages and their generating functions: The inverse problem. Theoret. Comput. Sci.39165-74.10.1016/j.tcs.2007.10.031 · Zbl 1133.68039 · doi:10.1016/j.tcs.2007.10.031
[83] [83]LagrangeJ.-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émieXXIV251-326. Reprinted in Joseph Louis de Lagrange: Œuvres Complètes, Vol. 3, Gauthier-Villars (1869), pp. 5-73.
[84] [84]LalleyS. P. (1993) Finite range random walk on free groups and homogeneous trees. Ann. Probab.21571-599. · Zbl 0804.60006
[85] [85]LalleyS. 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. · Zbl 1086.60026
[86] [86]LangW. (2000) On generalizations of the Stirling number triangles. J. Integer Seq.3 #00.2.4. · Zbl 0954.11010
[87] [87]LothaireM. (2005) Applied Combinatorics on Words, Vol. 105 of Encyclopedia of Mathematics and its Applications, Cambridge University Press. · Zbl 1133.68067
[88] [88]MansourT. and ShattuckM. (2011) Pattern avoiding partitions, sequence A054391 and the kernel method. Appl. Appl. Math.6397-411. · Zbl 1301.05023
[89] [89]MeirA. and MoonJ. W. (1978) On the altitude of nodes in random trees. Canad. J. Math.30997-1015.10.4153/CJM-1978-085-0 · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0
[90] [90]MorcretteB. (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. · Zbl 1354.05008
[91] [91]MorgenbesserJ. 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. · Zbl 1357.39016
[92] [92]MullerD. E. and SchuppP. 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) 4331-334.10.1090/S0273-0979-1981-14904-1 · Zbl 0484.03019 · doi:10.1090/S0273-0979-1981-14904-1
[93] [93]PakI. and GarrabrantS. (2014) Counting with irrational tiles. Preprint.
[94] [94]PanholzerA. (2005) Gröbner bases and the defining polynomial of a context-free grammar generating function. J. Autom. Lang. Combin.1079-97. · Zbl 1087.68046
[95] [95]PetreI. and SalomaaA. (2009) Algebraic systems and pushdown automata. Chapter 7 of Handbook of Weighted Automata (M.Drosteet al., eds), Monographs in Theoretical Computer Science, Springer, pp. 257-289.10.1007/978-3-642-01492-5 · Zbl 1200.68001 · doi:10.1007/978-3-642-01492-5
[96] [96]PevznerP. A. and WatermanM. 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.
[97] [97]PivoteauC., SalvyB. and SoriaM. (2012) Algorithms for combinatorial structures: Well-founded systems and Newton iterations. J. Combin. Theory Ser. A1191711-1773.10.1016/j.jcta.2012.05.007 · Zbl 1246.05012 · doi:10.1016/j.jcta.2012.05.007
[98] [98]ReutenauerC. and RobadoM. (2012) On an algebraicity theorem of Kontsevich. In Proc. FPSAC ’2012, DMTCS Proc. AR, pp. 239-246. · Zbl 1412.05221
[99] [99]RichardC. (2009) Limit distributions and scaling functions. Polygons, Polyominoes and Polycubes, Vol. 775 of Lecture Notes in Physics, Springer, pp. 247-299. · Zbl 1180.82089
[100] [100]RozenbergG. and SalomaaA., eds (1997) Handbook of Formal Languages (three volumes), Springer. · Zbl 0866.68057
[101] [101]SalomaaA. (1990) Formal languages and power series. In Handbook of Theoretical Computer Science, Vol. B, Elsevier, pp. 103-132. · Zbl 0900.68287
[102] [102]SalomaaA. and SoittolaM. (1978) Automata-Theoretic Aspects of Formal Power Series, Texts and Monographs in Computer Science, Springer. · Zbl 0377.68039
[103] [103]SchneiderC. (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. · Zbl 1225.33031
[104] [104]SchützenbergerM.-P. (1962) On a theorem of R. Jungen. Proc. Amer. Math. Soc.13885-890.10.1090/S0002-9939-1962-0142781-7 · Zbl 0107.03102 · doi:10.1090/S0002-9939-1962-0142781-7
[105] [105]SchwarzH. 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 MathematikLXXV292-335. · JFM 05.0146.03
[106] [106]SingerM. 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. · Zbl 0453.12010
[107] [107]SingerM. F. (1986) Algebraic relations among solutions of linear differential equations. Trans. Amer. Math. Soc.295753-763.10.1090/S0002-9947-1986-0833707-X · Zbl 0593.12014 · doi:10.1090/S0002-9947-1986-0833707-X
[108] [108]SoittolaM. (1976) Positive rational sequences. Theoret. Comput. Sci.2317-322.10.1016/0304-3975(76)90084-0 · Zbl 0341.68056 · doi:10.1016/0304-3975(76)90084-0
[109] [109]SokalA. D. (2009/10) A ridiculously simple and explicit implicit function theorem. Sém. Lothar. Combin.61A #B61Ad, 21. · Zbl 1182.30006
[110] [110]StanleyR. P. (1999) Enumerative Combinatorics 2, Vol. 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press. · Zbl 0928.05001
[111] [111]SturmfelsB. (2002) Solving Systems of Polynomial Equations, Vol. 97 of CBMS Regional Conference Series in Mathematics, Conference Board of the Mathematical Sciences. · Zbl 1101.13040
[112] [112]Tafat BouzidH. (2012) Combinatoire analytique des langages réguliers et algébriques. PhD thesis, Université Paris-XIII.
[113] [113]TanneryJ. (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
[114] [114]TrèvesF. (2006) Topological Vector Spaces, Distributions and Kernels, Dover. Unabridged republication of the 1967 original. · Zbl 1111.46001
[115] [115]van der PoortenA. 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. · Zbl 0687.10007
[116] [116]van LeeuwenJ., ed. (1990) Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics, Elsevier. · Zbl 0712.68054
[117] [117]ViennotG. (1985) Enumerative combinatorics and algebraic languages. In Fundamentals of Computation Theory 1985, Vol. 199 of Lecture Notes in Computer Science, Springer, pp. 450-464. · Zbl 0604.68081
[118] [118]WatermanM. S. (1995) Applications of combinatorics to molecular biology. Chapter 39 of Handbook of Combinatorics, Vols 1, 2, Elsevier, pp. 1983-2001. · Zbl 0842.92011
[119] [119]WeinbergF. and NebelM. 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. · Zbl 1284.68336
[120] [120]WoessW. (2012) Context-free pairs of groups II: Cuts, tree sets, and random walks. Discrete Math.312157-173.10.1016/j.disc.2011.07.02622267873 · Zbl 1248.37044 · doi:10.1016/j.disc.2011.07.026
[121] [121]WoodsA. R. (1997) Coloring rules for finite trees, and probabilities of monadic second order sentences. Random Struct. Alg.10453-485.10.1002/(SICI)1098-2418(199707)10:4<453::AID-RSA3>3.0.CO;2-T · Zbl 0872.03021 · doi:10.1002/(SICI)1098-2418(199707)10:4<453::AID-RSA3>3.0.CO;2-T
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.