{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:57Z","timestamp":1759639077045,"version":"3.40.5"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_47","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"599-610","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Backward Linearised Tree Pattern Matching"],"prefix":"10.1007","author":[{"given":"Jan","family":"Tr\u00e1vn\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Janou\u0161ek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo\u0159ivoj","family":"Melichar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Loek","family":"Cleophas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"47_CR1","doi-asserted-by":"crossref","unstructured":"Aho, A.V., Ganapathi, M., Tjiang, S.W.K.: Code generation using tree matching and dynamic programming. ACM Trans. Program. Lang. Syst., 491\u2013516 (1989)","DOI":"10.1145\/69558.75700"},{"key":"47_CR2","unstructured":"Aho, A.V., Ullman, J.D.: The theory of parsing, translation, and compiling. Prentice-Hall (1972)"},{"key":"47_CR3","unstructured":"Charras, C., Lecroq, T.: Handbook of exact string matching algorithms. Kings College Publications (2004)"},{"key":"47_CR4","doi-asserted-by":"crossref","unstructured":"Chase, D.R.: An improvement to bottom-up tree pattern matching. In: POPL, pp. 168\u2013177. ACM Press (1987)","DOI":"10.1145\/41625.41640"},{"key":"47_CR5","doi-asserted-by":"crossref","unstructured":"Cleophas, L.: Forest FIRE and FIRE wood: tools for tree automata and tree algorithms. In: Piskorski, J., Watson, B.W., Yli-Jyr\u00e4, A. (eds.) FSMNLP. Frontiers in Artificial Intelligence and Applications, vol. 19, pp. 191\u2013198. IOS Press (2008)","DOI":"10.3233\/978-1-58603-975-2-191"},{"key":"47_CR6","unstructured":"Cleophas, L.: Tree Algorithms: Two Taxonomies and a Toolkit. Ph.D. thesis, Department of Mathematics and Computer Science, Eindhoven University of Technology (April 2008)"},{"key":"47_CR7","unstructured":"Cole, R., Hariharan, R., Indyk, P.: Tree pattern matching and subset matching in deterministic o($$n log^3 n$$) time. In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, pp. 245\u2013254 (1999)"},{"key":"47_CR8","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata: Techniques and applications (2007). http:\/\/www.grappa.univ-lille3.fr\/tata\/ (release October 12, 2007)"},{"key":"47_CR9","doi-asserted-by":"crossref","unstructured":"Crochemore, M.A., Rytter, W.: Jewels of Stringology. World Scientific Publishing Company (2003)","DOI":"10.1142\/4838"},{"issue":"2","key":"47_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/2431211.2431212","volume":"45","author":"S Faro","year":"2013","unstructured":"Faro, S., Lecroq, T.: The exact online string matching problem: A review of the most recent results. ACM Comput. Surv. 45(2), 13 (2013)","journal-title":"ACM Comput. Surv."},{"key":"47_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-642-22256-6_25","volume-title":"Implementation and Application of Automata","author":"T Flouri","year":"2011","unstructured":"Flouri, T., Janou\u0161ek, J., Melichar, B., Iliopoulos, C.S., Pissis, S.P.: Tree template matching in ranked ordered trees by pushdown automata. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2011. LNCS, vol. 6807, pp. 273\u2013281. Springer, Heidelberg (2011)"},{"key":"47_CR12","doi-asserted-by":"crossref","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree languages. In: Handbook of Formal Languages, vol. 3, pp. 1\u201368. Springer (1997)","DOI":"10.1007\/978-3-642-59126-6_1"},{"issue":"1","key":"47_CR13","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1145\/322290.322295","volume":"29","author":"CM Hoffmann","year":"1982","unstructured":"Hoffmann, C.M., O\u2019Donnell, M.J.: Pattern matching in trees. Journal of the ACM 29(1), 68\u201395 (1982)","journal-title":"Journal of the ACM"},{"issue":"6","key":"47_CR14","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/spe.4380100608","volume":"10","author":"RN Horspool","year":"1980","unstructured":"Horspool, R.N.: Practical fast searching in strings. Software Practice and Experience 10(6), 501\u2013506 (1980)","journal-title":"Software Practice and Experience"},{"key":"47_CR15","unstructured":"Lang, H.W., Schimmler, M., Schmeck, H.: Matching tree patterns sublinear on the average. Christian-Albrechts-Universit\u00e4t, Tech. rep. (1980)"},{"key":"47_CR16","unstructured":"Smyth, W.F.: Computing Patterns in Strings. Addison-Wesley-Pearson Education Limited (2003)"},{"key":"47_CR17","unstructured":"Strolenberg, R.: ForestFIRE & FIREWood, A Toolkit & GUI for Tree Algorithms. Master\u2019s thesis, Department of Mathematics and Computer Science, Eindhoven University of Technology (June 2007). http:\/\/alexandria.tue.nl\/extra1\/afstversl\/wsk-i\/strolenberg2007.pdf"},{"key":"47_CR18","unstructured":"Watson, B.W.: A boyer-moore (or watson-watson) type algorithm for regular tree pattern matching. In: Stringology, pp. 33\u201338 (1997)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T21:57:28Z","timestamp":1747691848000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}