{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T13:40:01Z","timestamp":1736084401766,"version":"3.32.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":46,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540537090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0020799","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:07:52Z","timestamp":1131862072000},"page":"196-213","source":"Crossref","is-referenced-by-count":3,"title":["Average case analysis of unification algorithms"],"prefix":"10.1007","author":[{"given":"Luc","family":"Albert","sequence":"first","affiliation":[]},{"given":"Rafael","family":"Casas","sequence":"additional","affiliation":[]},{"given":"Fran\u00e7ois","family":"Fages","sequence":"additional","affiliation":[]},{"given":"A.","family":"Torrecillas","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Zimmermann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman. The design and analysis of computer algorithms. Addison Wesley Pub. Comp. 1974."},{"key":"17_CR2","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/3-540-19488-6_104","volume":"317","author":"L. Albert","year":"1988","unstructured":"L. Albert and F. Fages. Average case complexity analysis of the RETE pattern match algorithm. Proceedings of the 15 th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 317, Tampere, Finland, pages 18\u201337. Springer Verlag, July 1988.","journal-title":"Proceedings of the 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science"},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/3-540-52048-1_46","volume":"405","author":"L. Albert","year":"1989","unstructured":"L. Albert. Average case complexity analysis of RETE pattern match algorithm and average size of join in Databases. Proceedings of the 9 th conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science 405, Bangalore, India, pages 223\u2013241. Springer Verlag, December 1989.","journal-title":"Proceedings of the 9th conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science"},{"key":"17_CR4","unstructured":"L. Albert. Quelques analyses de complexit\u00e9 en moyenne sur les algorithmes de multi-filtrage, d'unification et de requ\u00eate multiple. PhD. Thesis N. 1379. Universit\u00e9 Paris XI, 1990."},{"key":"17_CR5","unstructured":"L. Albert, R. Casas, J. Diaz and A. Torrecillas. On unification over unrestricted pairs of trees. Submitted to Mathematical Foundations of Computer Science '90, Bratislava, Czechoslovakia, August 1990. Report de Recerca LSI-89-26, universitat politecnica de catalunya, 1989. In Alcom workshop on probabilistic algorithms and average case analysis, Computer Technology Institute, Patras, Greece, March 4\u20137 1990."},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"A. Boudet, J.P. Jouannaud and M. Schmidt-Schauss. Unification in Boolean rings and Abelian groups. LICS'88. 1988.","DOI":"10.1016\/S0747-7171(89)80054-9"},{"key":"17_CR7","unstructured":"Formel Project. The CAML reference manual. INRIA, 1989."},{"key":"17_CR8","first-page":"909","volume":"83","author":"A. Corbin","year":"1983","unstructured":"A. Corbin and M. Bidoit. A rehabilitation of Robinson's unification algorithm. In Information processing 83, R.E.A. Mason, pages 909\u2013914. North Holland 1983.","journal-title":"Information processing"},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0020-0190(89)90078-1","volume":"31","author":"R. Casas","year":"1989","unstructured":"R. Casas, J. Diaz and J.M. Steyaert. Average case analysis of Robinson's unification algorithm with two different variables. Information proceedings letters, 31, pages 227\u2013232, June 1989.","journal-title":"Information proceedings letters"},{"key":"17_CR10","volume-title":"Symbolic Logic and Mechanical Theorem Proving","author":"C.L. Chang","year":"1973","unstructured":"C.L. Chang and R.C. Lee. Symbolic Logic and Mechanical Theorem Proving. Academic Press, New-York. 1973."},{"key":"17_CR11","unstructured":"A. Colmerauer. Les grammaires de m\u00e9tamorphose. Natural Language Communication with Computer, Lectures Notes in Computer Science. Springer-Verlag. 1978."},{"key":"17_CR12","unstructured":"A. Colmerauer. Prolog II, manuel de r\u00e9f\u00e9rence et mod\u00e8le th\u00e9orique. Rapport interne, Groupe d'Intelligence Artificielle, Universit\u00e9 d'Aix-Marseille II. March 1982."},{"key":"17_CR13","unstructured":"A. Colmerauer. Equations and inequations on finite and infinite trees. Proceedings of the International Conference on Fith Generation Computer Systems. 1984."},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"B. Courcelle. Fundamental properties of infinite trees. Theoretical Computer Science. 1983","DOI":"10.1016\/0304-3975(83)90059-2"},{"key":"17_CR15","unstructured":"N. Dershowitz and N. Lindenstrauss. Average time analyses related to logic programming. In 6th International Conference on Logic Programming, pages 369\u2013381. Lisboa 1989."},{"key":"17_CR16","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0743-1066(84)90022-0","volume":"1","author":"C. Dwork","year":"1984","unstructured":"C. Dwork, P.C. Kanellakis and J.C. Mitchell. On the sequential nature of unification. Journal of logic programming 1, pages 35\u201350. 1984.","journal-title":"Journal of logic programming"},{"issue":"2","key":"17_CR17","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0004-3702(88)90005-7","volume":"36","author":"G. Escalada-Imaz","year":"1988","unstructured":"G. Escalada-Imaz and M. Ghallab. A practically efficient and almost linear unification algorithm. Artificial Intelligence, volume 36, number 2, pages 249\u2013263. Sept. 1988.","journal-title":"Artificial Intelligence"},{"key":"17_CR18","unstructured":"F. Fages. Formes canoniques dans les alg\u00e8bres bool\u00e9ennes, et application \u00e0 la d\u00e9monstration automatique en logique de premier ordre. Th\u00e8se de l'Universit\u00e9 de Paris VI. 1983."},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"F. Fages. Associative-commutative unification. 7th CADE, Napa Valley. 1984.","DOI":"10.1007\/978-0-387-34768-4_12"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"F. Fages and G. Huet. Complete sets of unifiers and matchers in equational theories. Theoretical Computer Science. July 1986.","DOI":"10.1016\/0304-3975(86)90175-1"},{"key":"17_CR21","unstructured":"P. Flajolet. Mathematical methods in the analysis of algorithms and data structures. In Trends in theoretical computer science, E. Borger, Computer science press, ch. 6, pages 225\u2013304. Rockville, Maryland, 1988. (Lecture Notes for a Graduate Course in Computer Science, Udine, 1984)."},{"issue":"2","key":"17_CR22","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0403019","volume":"3","author":"P. Flajolet","year":"1990","unstructured":"P. Flajolet and A. Odlyzko. Singularity Analysis of Generating Functions. In SIAM Journal of Disc. Math., vol. 3, N. 2, pages 216\u2013240, 1990.","journal-title":"SIAM Journal of Disc. Math."},{"key":"17_CR23","unstructured":"P. Flajolet, B. Salvy and P. Zimmermann. Lambda-upsilon-omega: The 1989 Cookbook. Inria Research Report 1073, Institut National de Recherche en Informatique et Automatique, August 1989."},{"key":"17_CR24","unstructured":"P. Flajolet and J. Vitter. Average Case Analysis of Algorithms and Data Structures. In a Handbook of Theoretical Computer Science, North-Holland, 1987."},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"J. Herbrand. Recherches sur la th\u00e9orie de la d\u00e9monstration. Th\u00e8se de l'Universit\u00e9 de Paris. 1930. In Ecrits logiques de Jacques Herbrand. Paris, PUF, 1968.","DOI":"10.3917\/puf.herbr.1968.01.0233"},{"key":"17_CR26","doi-asserted-by":"crossref","unstructured":"G. Huet and D. Oppen. Equations and Rewrite Rules: a Survey. In Formal Languages: Perspectives and Open Problems, Ed. Book R., Academic Press. 1980.","DOI":"10.1016\/B978-0-12-115350-2.50017-8"},{"key":"17_CR27","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0304-3975(75)90011-0","volume":"1.1","author":"G. Huet","year":"1975","unstructured":"G. Huet. A Unification Algorithm for Typed Lambda Calculus. Theoretical Computer Science, 1.1, pages 27\u201357. 1975","journal-title":"Theoretical Computer Science"},{"key":"17_CR28","unstructured":"G. Huet. R\u00e9solution d'\u00e9quations dans les langages d'ordre 1,2,...,\u03c9. Th\u00e8se d'\u00e9tat de l'Universit\u00e9 Paris VII. 1976."},{"key":"17_CR29","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF03037057","volume":"2","author":"J. Jaffar","year":"1984","unstructured":"J. Jaffar. Efficient unification over infinite terms. New Generation Computing, 2, pages 207\u2013219. 1984.","journal-title":"New Generation Computing"},{"key":"17_CR30","doi-asserted-by":"crossref","unstructured":"D. Knuth and P. Bendix. Simple Word Problems in Universal Algebras. In Computational Problems in Abstract Algebra, Ed. Leech J., Pergamon Press, pages 263\u2013297. 1970.","DOI":"10.1016\/B978-0-08-012975-4.50028-X"},{"key":"17_CR31","first-page":"569","volume":"74","author":"R.A. Kowalski","year":"1974","unstructured":"R.A. Kowalski. Predicate Logic as Programming Language. Proceedings IFIP 74, North Holland, pages 569\u2013574. 1974.","journal-title":"Proceedings IFIP"},{"key":"17_CR32","unstructured":"J.L. Lassez, M.J. Maher and K. Marriott. Unification revisited. In Foundations of deductive databases and Logic Programming, J. Minker. 1986. IBM Research Report RC12355, 1986."},{"key":"17_CR33","unstructured":"B.W. Char, K.O. Geddes, G.H. Gonnet, M.B. Monagan and S.M. Watt. MAPLE: Reference Manual. University of Waterloo, 1988. 5th edition."},{"key":"17_CR34","doi-asserted-by":"crossref","unstructured":"H.G. Mairson. Deciding ML typability is complete for deterministic exponential time. POPL, San Francisco. January 1990.","DOI":"10.1145\/96709.96748"},{"key":"17_CR35","first-page":"348","volume":"17","author":"R. Milner","year":"1978","unstructured":"R. Milner. A Theory of Type Polymorphism in Programming. JCSS 17, pages 348\u2013375. 1978.","journal-title":"JCSS"},{"key":"17_CR36","unstructured":"A. Martelli and U. Montanari. Unification in Linear Time and Space: a Structured Presentation. Internal Report B76-16, IEI, Pisa. July 1976."},{"issue":"2","key":"17_CR37","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1145\/357162.357169","volume":"4","author":"A. Martelli","year":"1982","unstructured":"A. Martelli and U. Montanari. An efficient unification algorithm. In ACM Transactions on Programming Languages and Systems, volume 4, number 2, pages 258\u2013282. April 1982.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"17_CR38","doi-asserted-by":"crossref","unstructured":"H. Mannila and E. Ukkonen. On the complexity of unification sequences. Logic programming. 1986.","DOI":"10.1007\/3-540-16492-8_69"},{"key":"17_CR39","first-page":"73","volume":"7","author":"G. Plotkin","year":"1972","unstructured":"G. Plotkin. Building-in Equational Theories. Machine Intelligence 7, pages 73\u201390. 1972.","journal-title":"Machine Intelligence"},{"key":"17_CR40","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/0022-0000(78)90043-0","volume":"16","author":"M.S. Paterson","year":"1978","unstructured":"M.S. Paterson and M.N. Wegman. Linear unification. In Journal of computer and system sciences 16, pages 158\u2013167. 1978.","journal-title":"Journal of computer and system sciences"},{"issue":"1","key":"17_CR41","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/321250.321253","volume":"12","author":"J.A. Robinson","year":"1965","unstructured":"J.A. Robinson. A machine-oriented logic based on the resolution principle. In Journal of the Association for Computing Machinery, volume 12, number 1, pages 23\u201341. Jan. 1965.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"17_CR42","volume-title":"Machine Intelligence 6","author":"J.A. Robinson","year":"1971","unstructured":"J.A. Robinson. Computational Logic: the Unification Computation. Machine Intelligence 6, Eds B. Meltzer and D. Michie American Elsevier, New-York. 1971."},{"key":"17_CR43","unstructured":"L. Sterling and E. Shapiro. The Art of Prolog: Advanced Programming Techniques. MIT Press Series in Logic Programming, 1986."},{"key":"17_CR44","doi-asserted-by":"crossref","unstructured":"M.E. Stickel. A Complete Unification Algorithm for Associative-Commutative Functions. 4th International Joint Conference on Artificial Intelligence, Tbilisi. 1975.","DOI":"10.21236\/ADA015846"},{"issue":"2","key":"17_CR45","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R.E. Tarjan","year":"1984","unstructured":"R.E. Tarjan and J. van Leeuwen. Worst-case analysis of set union algorithms. In Journal of the association for computing machinery, volume 31, number 2, pages 245\u2013281. April 1984.","journal-title":"Journal of the association for computing machinery"},{"key":"17_CR46","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02575754","volume":"IV","author":"M. Venturini-Zilli","year":"1975","unstructured":"M. Venturini-Zilli. Complexity of the Unification Algorithm for First-Order Expressions. Calcolo XII, Fasc. IV, pages 361\u2013372. 1975.","journal-title":"Calcolo XII"}],"container-title":["Lecture Notes in Computer Science","STACS 91"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0020799.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T13:00:30Z","timestamp":1736082030000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0020799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540537090"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/bfb0020799","relation":{},"subject":[]}}