PARALLEL RAM ALGORITHMS FOR FACTORIZING WORDS

Authors
DAYKIN JW ILIOPOULOS CS SMYTH WF
Citation
Jw. Daykin et al., PARALLEL RAM ALGORITHMS FOR FACTORIZING WORDS, Theoretical computer science, 127(1), 1994, pp. 53-67
Citations number
6
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
127
Issue
1
Year of publication
1994
Pages
53 - 67
Database
ISI
SICI code
0304-3975(1994)127:1<53:PRAFFW>2.0.ZU;2-Z
Abstract
An O(log n log log n) CRCW PRAM algorithm using O(n/log n) processors for computing the unique Lyndon factorization of a word of length n ov er an unbounded alphabet is presented; this improves the bounds given by Apostolico and Crochemore (1989). Moreover, in the case of fixed al phabets the CRCW PRAM algorithm is optimal (linear cost), requiring O( log n) units of time.