{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:55Z","timestamp":1725663655601},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540194880"},{"type":"electronic","value":"9783540392910"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19488-6_104","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:13:19Z","timestamp":1330182799000},"page":"18-37","source":"Crossref","is-referenced-by-count":2,"title":["Average case complexity analysis of the RETE multi-pattern match algorithm"],"prefix":"10.1007","author":[{"given":"Luc","family":"Albert","sequence":"first","affiliation":[]},{"given":"Fran\u00e7ois","family":"Fages","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"2_CR1","unstructured":"L. Albert \u201cPr\u00e9sentation et \u00e9valuation de la complexit\u00e9 de l'algorithme RETE de multi-pattern matching dans les syst\u00e8mes de r\u00e8gles de production\u201d, rapport de DEA Universite de PARIS XI, ENS, rapport de recherche 87-8 LCR Thomson-CSF, 1987."},{"key":"2_CR2","unstructured":"NG de Bruijn Asymptotic Methods in Analysis Dover 1958."},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"C.Choppy,S.Kaplan,M.Soria \u201cAlgorithmic complexity of term rewriting systems\u201d, proceedings of the first Conference on Rewriting Techniques and Applications, Dijon, France. 1986.","DOI":"10.1007\/3-540-17220-3_22"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"D.W. Clark \u201cMeasurements of Dynamic List Structures Use in Lisp\u201d. IEEE Transactions on Software Engineering SE-5(1), pp.51\u201359. (Jan. 1979).","DOI":"10.1109\/TSE.1979.226495"},{"key":"2_CR5","unstructured":"J. Dieudonn\u00e9 Calcul infinit\u00e9simal Hermann 1968."},{"key":"2_CR6","unstructured":"P. Dufresne \u201cContribution algorithmique \u00e0 l'inf\u00e9rence par r\u00e8gles de production\", Th\u00e8se Universit\u00e9 Paul Sabatier Toulouse 1984."},{"key":"2_CR7","unstructured":"F. Fages \u201cOn the proceduralization of rules in expert systems\u201d, First France-Japan Symposium on Artificial Intelligence, Tokyo, Nov. 86. In Programming of Future Generation Computers, Addison-Wesley, Eds. M. Nivat and K. Fuchi."},{"key":"2_CR8","unstructured":"P. Flajolet \u201cMathematical methods in the analysis of algorithms and data structures\u201d, INRIA, Research Report 400,1985. To appear in the Mathematical Handbook of Theoretical Computer Science, North-Holland."},{"key":"2_CR9","unstructured":"P. Flajolet \u201cThe symbolic operator method\u201d, in Mathematical methods in the analysis of algorithms and data structure, L.N.C.S., Springer Verlag, to appear 1987."},{"key":"2_CR10","unstructured":"C. Forgy \u201cOn the efficient implementation of production systems\u201d, PhD Thesis Carnegie Mellon University 1979."},{"key":"2_CR11","doi-asserted-by":"crossref","DOI":"10.21236\/ADA106558","volume-title":"OPS-V user's manual","author":"C. Forgy","year":"1981","unstructured":"C. Forgy \u201cOPS-V user's manual\u201d, Computer Science Department, Carnegie Mellon University, Pittsburgh, MA, 1981."},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0004-3702(82)90020-0","volume":"19","author":"C. Forgy","year":"1982","unstructured":"C. Forgy \u201cRete, a fast algorithm for the many patterns many objects Match problem\u201d, Artificial Intelligence 19, 1982,pp 17\u201337.","journal-title":"Artificial Intelligence"},{"key":"2_CR13","unstructured":"P. Flajolet, R. Sedgewick \u201cMathematical analysis of algorithms\u201d, Computer Science 504, lecture Notes for Princeton University 1986."},{"key":"2_CR14","unstructured":"P. Flajolet, P. Sipala et J.M. Steyaert \u201cThe analysis of tree compaction in symbolic manipulations\u201d, preprint."},{"key":"2_CR15","unstructured":"M. Ghallab, P. Dufresne \u201cMoteurs d'inf\u00e9rences pour syst\u00e8mes de r\u00e8gles de production: techniques de compilation et d'interpr\u00e9tation\u201d, LAAS Toulouse 1987,pp 89\u2013103."},{"key":"2_CR16","unstructured":"A. Gupta et C.L. Forgy \u201cMeasurements on production systems\u201d, Carnegie Mellon University Technical Report CMU-CS-83-167,1983."},{"key":"2_CR17","unstructured":"A. Gupta \u201cParallelism in production Systems: the sources and the expected Speed-up\u201d, Carnegie Mellon University Technical Report CMU-CS-84-169,1984."},{"key":"2_CR18","unstructured":"P. Henrici Applied and Computational complex Analysis Volumes 1\u20133 Wiley New-York."},{"key":"2_CR19","volume-title":"Building Expert Systems","author":"F. Hayes-Roth","year":"1983","unstructured":"F. Hayes-Roth, D.A. Waterman and D.A. Lenat. Building Expert Systems. Addison-Wesley, Reading, M.A. (1983)."},{"key":"2_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90050-6","volume":"33","author":"J.E. Laird","year":"1987","unstructured":"J.E. Laird, A. Newell and P.S. Rosenbloom. \u201cSOAR: An Architecture for General Intelligence\u201d, Artificial Intelligence 33, pp 1\u201364. (1987).","journal-title":"Artificial Intelligence"},{"key":"2_CR21","unstructured":"B.W. Char, K.O. Geddes, G.H. Gonnet, S.M. Watt, MAPLE: Reference Manual, University of Waterloo, 1985."},{"key":"2_CR22","unstructured":"D.P. Miranker \u201cTREAT: A Better Match Algorithm for AI Production Systems\u201d Proceedings of the 1987 National Conference on Artificial Intelligence. Seattle, Washington. (1987)."},{"key":"2_CR23","doi-asserted-by":"crossref","first-page":"997","DOI":"10.4153\/CJM-1978-085-0","volume":"30","author":"A. Meier","year":"1978","unstructured":"A. Meier, J.W. Moon \u201cOn the altitude of nodes in random trees\u201d, Canadian Journal of Math 30,1978,pp 997\u20131015.","journal-title":"Canadian Journal of Math"},{"key":"2_CR24","first-page":"3","volume":"83","author":"M. Stefik","year":"1983","unstructured":"Stefik M., Bobrow D., Mittal S. and Conway L \u201cKnowledge Programming in LOOPS: Report on an Experimental Course\u201d The AI magazine Fall 83, pp 3\u201313. (1983).","journal-title":"The AI magazine Fall"},{"key":"2_CR25","unstructured":"Schang T. and Fages F \u201cA Real-Time Expert System for On-Board Radar Identification\u201d 55th Symposium AVP-AGARD on Software Engineering and its Applications to Avionics.(1988)."},{"key":"2_CR26","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0019-9958(83)80056-4","volume":"58","author":"J.M. Steyaert","year":"1983","unstructured":"J.M. Steyaert, P. Flajolet \u201cPatterns and Pattern Matching in trees: an analysis\u201d, Information and Control 58,1983,pp 19\u201358.","journal-title":"Information and Control"},{"key":"2_CR27","unstructured":"J.M. Steyaert \u201cComplexit\u00e9 et structures des algorithmes\u201d, Th\u00e8se d'Etat Universit\u00e9 de Paris 7 1984."},{"key":"2_CR28","unstructured":"G. Viennot \u201cLa combinatoire bijective par l'example\u201d, Universit\u00e9 de Bordeaux 1, 1986."},{"key":"2_CR29","unstructured":"Warren D.H.D. An abstract Prolog Instruction Set. Technical Note 309, SRI International. 1985."},{"key":"2_CR30","doi-asserted-by":"crossref","unstructured":"Wright, M.L., Green M.W., Fiegl G., Cross P.F., \u201cAn Expert System for Real-Time Control\u201d SRI International, in IEEE Software. (March 1986).","DOI":"10.1109\/MS.1986.232784"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19488-6_104.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:17:22Z","timestamp":1605626242000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19488-6_104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194880","9783540392910"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-19488-6_104","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}