@article{61874402765c456cb716afb55f68c072,

title = "Parallel two dimensional witness computation",

abstract = "An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m1 × m2 pattern is given. The algorithm takes O(log log m) time and does O(m1 × m 2) work, where m = max{m1, m2}. This yields a work optimal algorithm for 2D pattern matching which takes O (log log m) preprocessing time and O(1) text processing time.",

author = "Richard Cole and Zvi Galil and Ramesh Hariharan and S. Muthukrishnan and Kunsoo Park",

note = "Funding Information: Cole, Maxime Crochemore, Zvi Galil, Leszek Ga¸sieniec, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park, and Wojciech Rytter, which appeared in the 34th Annual Symposium on Foundations of Computer Science, 248–258. 1993 IEEE. ∗Corresponding author. Fax: 1-212-995-4124. E-mail address: cole@cs.nyu.edu (R. Cole). 1This work was partially supported by NSF Grants CCR-8902221, CCR-8906949, CCR-9202900, CCR-9503309, CCR-9800085, and CCR-0105678. 2This work was partially supported by NSF Grant CCR-90-14605 and CISE Institutional Infrastructure Grant CDA-90-24735. 3This work was largely done while the author was a student at the Courant Institute, NYU, and was supported by NSF Grants CCR-8902221, CCR-8906949, and CCR-9202900. 4 This work was largely done while the author was a student at the Courant Institute, NYU, and was supported by NSF/DARPA Grant CCR-89-06949 and NSF Grant CCR-91-03953. 5This work was supported by BK21 Project and MOST Grant M6-0203-00-0039.",

year = "2004",

month = jan,

day = "10",

doi = "10.1016/S0890-5401(03)00162-7",

language = "English (US)",

volume = "188",

pages = "20--67",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "1",

}