Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Parallel RAM algorithms for factorizing words

Daykin, J.W., Iliopoulos, C.S. and Smyth, W.F. (1994) Parallel RAM algorithms for factorizing words. Theoretical Computer Science, 127 (1). pp. 53-67.

Free to read: http://dx.doi.org/10.1016/0304-3975(94)90100-7
*No subscription required

Abstract

An O(logn log log n) CRCW PRAM algorithm using O(n/log 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.

Item Type: Journal Article
Publisher: Elsevier BV
Copyright: © 1994 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27517
Item Control Page Item Control Page