×

zbMATH — the first resource for mathematics

Analytic models and ambiguity of context-free languages. (English) Zbl 0612.68069
We establish that several classical context-free languages are inherently ambiguous by proving that their counting generating functions, when considered as analytic functions, exhibit some characteristic form of transcendental behaviour. To that purpose, we survey some general results on elementary analytic properties and enumerative uses of algebraic functions in relation to formal languages. In particular, the paper contains a general density theorem for unambiguous context-free languages.

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Autebert, J.-M.; Beauquier, J.; Boasson, L.; Nivat, M., Quelques problèmes ouverts en théorie des langages algébriques, RAIRO inform. théor., 13, 363-379, (1979) · Zbl 0434.68056
[2] Baron, G.; Kuich, W., The characterization of nonexpansive grammars by rational power series, Inform. and control, 48, 109-118, (1981) · Zbl 0481.68075
[3] Beauquier, J.; Thimonier, L., Formal languages and Bernoulli processes, () · Zbl 0615.68055
[4] Ben-Or, M., Lower bounds for algebraic computation trees, Proc. 15th ACM symp. on theory of computing, 80-86, (198)
[5] Berstel, J., Sur la densité asymptotique des langages formels, (), 345-368
[6] Berstel, J., Contribution à l’étude des propriétés arithmétiques des langages formels, ()
[7] Bertoni, A.; Sabadini, N., Algebricity of the generating function for context-free languages, (1985), Manuscript
[8] Chandrasekharan, K., Arithmetical functions, (1970), Springer Berlin · Zbl 0217.31602
[9] Chomsky, N.; Schutzenberger, M.-P., The algebraic theory of context-free languages, (), 118-161 · Zbl 0148.00804
[10] Comtet, L., Calcul pratique des coefficients de Taylor d’une fonction algébrique, Enseignement math., 10, 267-270, (1964) · Zbl 0166.41702
[11] Comtet, L., Advanced combinatorics, (1974), Reidel Dordrecht
[12] Crestin, J.P., Un langage non ambigu dont le carré est d’ambiguité inherente bornée, (), 377-390 · Zbl 0277.68041
[13] Davies, B., Integral transforms and their application, (1978), Springer New York · Zbl 0381.44001
[14] Dieudonné, J., Calcul infinitésimal, (1968), Hermann Paris · Zbl 0155.10001
[15] Feller, W., An introduction to probability theory and its application, (1950), Wiley New York · Zbl 0039.13201
[16] Flajolet, P.; Odlyzko, A., The expected height of binary trees and other simple trees, J. comput. system sci., 25, 171-213, (1982) · Zbl 0499.68027
[17] Flajolet, P.; Regnier, M.; Sedgewick, R., Some uses of the Mellin integral transform in the analysis of algorithms, (), 241-254
[18] Gelfond, A.O., Transcendental and algebraic numbers, (1960), Dover New York · Zbl 0090.26103
[19] Guibas, L.; Odlyzko, A., Strings overlap, pattern-matching and non-transitive games, J. comb. theory. ser. A, 30, 183-208, (1980) · Zbl 0454.68109
[20] Hardy, G.H., Ramanujan, twelve lectures suggested by his life and work, (1940), Cambridge, University Press London · Zbl 0025.10505
[21] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[22] Henrici, P., Applied and computational complex analysis, (1977), Wiley New York · Zbl 0377.30002
[23] Hickey, T.; Cohen, J., Uniform random generation of strings in a context-free language, SIAM J. comput., 12, 645-655, (1983) · Zbl 0524.68046
[24] Ibarra, O.; Ravikumar, B., On sparseness, ambiguity and other decision problems for acceptors and transducer, (), 171-179
[25] Kemp, R., On the number of words in the language \({w ∈ Σ\^{}\{∗\}¦w = w\^{}\{R\}}\^{}\{2\}\), Discrete math., 40, 225-234, (1980) · Zbl 0485.68065
[26] Kemp, R., A note on the density of inherently ambiguous context-free languages, Acta inform., 14, 295-298, (1980) · Zbl 0441.68085
[27] Kendig, K., Elementary algebraic geometry, (1977), Springer New York · Zbl 0364.14001
[28] Knuth, D.E., The average time for carry propagation, Nederl. akad. wetensch. indag. math., 40, 238-242, (1978) · Zbl 0382.10035
[29] Kornai, A., Quantitative comparison of formal languages, (1985), Manuscript, submitted
[30] Kuich, W.; Salomaa, A., Semirings, automata, languages, (1986), Springer New York · Zbl 0582.68002
[31] Kuich, W.; Shyamasundar, R.K., The structure generating function of some families of languages, Inform. and control, 32, 85-92, (1976) · Zbl 0338.68054
[32] Meir, A.; Moon, J., On the altitude of nodes in random trees, Canad. J. math., 30, 997-1015, (1978) · Zbl 0394.05015
[33] Pippenger, N., Computational complexity in algebraic function fields, Proc. 20th IEEE symp. FOCS, 61-65, (1979)
[34] Rudin, W., Real and complex analysis, (1974), McGraw-Hill New York
[35] Salomaa, A.; Soittola, M., Automata theoretic aspects of formal power series, (1978), Springer New York · Zbl 0377.68039
[36] Schneider, Th., Einfuehrung in die transzendenten zahlen, (1957), Springer Berlin
[37] Seidenberg, A., Elements of the theory of algebraic curves, (1965), Addison-Wesley Reading, MA · Zbl 0138.00301
[38] Shamir, E., Some inherently ambiguous context-free languages, Inform. and control, 18, 355-363, (1971) · Zbl 0227.68039
[39] Shamos, M.I.; Yuval, G., Lower bounds from complex function theory, Proc. 17th IEEE symp. FOCS, 268-273, (1976)
[40] Stanley, R., Differentiably finite power series, European J. combin., 1, 175-188, (1980) · Zbl 0445.05012
[41] Whittaker, E.T.; Watson, G.N., A course in modern analysis, (1927), Cambridge University Press London · Zbl 0108.26903
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.