@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",
}