FAST PARALLEL LYNDON FACTORIZATION WITH APPLICATIONS

Authors
APOSTOLICO A CROCHEMORE M
Citation
A. Apostolico et M. Crochemore, FAST PARALLEL LYNDON FACTORIZATION WITH APPLICATIONS, Mathematical systems theory, 28(2), 1995, pp. 89-108
Citations number
18
Categorie Soggetti
System Science","Mathematics, Pure","Computer Science Theory & Methods",Mathematics
Journal title
Mathematical systems theory → ACNP
ISSN journal
00255661
Volume
28
Issue
2
Year of publication
1995
Pages
89 - 108
Database
ISI
SICI code
0025-5661(1995)28:2<89:FPLFWA>2.0.ZU;2-Q
Abstract
It is shown that the Lyndon decomposition of a word of n symbols can b e computed by an n-processor CRCW PRAM in 0(log n) time. Extensions of the basic algorithm convey, within the same time and processors bound s, efficient parallel solutions to problems such as finding the lexico graphically minimum or maximum suffix for all prefixes of the input st ring, and finding the lexicographically least rotation of all prefixes of the input.