{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:32Z","timestamp":1725663692482},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_166","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T08:20:18Z","timestamp":1330244418000},"page":"497-506","source":"Crossref","is-referenced-by-count":3,"title":["Parallel detection of all palindromes in a string"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Apostolico","sequence":"first","affiliation":[]},{"given":"Dany","family":"Breslauer","sequence":"additional","affiliation":[]},{"given":"Zvi","family":"Galil","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"40_CR1","first-page":"296","volume-title":"Optimal Parallel Algorithms for Periods, Palindromes and Squares","author":"A. Apostolico","year":"1992","unstructured":"A. Apostolico, D. Breslauer, and Z. Galil. Optimal Parallel Algorithms for Periods, Palindromes and Squares. In Proc. 19th International Colloquium on Automata, Languages, and Programming, pages 296\u2013307. Springer-Verlag, Berlin, Germany, 1992."},{"key":"40_CR2","first-page":"1209","volume":"11","author":"V.L. Arlazarov","year":"1970","unstructured":"V.L. Arlazarov, E.A. Dinic, M.A. Kronrod, and I.A. Faradzev. On economic construction of the transitive closure of a directed graph. Soviet Math. Dokl., 11:1209\u20131210, 1970.","journal-title":"Soviet Math. Dokl."},{"key":"40_CR3","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"R.P. Brent. Evaluation of general arithmetic expressions. J. Assoc. Comput. Mach., 21:201\u2013206, 1974.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"6","key":"40_CR4","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1137\/0219072","volume":"19","author":"D. Breslauer","year":"1990","unstructured":"D. Breslauer and Z. Galil. An optimal O(loglog n) time parallel string matching algorithm. SIAM J. Comput., 19(6):1051\u20131058, 1990.","journal-title":"SIAM J. Comput."},{"key":"40_CR5","unstructured":"D. Breslauer and Z. Galil. Finding all Periods and Initial Palindromes of a String in Parallel. Technical Report CUCS-017-92, Computer Science Dept., Columbia University, 1992."},{"key":"40_CR6","first-page":"75","volume-title":"Information Processing 71","author":"S.A. Cook","year":"1972","unstructured":"S.A. Cook. Linear time simulation of deterministic two-way pushdown automata. In Information Processing 71, pages 75\u201380. North Holland Publishing Co., Amsterdam, the Netherlands, 1972."},{"key":"40_CR7","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0304-3975(91)90073-B","volume":"88","author":"M. Crochemore","year":"1991","unstructured":"M. Crochemore and W. Rytter. Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays. Theoret. Comput. Sci., 88:59\u201382, 1991.","journal-title":"Theoret. Comput. Sci."},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"F.E. Fich, R.L. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation. In Proc. 3rd ACM Symp. on Principles of Distributed Computing, pages 179\u2013189, 1984.","DOI":"10.1145\/800222.806745"},{"key":"40_CR9","first-page":"113","volume-title":"Complexity of Computation","author":"M.J. Fischer","year":"1974","unstructured":"M.J. Fischer and M.S. Paterson. String matching and other products. In R.M. Karp, editor, Complexity of Computation, pages 113\u2013125. American Mathematical Society, Prividence, RI., 1974."},{"issue":"4","key":"40_CR10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0020-0190(76)90050-8","volume":"4","author":"Z. Galil","year":"1976","unstructured":"Z. Galil. Two fast simulations which imply some fast string matching and palindrome-recognition algorithms. Inform. Process. Lett., 4(4):85\u201387, 1976.","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"40_CR11","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/0022-0000(78)90042-9","volume":"16","author":"Z. Galil","year":"1978","unstructured":"Z. Galil. Palindrome Recognition in Real Time by a Multitape Turing Machine. J. Comput. System Sci., 16(2):140\u2013157, 1978.","journal-title":"J. Comput. System Sci."},{"key":"40_CR12","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/S0019-9958(85)80031-0","volume":"67","author":"Z. Galil","year":"1985","unstructured":"Z. Galil. Optimal parallel algorithms for string matching. Inform. and Control, 67:144\u2013157, 1985.","journal-title":"Inform. and Control"},{"issue":"1","key":"40_CR13","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1145\/322047.322056","volume":"25","author":"Z. Galil","year":"1978","unstructured":"Z. Galil and J. Seiferas. A Linear-Time On-Line Recognition Algorithm for \u201cPalstar\u201d. J. Assoc. Comput. Mach., 25(1):102\u2013111, 1978.","journal-title":"J. Assoc. Comput. Mach."},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Z. Kedem, G.M. Landau, and K. Palem. Optimal parallel suffix-prefix matching algorithm and applications. Manuscript, 1988.","DOI":"10.1145\/72935.72977"},{"key":"40_CR15","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6:322\u2013350, 1977.","journal-title":"SIAM J. Comput."},{"key":"40_CR16","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1307\/mmj\/1028998766","volume":"9","author":"R.C. Lyndon","year":"1962","unstructured":"R.C. Lyndon and M.P. Schutzenberger. The equation a m = b n c p in a free group. Michigan Math. J., 9:289\u2013298, 1962.","journal-title":"Michigan Math. J."},{"key":"40_CR17","doi-asserted-by":"crossref","unstructured":"G. Manacher. A new Linear-Time \u201cOn-Line\u201d Algorithm for Finding the Smallest Initial Palindrome of a String. J. Assoc. Comput. Mach., 22, 1975.","DOI":"10.1145\/321892.321896"},{"key":"40_CR18","unstructured":"A.O. Slisenko. Recognition of palindromes by multihead Turing machines. In V.P. Orverkov and N.A. Sonin, editors, Problems in the Constructive Trend in Mathematics VI (Proceedings of the Steklov Institute of Mathematics, No. 129), pages 30\u2013202. Academy of Sciences of the USSR, 1973. English Translation by R.H. Silverman, pp. 25\u2013208, Amer. Math. Soc., Providence, RI, 1976."}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_166.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:13:59Z","timestamp":1605629639000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_166","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}