{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T18:23:59Z","timestamp":1777141439200,"version":"3.51.4"},"publisher-location":"Berlin\/Heidelberg","reference-count":32,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540528261","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032034","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:05:31Z","timestamp":1134281131000},"page":"220-234","source":"Crossref","is-referenced-by-count":34,"title":["Analytic variations on the common subexpression problem"],"prefix":"10.1007","author":[{"given":"Philippe","family":"Flajolet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Sipala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Marc","family":"Steyaert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"Aho, A. V., Sethi, R., and Ullman, J. D.Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986."},{"key":"18_CR2","unstructured":"Albert, L., Casas, R., Fages, F., and Zimmermann, P. Average case analysis of unification algorithms, 1990. Technical report, INRIA, in preparation."},{"key":"18_CR3","unstructured":"Albert, L., and Fages, F. Average case analysis of the Rete pattern-matching algorithm. In Automata, Languages and Programming (1988), T. Lepist\u00f6 and A. Salomaa, Eds., vol. 317 of Lecture Notes in Computer Science, Springer Verlag. Proceedings of 15th ICALP Colloquium, Tempere, Finland, July 1988."},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0020-0190(89)90078-1","volume":"31","author":"R. Casas","year":"1989","unstructured":"Casas, R., Diaz, J., and Steyaert, J.-M. Average case analysis of Robinson's unification algorithm with two different variables. Inf. Process. Lett. 31 (June 1989), 227\u2013232.","journal-title":"Inf. Process. Lett."},{"key":"18_CR5","unstructured":"Casas, R., Diaz, J., Steyaert, J.-M., and Verges, M. On compact representation of trees. In Proceedings of the Colloquium on Algebra, Combinatorics and Logic for Computer Science (1984), Janos Bolyai Mathematical Society, North Holland Publishing Company."},{"key":"18_CR6","series-title":"Tech. Rep.","volume-title":"Algebraic simplification in computer algebra: an analysis of bottom-up algorithms","author":"R. Casas","year":"1989","unstructured":"Casas, R., Fernandez Camacho, M.-I., and Steyaert, J.-M. Algebraic simplification in computer algebra: an analysis of bottom-up algorithms. Tech. Rep. LIX-RR-89.04, Ecole Polytechnique, Palaiseau, France, 1989. To appear in Theoretical Computer Science, 1990."},{"key":"18_CR7","unstructured":"Char, B., Geddes, K., Gonnet, G., Monagan, M., and Watt, S.MAPLE: Reference Manual. University of Waterloo, 1988. 5th edition."},{"issue":"2","key":"18_CR8","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0747-7171(86)80021-9","volume":"2","author":"B. W. Char","year":"1986","unstructured":"Char, B. W., Fee, G. J., Geddes, K. O., Gonnet, G. H., and Monagan, M. M. A tutorial introduction to Maple. Journal of Symbolic Computation 2, 2 (1986), 179\u2013200.","journal-title":"Journal of Symbolic Computation"},{"key":"18_CR9","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0304-3975(89)90005-4","volume":"67","author":"C. Choppy","year":"1989","unstructured":"Choppy, C., Kaplan, S., and Soria, M. Complexity analysis of term rewriting systems. Theoretical Computer Science 67 (1989), 261\u2013282.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"18_CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1109\/TSE.1979.226495","volume":"SE-5","author":"D. W. Clark","year":"1979","unstructured":"Clark, D. W. Measurements of dynamic list structure use in Lisp. IEEE Trans. Software Eng. SE-5, 1 (1979), 51\u201359.","journal-title":"IEEE Trans. Software Eng."},{"issue":"2","key":"18_CR11","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/359423.359427","volume":"20","author":"D. W. Clark","year":"1977","unstructured":"Clark, D. W., and Green, C. C.. An empirical study of list structure in Lisp. Commun. ACM 20, 2 (1977), 78\u201387.","journal-title":"Commun. ACM"},{"key":"18_CR12","unstructured":"Donzeau-Gouge, V., Huet, G., Kahn, G., and Lang, B. Programming environments based on structured editors: the MENTOR experience. In Interactive Programming Environments (1984), D. Barstow, E. Sandewall, and H. Shrobe, Eds., McGraw-Hill, pp. 128\u2013140."},{"key":"18_CR13","first-page":"758","volume":"27","author":"P. J. Downey","year":"1980","unstructured":"Downey, P. J., Sethi, R., and Tarjan, R. E. Variations on the common subexpression problem. J. A.C.M. 27 (1980), 758\u2013771.","journal-title":"J. A.C.M."},{"key":"18_CR14","first-page":"225","volume-title":"Trends in Theoretical Computer Science","author":"P. Flajolet","year":"1988","unstructured":"Flajolet, P. Mathematical methods in the analysis of algorithms and data structures. In Trends in Theoretical Computer Science, E. B\u00f6rger, Ed. Computer Science Press, Rockville, Maryland, 1988, ch. 6, pp. 225\u2013304. (Lecture Notes for A Graduate Course in Computation Theory, Udine, 1984)."},{"key":"18_CR15","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0022-0000(82)90004-6","volume":"25","author":"P. Flajolet","year":"1982","unstructured":"Flajolet, P., and Odlyzko, A. The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25 (1982), 171\u2013213.","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0403019","volume":"3","author":"P. Flajolet","year":"1990","unstructured":"Flajolet, P., and Odlyzko, A. M. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics 3, 1 (February 1990). To appear. (Also available as INRIA Research Report 826, 1987, 25 pages).","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"18_CR17","unstructured":"Flajolet, P., Salvy, B., and Zimmermann, P. Lambda-Upsilon-Omega: The 1989 Cook-book. Research Report 1073, Institut National de Recherche en Informatique et en Automatique, August 1989. 116 pages."},{"key":"18_CR18","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01704918","volume":"19","author":"P. Flajolet","year":"1987","unstructured":"Flajolet, P., and Steyaert, J.-M. A complexity calculus for recursive tree algorithms. Mathematical Systems Theory 19 (1987), 301\u2013331.","journal-title":"Mathematical Systems Theory"},{"key":"18_CR19","unstructured":"Goto, E. Monocopy and associative algorithms in an extended LISP. Tech. Rep. 74-03, Information Sciences Lab., University of Tokyo, April 1974."},{"key":"18_CR20","volume-title":"Combinatorial Enumeration","author":"I. P. Goulden","year":"1983","unstructured":"Goulden, I. P., and Jackson, D. M.Combinatorial Enumeration. John Wiley, New York, 1983."},{"key":"18_CR21","unstructured":"Knuth, D. E.The Art of Computer Programming, vol. 1: Fundamental Algorithms. Addison-Wesley, 1968."},{"key":"18_CR22","unstructured":"Knuth, D. E.The Art of Computer Programming, vol. 3: Sorting and Searching. Addison-Wesley, 1973."},{"key":"18_CR23","unstructured":"Macsyma. VAX UNIX MACSYMA Reference manual, 1985."},{"key":"18_CR24","doi-asserted-by":"crossref","DOI":"10.21236\/AD0406138","volume-title":"LISP 1.5 Programmer's Manual","author":"J. McCarthy","year":"1962","unstructured":"McCarthy, J.LISP 1.5 Programmer's Manual. M.I.T. Press, Cambridge, Mass., 1962."},{"key":"18_CR25","doi-asserted-by":"crossref","first-page":"997","DOI":"10.4153\/CJM-1978-085-0","volume":"30","author":"A. Meir","year":"1978","unstructured":"Meir, A., and Moon, J. W. On the altitude of nodes in random trees. Canadian Journal of Mathematics 30 (1978), 997\u20131015.","journal-title":"Canadian Journal of Mathematics"},{"key":"18_CR26","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0097-3165(89)90078-2","volume":"51","author":"A. Meir","year":"1989","unstructured":"Meir, A., and Moon, J. W. On an asymptotic method in enumeration. Journal of Combinatorial Theory, Series A 51 (1989), 77\u201389.","journal-title":"Journal of Combinatorial Theory"},{"key":"18_CR27","unstructured":"Odlyzko, A. M. Enumeration of strings. In Combinatorial Algorithms on Words (1985), A. Apostolico and Z. Galil, Eds., vol. 12 of NATO Advance Science Institute Series. Series F: Computer and Systems Sciences, Springer Verlag, pp. 205\u2013228."},{"key":"18_CR28","unstructured":"Pedersen, J. Enumeration of trees containing variable patterns, 1988. Manuscript."},{"key":"18_CR29","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02546665","volume":"68","author":"G. P\u00f3lya","year":"1937","unstructured":"P\u00f3lya, G. Kombinatorische Anzahlbestimmungen f\u00fcr Gruppen, Graphen und chemische Verbindungen. Acta Mathematica 68 (1937), 145\u2013254.","journal-title":"Acta Mathematica"},{"key":"18_CR30","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4664-0","volume-title":"Combinatorial Enumeration of Groups, Graphs and Chemical Componds","author":"G. P\u00f3lya","year":"1987","unstructured":"P\u00f3lya, G., and Read, R. C.Combinatorial Enumeration of Groups, Graphs and Chemical Componds. Springer Verlag, New York, 1987."},{"issue":"1\u20133","key":"18_CR31","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0019-9958(83)80056-4","volume":"58","author":"J.-M. Steyaert","year":"1983","unstructured":"Steyaert, J.-M., and Flajolet, P. Patterns and pattern-matching in trees: an analysis. Information and Control 58, 1\u20133 (July 1983), 19\u201358.","journal-title":"Information and Control"},{"key":"18_CR32","unstructured":"Terashima, M. Algorithms used in an implementation of HLISP. Tech. Rep. 75-03, Information Sciences Lab., University of Tokyo, January 1975."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0032034.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:05:34Z","timestamp":1607551534000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/bfb0032034","relation":{},"subject":[]}}