Parallel two dimensional witness computation

Richard Cole; Zvi Galil; Ramesh Hariharan; S. Muthukrishnan; Kunsoo Park

doi:10.1016/S0890-5401(03)00162-7

Parallel two dimensional witness computation

Richard Cole, Zvi Galil, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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

Original language	English (US)
Pages (from-to)	20-67
Number of pages	48
Journal	Information and Computation
Volume	188
Issue number	1
DOIs	https://doi.org/10.1016/S0890-5401(03)00162-7
State	Published - Jan 10 2004

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Computer Science Applications
Computational Theory and Mathematics

Access to Document

10.1016/S0890-5401(03)00162-7

Cite this

@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: [email protected] (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",

}

TY - JOUR

T1 - Parallel two dimensional witness computation

AU - Cole, Richard

AU - Galil, Zvi

AU - Hariharan, Ramesh

AU - Muthukrishnan, S.

AU - Park, Kunsoo

N1 - 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: [email protected] (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.

PY - 2004/1/10

Y1 - 2004/1/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0347538011&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347538011&partnerID=8YFLogxK

U2 - 10.1016/S0890-5401(03)00162-7

DO - 10.1016/S0890-5401(03)00162-7

M3 - Article

AN - SCOPUS:0347538011

SN - 0890-5401

VL - 188

SP - 20

EP - 67

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -

Parallel two dimensional witness computation

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this