{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T14:29:43Z","timestamp":1649168983476},"reference-count":22,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2001,12,1]],"date-time":"2001-12-01T00:00:00Z","timestamp":1007164800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4246,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annals of Pure and Applied Logic"],"published-print":{"date-parts":[[2001,12]]},"DOI":"10.1016\/s0168-0072(01)00051-3","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T09:36:39Z","timestamp":1027589799000},"page":"59-80","source":"Crossref","is-referenced-by-count":5,"title":["Window-accumulated subsequence matching problem is linear"],"prefix":"10.1016","volume":"113","author":[{"given":"Luc","family":"Boasson","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Cegielski","sequence":"additional","affiliation":[]},{"given":"Ir\u00e8ne","family":"Guessarian","sequence":"additional","affiliation":[]},{"given":"Yuri","family":"Matiyasevich","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0168-0072(01)00051-3_BIB1","first-page":"255","article-title":"Algorithms for Finding Patterns in Strings","volume":"vol. 1","author":"Aho","year":"1990"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB2","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB3","series-title":"Window-accumulated subsequence matching problem is linear, Proc. PODS\u201999 (Principles of Database Systems)","first-page":"327","author":"Boasson","year":"1999"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB4","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/135239.135243","article-title":"A new approach to text searching","volume":"3","author":"Baeza-Yates","year":"1992","journal-title":"Comm. ACM"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB5","first-page":"1","volume":"vol. 1075","author":"Baeza-Yates","year":"1996"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB6","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1006\/inco.1995.1026","article-title":"On the power of the shift instruction","volume":"117","author":"Ben-Amram","year":"1995","journal-title":"Inform and Comput."},{"key":"10.1016\/S0168-0072(01)00051-3_BIB7","series-title":"Proc. IFIP Congress","first-page":"75","article-title":"Linear time simulation of deterministic two-way pushdown automata","author":"Cook","year":"1971"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB8","first-page":"44","volume":"vol. 324","author":"Crochemore","year":"1988"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB9","first-page":"12","volume":"vol. 1264","author":"Das","year":"1997"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB10","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1145\/322234.322244","article-title":"String matching in real time","volume":"28","author":"Galil","year":"1981","journal-title":"J. ACM"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB11","doi-asserted-by":"crossref","unstructured":"D.E. Knuth, Big omicron and big omega and big theta, SIGACT News (1976) 18\u201324.","DOI":"10.1145\/1008328.1008329"},{"issue":"2","key":"10.1016\/S0168-0072(01)00051-3_BIB12","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast pattern matching in strings","volume":"6","author":"Knuth","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0168-0072(01)00051-3_BIB13","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S0304-3975(97)88195-9","article-title":"Matching a set of strings with variable length don't cares","volume":"178","author":"Kucherov","year":"1997","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0168-0072(01)00051-3_BIB14","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(91)90032-D","article-title":"An algorithm for string matching with a sequence of don't cares","volume":"37","author":"Manber","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0168-0072(01)00051-3_BIB15","first-page":"41","volume":"vol. 1186","author":"Mannila","year":"1997"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB16","unstructured":"H. Mannila, H. Toivonen, A. Verkamo, Discovering frequent episodes in sequences, Proc. 1995 KDD Conf., 1995, pp. 210\u2013215."},{"key":"10.1016\/S0168-0072(01)00051-3_BIB17","doi-asserted-by":"crossref","unstructured":"Y. Matiyasevich, Real-time recognition of the inclusion relation, Zapiski Nauchnykh Leningradskovo Otdeleniya Mat. Inst. Steklova Akad. Nauk SSSR 20 (1971) 104\u2013114. (Translated into English, J. Soviet Math. 1 (1973) 64\u201370).","DOI":"10.1007\/BF01117471"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB18","doi-asserted-by":"crossref","unstructured":"V. Pratt, M. Rabin, L. Stockmeyer, A charaterization of the power of vector machines, Proc. SToC 74, pp. 122\u2013134.","DOI":"10.1145\/800119.803892"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB19","first-page":"493","volume":"vol. 64","author":"Slissenko","year":"1978"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(92)90362-J","article-title":"Multiplication, division and shift instructions in parallel random access machines","volume":"100","author":"Trahan","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0168-0072(01)00051-3_BIB21","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","article-title":"On-line construction of suffix-trees","volume":"14","author":"Ukkonen","year":"1995","journal-title":"Algorithmica"},{"key":"10.1016\/S0168-0072(01)00051-3_BIB22","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/135239.135244","article-title":"Fast text searching","volume":"3","author":"Wu","year":"1992","journal-title":"Comm. ACM"}],"container-title":["Annals of Pure and Applied Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0168007201000513?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0168007201000513?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T12:26:05Z","timestamp":1578486365000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0168007201000513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12]]},"references-count":22,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2001,12]]}},"alternative-id":["S0168007201000513"],"URL":"https:\/\/doi.org\/10.1016\/s0168-0072(01)00051-3","relation":{},"ISSN":["0168-0072"],"issn-type":[{"value":"0168-0072","type":"print"}],"subject":[],"published":{"date-parts":[[2001,12]]}}}