TY - JOUR
T1 - Parallel RAM Algorithms for Factorizing Words
AU - Daykin, Jacqueline W.
AU - Iliopoulos, Costas S.
AU - Smyth, William F.
N1 - Funding Information:
The first two authors wish to acknowledge the support of the UK Science and Engineering Research Council grant number GR/F 00898 during the course of this research. The second author was also partially supported by NATO grant CRG 900293 and Royal Society grant JD/MDO. The work of the third author was supported in part by grant number A8180 of the Natural Sciences and Engineering Research Board of Canada.
PY - 1994/5/9
Y1 - 1994/5/9
N2 - An O(logn log log n) CRCW PRAM algorithm using O(nlogn) processors for computing the unique Lyndon factorization of a word of length n over an unbounded alphabet is presented; this improves the bounds given by Apostolico and Crochemore (1989). Moreover, in the case of fixed alphabets the CRCW PRAM algorithm is optimal (linear cost), requiring O(log n) units of time.
AB - An O(logn log log n) CRCW PRAM algorithm using O(nlogn) processors for computing the unique Lyndon factorization of a word of length n over an unbounded alphabet is presented; this improves the bounds given by Apostolico and Crochemore (1989). Moreover, in the case of fixed alphabets the CRCW PRAM algorithm is optimal (linear cost), requiring O(log n) units of time.
UR - http://www.scopus.com/inward/record.url?scp=0028769345&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(94)90100-7
DO - 10.1016/0304-3975(94)90100-7
M3 - Article
SN - 0304-3975
VL - 127
SP - 53
EP - 67
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1
ER -