Parallel RAM algorithms for factorizing words
- Daykin, J.W.
- Iliopoulos, C.S.
- Smyth, W.F.
Publication date
May 1994
DOI Publisher
Published by Elsevier B.V. ISSN
0304-3975 Citation count (estimate)
17Abstract
AbstractAn O(logn log log n) CRCW PRAM algorithm using O(nlog n) 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
Add to ORKG