{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:20:20Z","timestamp":1787498420401,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540580942","type":"print"},{"value":"9783540484509","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58094-8_19","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:12:10Z","timestamp":1330251130000},"page":"213-225","source":"Crossref","is-referenced-by-count":3,"title":["Query primitives for tree-structured data"],"prefix":"10.1007","author":[{"given":"Pekka","family":"Kilpel\u00e4inen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Heikki","family":"Mannila","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"19_CR1","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974."},{"key":"19_CR2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D. Angluin","year":"1980","unstructured":"D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46\u201362, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR3","unstructured":"F. Bancilhon and P. Richard. Managing texts and facts in a mixed data base environment. In G. Gardarin and E. Gelenbe, editors, New Applications of Data Bases, pages 87\u2013107. Academic Press, 1984."},{"issue":"1","key":"19_CR4","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0747-7171(87)80027-5","volume":"3","author":"D. Benanav","year":"1987","unstructured":"D. Benanav, D. Kapur, and P. Narendran. Complexity of matching problems. Journal of Symbolic Computation, 3(1&2):203\u2013216, February\/April 1987.","journal-title":"Journal of Symbolic Computation"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"G. Coray, R. Ingold, and C. Vanoirbeek. Formatting structured documents: Batch versus interactive. In J. C. van Vliet, editor, Text Processing and Document Manipulation, pages 154\u2013170. Cambridge University Press, 1986.","DOI":"10.1017\/CBO9780511663130.013"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"M. Dubiner, Z. Galil, and E. Magen. Faster tree pattern matching. In Proc. of the Symposium on Foundations of Computer Science (FOCS'90), pages 145\u2013150, 1990.","DOI":"10.1109\/FSCS.1990.89533"},{"key":"19_CR7","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0020-0190(90)90154-P","volume":"36","author":"P. Dublish","year":"1990","unstructured":"P. Dublish. Some comments on the subtree isomorphism problem for ordered trees. Information Processing Letters, 36:273\u2013275, 1990.","journal-title":"Information Processing Letters"},{"key":"19_CR8","unstructured":"M. J. Fischer and M. S. Paterson. String-matching and other products. In Complexity of Computation, pages 113\u2013125. SIAM-AMS, 1974."},{"issue":"1","key":"19_CR9","first-page":"19","volume":"1","author":"R. Furuta","year":"1988","unstructured":"R. Furuta, V. Quint, and J. Andr\u00e9. Interactively editing structured documents. Electronic Publishing, 1(1):19\u201344, 1988.","journal-title":"Electronic Publishing"},{"issue":"3","key":"19_CR10","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"M. R. Garey","year":"1978","unstructured":"M. R. Garey and D. S. Johnson. \u201cStrong\u201d NP-completeness results: Motivation, examples and implications. Journal of the ACM, 25(3):499\u2013508, July 1978.","journal-title":"Journal of the ACM"},{"key":"19_CR11","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979."},{"key":"19_CR12","unstructured":"G. H. Gonnet and F. Wm. Tompa. Mind your grammar-a new approach to text databases. In Proc. of the Conference on Very Large Data Bases (VLDB'87), pages 339\u2013346, 1987."},{"key":"19_CR13","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(91)90159-F","volume":"39","author":"R. Grossi","year":"1991","unstructured":"R. Grossi. A note on the subtree isomorphism for ordered trees and related problems. Information Processing Letters, 39:81\u201384, 1991.","journal-title":"Information Processing Letters"},{"issue":"1","key":"19_CR14","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/322290.322295","volume":"29","author":"C. M. Hoffman","year":"1982","unstructured":"C. M. Hoffman and M. J. O'Donnell. Pattern matching in trees. Journal of the ACM, 29(1):68\u201395, January 1982.","journal-title":"Journal of the ACM"},{"issue":"4","key":"19_CR15","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. E. Hopcroft","year":"1973","unstructured":"J. E. Hopcroft and R. M. Karp. An n\n5\/2 algorithm for maximum matching in bipartite graphs. SIAM Journal on Computing, 2(4):225\u2013231, December 1973.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR16","unstructured":"P. Kilpel\u00e4inen. Tree Matching Problems with Applications to Structured Text Databases. PhD thesis, University of Helsinki, Dept. of Comp. Science, November 1992."},{"key":"19_CR17","unstructured":"P. Kilpel\u00e4inen, G. Lind\u00e9n, H. Mannila, and E. Nikunen. A structured document database system. In R. Furuta, editor, EP90 \u2014 Proceedings of the International Conference on Electronic Publishing, Document Manipulation & Typography, The Cambridge Series on Electronic Publishing. Cambridge University Press, 1990."},{"key":"19_CR18","unstructured":"P. Kilpel\u00e4inen and H. Mannila. Ordered and unordered tree inclusion. Report A-1991-4, University of Helsinki, Dept. of Comp. Science, August 1991. To appear in SIAM Journal on Computing."},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"P. Kilpel\u00e4inen and H. Mannila. The tree inclusion problem. In S. Abramsky and T. S. E. Maibaum, editors, TAPSOFT'91, Proc. of the International Joint Conference on the Theory and Practice of Software Development, Vol. 1: Colloqium on Trees in Algebra and Programming (CAAP'91), pages 202\u2013214. Springer-Verlag, 1991.","DOI":"10.1007\/3-540-53982-4_12"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"P. Kilpel\u00e4inen and H. Mannila. Grammatical tree matching. In A. Apostolico, M. Crochemore, Z. Galil, and U. Manber, editors, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, pages 162\u2013174. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-56024-6_13"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju. Efficient tree pattern matching. In Proc. of the Symposium on Foundations of Computer Science (FOCS'89), pages 178\u2013183, 1989.","DOI":"10.1109\/SFCS.1989.63475"},{"issue":"1\u20133","key":"19_CR22","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J. Matou\u0161ek","year":"1992","unstructured":"J. Matou\u0161ek and R. Thomas. On the complexity of finding iso-and other morphisms for partial k-trees. Discrete Mathematics, 108(1\u20133):343\u2013364, October 1992.","journal-title":"Discrete Mathematics"},{"key":"19_CR23","first-page":"273","volume":"10","author":"D. W. Matula","year":"1968","unstructured":"D. W. Matula. An algorithm for subtree identification. SIAM Rev., 10:273\u2013274, 1968. Abstract.","journal-title":"SIAM Rev."},{"issue":"2","key":"19_CR24","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1145\/128749.128752","volume":"39","author":"R. Ramesh","year":"1992","unstructured":"R. Ramesh and I. V. Ramakrishnan. Nonlinear pattern matching in trees. Journal of the ACM, 39(2):295\u2013316, April 1992.","journal-title":"Journal of the ACM"},{"issue":"4","key":"19_CR25","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1137\/0206053","volume":"6","author":"S. W. Reyner","year":"1977","unstructured":"S. W. Reyner. An analysis of a good algorithm for the subtree problem. SIAM Journal on Computing, 6(4):730\u2013732, December 1977.","journal-title":"SIAM Journal on Computing"},{"key":"19_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 and P. Flajolet. Patterns and pattern-matching in trees: An analysis. Information and Control, 58:19\u201358, 1983.","journal-title":"Information and Control"},{"key":"19_CR27","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0020-0190(92)90046-X","volume":"41","author":"R. M. Verma","year":"1992","unstructured":"R. M. Verma. Strings, trees, and patterns. Information Processing Letters, 41:157\u2013161, March 1992.","journal-title":"Information Processing Letters"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"R. M. Verma and I. V. Ramakrishnan. Some complexity theoretic aspects of AC rewriting. In B. Monien and R. Cori, editors, STACS89 \u2014 6th Annual Symposium on Theoretical Aspects of Computer Science, pages 407\u2013420. Springer-Verlag, 1989.","DOI":"10.1007\/BFb0029003"},{"issue":"6","key":"19_CR29","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K. Zhang","year":"1989","unstructured":"K. Zhang and D. Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal on Computing, 18(6):1245\u20131262, December 1989.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"K. Zhang, D. Shasha, and J. T.-L. Wang. Fast serial and parallel algorithms for approximate tree matching with VLDC's. In A. Apostolico, M. Crochemore, Z. Galil, and U. Manber, editors, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, pages 151\u2013161. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-56024-6_12"},{"issue":"3","key":"19_CR31","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(92)90136-J","volume":"42","author":"K. Zhang","year":"1992","unstructured":"K. Zhang, R. Statman, and D. Shasha. On the editing distance between unordered labeled trees. Information Processing Letters, 42(3):133\u2013139, May 1992.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58094-8_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:10:53Z","timestamp":1619557853000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58094-8_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580942","9783540484509"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-58094-8_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}