{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:54:18Z","timestamp":1757627658820,"version":"3.44.0"},"reference-count":38,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1992,11,1]],"date-time":"1992-11-01T00:00:00Z","timestamp":720576000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1992,11,1]],"date-time":"1992-11-01T00:00:00Z","timestamp":720576000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2004,3,24]],"date-time":"2004-03-24T00:00:00Z","timestamp":1080086400000},"content-version":"vor","delay-in-days":4161,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1992,11]]},"DOI":"10.1016\/0304-3975(92)90277-m","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:47:37Z","timestamp":1027640857000},"page":"21-60","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":24,"title":["More efficient bottom-up multi-pattern matching in trees"],"prefix":"10.1016","volume":"106","author":[{"given":"J.","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Paige","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"year":"1974","series-title":"Design and Analysis of Computer Algorithms","author":"Aho","key":"10.1016\/0304-3975(92)90277-M_BIB1"},{"key":"10.1016\/0304-3975(92)90277-M_BIB2","series-title":"Lehrstuhl fur Informatik III","article-title":"Table compression for tree automata","author":"Borstler","year":"1987"},{"key":"10.1016\/0304-3975(92)90277-M_BIB3","series-title":"Proc. CAAP '88","first-page":"1","article-title":"A tree pattern matching algorithm with reasonable space requirements","volume":"Vol. 299","author":"Burghardt","year":"1988"},{"key":"10.1016\/0304-3975(92)90277-M_BIB4","series-title":"Constructing Programs from Specifications","first-page":"126","article-title":"Type analysis and data structure selection","author":"Cai","year":"1991"},{"key":"10.1016\/0304-3975(92)90277-M_BIB5","article-title":"The RAPTS transformational system \u2013 a proposal for demonstration","author":"Cai","year":"1990","journal-title":"ESOP '90 Systems Exhibition"},{"key":"10.1016\/0304-3975(92)90277-M_BIB6","series-title":"Proc. CAAP 90","first-page":"72","article-title":"More efficient bottom up tree pattern matching","volume":"Vol. 431","author":"Cai","year":"1990"},{"key":"10.1016\/0304-3975(92)90277-M_BIB7","first-page":"168","article-title":"An improvement to bottom-up tree pattern matching","author":"Chase","year":"1987","journal-title":"Proc. 14th Ann. ACM Symp. on Principles of Programming Languages"},{"key":"10.1016\/0304-3975(92)90277-M_BIB8","article-title":"Fully persistent arrays","author":"Dietz","year":"1990","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(92)90277-M_BIB9","first-page":"524","article-title":"Dynamic perfect hashing: upper and lower bounds","author":"Dietzfelbinger","year":"1988","journal-title":"Proc. IEEE 29th FOCS"},{"key":"10.1016\/0304-3975(92)90277-M_BIB10","series-title":"Interactive Programming Environments","article-title":"Programming environments based on structured Editors: the Mentor Experience","author":"Donzeau-Gouge","year":"1984"},{"key":"10.1016\/0304-3975(92)90277-M_BIB11","first-page":"109","article-title":"Making data structures persistent","author":"Driscoll","year":"1986","journal-title":"Proc. 8th ACM STOC"},{"key":"10.1016\/0304-3975(92)90277-M_BIB12","article-title":"Faster tree pattern matching","author":"Dubiner","year":"1990","journal-title":"Proc. 31st IEEE FOCS '90"},{"issue":"3","key":"10.1016\/0304-3975(92)90277-M_BIB13","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","article-title":"Storing a sparse table with O(1) worst case access time","volume":"31","author":"Fredman","year":"1984","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(92)90277-M_BIB14","series-title":"Proc. ESOP '88","first-page":"245","article-title":"Code selection techniques: pattern matching, tree parsing, and inversion of derivors","volume":"Vol. 300","author":"Giegerich","year":"1988"},{"key":"10.1016\/0304-3975(92)90277-M_BIB15","first-page":"74","article-title":"Schema recognition for program transformations","author":"Givler","year":"1984","journal-title":"ACM Symp. on LISP and Functional Programming"},{"key":"10.1016\/0304-3975(92)90277-M_BIB16","first-page":"157","article-title":"A dichromatic framework for balanced trees","author":"Guibas","year":"1978","journal-title":"Proc. 19th IEEE FOCS"},{"key":"10.1016\/0304-3975(92)90277-M_BIB17","first-page":"119","article-title":"High-quality code generation via bottom-up tree pattern matching","author":"Hatcher","year":"1986","journal-title":"Proc. 13th ACM Symp. on Principles of Programming Languages"},{"key":"10.1016\/0304-3975(92)90277-M_BIB18","series-title":"Proc. ESOP '88","first-page":"175","article-title":"A functional language for the specification of complex tree transformations","volume":"Vol. 300","author":"Heckmann","year":"1988"},{"key":"10.1016\/0304-3975(92)90277-M_BIB19","series-title":"Tech. Report","article-title":"Encoding optimal pattern selection in a table-driven bottom-up tree-pattern matcher","author":"Henry","year":"1989"},{"issue":"1","key":"10.1016\/0304-3975(92)90277-M_BIB20","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/322290.322295","article-title":"Pattern matching in trees","volume":"29","author":"Hoffmann","year":"1982","journal-title":"J. ACM"},{"issue":"1","key":"10.1016\/0304-3975(92)90277-M_BIB21","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/357153.357158","article-title":"Programming with equations","volume":"4","author":"Hoffmann","year":"1982","journal-title":"ACM TOPLAS"},{"issue":"3","key":"10.1016\/0304-3975(92)90277-M_BIB22","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1145\/72551.72554","article-title":"Conception, evolution, and application of functional programming languages","volume":"21","author":"Hudak","year":"1989","journal-title":"ACM Comput. Survey"},{"key":"10.1016\/0304-3975(92)90277-M_BIB23","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/BF00264598","article-title":"Proving and applying program transformations expressed with second-order patterns","volume":"11","author":"Huet","year":"1978","journal-title":"Acta Inform."},{"key":"10.1016\/0304-3975(92)90277-M_BIB24","series-title":"Computational Problems in Abstract Algebra","first-page":"263","article-title":"Simple word problems in universal algebras","author":"Knuth","year":"1970"},{"key":"10.1016\/0304-3975(92)90277-M_BIB25","article-title":"Efficient tree pattern matching","author":"Kosaraju","year":"1989","journal-title":"Proc. 30th IEEE FOCS '89"},{"key":"10.1016\/0304-3975(92)90277-M_BIB26","series-title":"Proc. 2nd CCHSC Workshop","first-page":"52","article-title":"OPTRAN \u2013 a language\/system for the specification of program transformations: system overview and experiences","volume":"Vol. 371","author":"Lipps","year":"1988"},{"key":"10.1016\/0304-3975(92)90277-M_BIB27","article-title":"Unification-free execution of logic programs","author":"Maluszynski","year":"1985","journal-title":"IEEE Proc. Symp. on Logic Programming"},{"year":"1984","series-title":"Sorting and Searching, Data Structures and Algorithms, 1","author":"Mehlhorn","key":"10.1016\/0304-3975(92)90277-M_BIB28"},{"key":"10.1016\/0304-3975(92)90277-M_BIB29","first-page":"294","article-title":"Optimal code generation for expression trees: an application of BURS theory","author":"Pelegri-Llopart","year":"1988","journal-title":"Proc. 15th ACM Symp. on Principles of Programming Languages"},{"key":"10.1016\/0304-3975(92)90277-M_BIB30","first-page":"199","article-title":"Higher-order abstract syntax","author":"Pfenning","year":"1988","journal-title":"Proc. SIGPLAN '88 Conf. on Programming Language Design and Implementation"},{"key":"10.1016\/0304-3975(92)90277-M_BIB31","series-title":"Proc. RTA '85","first-page":"407","article-title":"Fast many-to-one matching algorithm","volume":"Vol. 202","author":"Purdom","year":"1985"},{"year":"1988","series-title":"The Synthesizer Generator","author":"Reps","key":"10.1016\/0304-3975(92)90277-M_BIB32"},{"issue":"7","key":"10.1016\/0304-3975(92)90277-M_BIB33","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","article-title":"Planar point location using persistent search trees","volume":"29","author":"Sarnak","year":"1986","journal-title":"Comm. ACM"},{"year":"1989","series-title":"Programming Languages: Concepts and Constructs","author":"Sethi","key":"10.1016\/0304-3975(92)90277-M_BIB34"},{"year":"1976","series-title":"The Irvine program transformation catalogue","author":"Standish","key":"10.1016\/0304-3975(92)90277-M_BIB35"},{"year":"1984","series-title":"Data Structures and Network Algorithms","author":"Tarjan","key":"10.1016\/0304-3975(92)90277-M_BIB36"},{"key":"10.1016\/0304-3975(92)90277-M_BIB37","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","article-title":"Preserving order in a forest in less than logarithmic time and linear space","volume":"6","author":"Van Emde Boas","year":"1977","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(92)90277-M_BIB38","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","article-title":"Log-logarithmic worst-case range queries are possible in space O(N)","volume":"17","author":"Willard","year":"1983","journal-title":"Inform. Process. Lett."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290277M?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290277M?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T04:18:04Z","timestamp":1757477884000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759290277M"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,11]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1992,11]]}},"alternative-id":["030439759290277M"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(92)90277-m","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[1992,11]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"More efficient bottom-up multi-pattern matching in trees","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0304-3975(92)90277-M","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1992 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}