Parallel RAM Algorithms for Factorizing Words

Jacqueline W. Daykin, Costas S. Iliopoulos, William F. Smyth

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)53-67
Number of pages15
JournalTheoretical Computer Science
Issue number1
Publication statusPublished - 09 May 1994
Externally publishedYes


Dive into the research topics of 'Parallel RAM Algorithms for Factorizing Words'. Together they form a unique fingerprint.

Cite this