{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T16:11:44Z","timestamp":1698250304051},"reference-count":27,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":5192,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[1993,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a text tree <jats:italic>t<\/jats:italic> and a pattern tree <jats:italic>p<\/jats:italic>, tree pattern matching involves finding subtrees of <jats:italic>t<\/jats:italic> which match <jats:italic>p.<\/jats:italic> This paper proposed a parallel algorithm for tree pattern matching. The algorithm is designed to run in <jats:italic>O<\/jats:italic>(log <jats:italic>n<\/jats:italic>) parallel time using <jats:italic>mn<\/jats:italic>\/log<jats:italic>n<\/jats:italic> processors on CREW\u2010PRAM, where <jats:italic>n<\/jats:italic> and <jats:italic>m<\/jats:italic> are the sizes of <jats:italic>t<\/jats:italic> and <jats:italic>p<\/jats:italic> respectively. This improves the result of Ramesh et al. that runs in <jats:italic>O<\/jats:italic>(log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>) time using <jats:italic>nr<\/jats:italic>\/log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic> processors, where <jats:italic>r<\/jats:italic> is the number of vertices of <jats:italic>p<\/jats:italic> labeled with variables. Futhermore, the method of processor allocation is described specifically in the proposed algorithm.<\/jats:p>","DOI":"10.1002\/scj.4690240503","type":"journal-article","created":{"date-parts":[[2007,7,8]],"date-time":"2007-07-08T00:45:31Z","timestamp":1183855531000},"page":"30-39","source":"Crossref","is-referenced-by-count":4,"title":["A parallel algorithm for tree pattern matching"],"prefix":"10.1002","volume":"24","author":[{"given":"Koji","family":"Tarora","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomio","family":"Hirata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuyoshi","family":"Inagaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"334","volume-title":"Efficient tree pattern matching: an aid to code generation","author":"Aho A. V.","year":"1984"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0040376"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0026092"},{"key":"e_1_2_1_6_2","first-page":"168","volume-title":"An improvement to bottom\u2010up tree pattern matching","author":"Chase D. R.","year":"1987"},{"key":"e_1_2_1_7_2","first-page":"32","article-title":"Deterministic coin tossing with applications to optimal parallel list ranking","volume":"70","author":"Cole R.","year":"1986","journal-title":"Information and Computation"},{"key":"e_1_2_1_8_2","first-page":"478","volume-title":"Approximate and exact parallel scheduling with applications to list, tree and graph problems","author":"Cole R.","year":"1986"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217046"},{"key":"e_1_2_1_10_2","first-page":"145","volume-title":"Faster tree pattern matching","author":"Dubiner M.","year":"1990"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80031-0"},{"key":"e_1_2_1_12_2","volume-title":"Efficient Parallel Algorithms","author":"Gibbons A.","year":"1988"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/359657.359666"},{"key":"e_1_2_1_14_2","unstructured":"T.HirataandY.InagakiTree pattern matching algorithms. Technical Report of IPS 88AL\u201342(1988)."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322295"},{"key":"e_1_2_1_16_2","first-page":"169","volume-title":"An interpreter generator using tree pattern matching","author":"Hoffman C. M.","year":"1979"},{"key":"e_1_2_1_17_2","first-page":"125","volume-title":"Identification of repeated patterns in strings, trees, and arrays","author":"Karp R. M.","year":"1972"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-11980-9_18"},{"key":"e_1_2_1_20_2","first-page":"178","volume-title":"Efficient tree pattern matching","author":"Kosaraju S. R.","year":"1989"},{"issue":"1","key":"e_1_2_1_21_2","first-page":"2","article-title":"Parallelization and its limit from a theoretical aspect","volume":"7","author":"Miyano S.","year":"1990","journal-title":"Computer Software"},{"key":"e_1_2_1_22_2","first-page":"307","volume-title":"On simultaneous resource bounds","author":"Pippenger N.","year":"1979"},{"key":"e_1_2_1_23_2","first-page":"274","volume-title":"Optimal speedups for parallel pattern matching in trees","author":"Ramesh R.","year":"1987"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80023-5"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(89)90014-9"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213027"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80028-0"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690240503","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690240503","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T22:29:02Z","timestamp":1698186542000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690240503"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,1]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1993,1]]}},"alternative-id":["10.1002\/scj.4690240503"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690240503","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,1]]}}}