Parallel RAM Algorithms for Factorizing Words

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

doi:10.1016/0304-3975(94)90100-7

Parallel RAM Algorithms for Factorizing Words

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

Allbwn ymchwil: Cyfraniad at gyfnodolyn › Erthygl › adolygiad gan gymheiriaid

23 Dyfyniadau (Scopus)

Crynodeb

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.

Iaith wreiddiol	Saesneg
Tudalennau (o-i)	53-67
Nifer y tudalennau	15
Cyfnodolyn	Theoretical Computer Science
Cyfrol	127
Rhif cyhoeddi	1
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1016/0304-3975(94)90100-7
Statws	Cyhoeddwyd - 09 Mai 1994
Cyhoeddwyd yn allanol	Ie

Mynediad at Ddogfen

10.1016/0304-3975(94)90100-7

Cysylltiad parhaol

Dolen barhaus

Ffeiliau eraill a chysylltiadau

Dolen i’r cyhoeddiad yn Scopus

Dyfynnu hyn

@article{b5a314e29fa74ee2a49df16acfe35caa,

title = "Parallel RAM Algorithms for Factorizing Words",

abstract = "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.",

author = "Daykin, \{Jacqueline W.\} and Iliopoulos, \{Costas S.\} and Smyth, \{William F.\}",

note = "Funding Information: The first two authors wish to acknowledge the support of the UK Science and Engineering Research Council grant number GR/F 00898 during the course of this research. The second author was also partially supported by NATO grant CRG 900293 and Royal Society grant JD/MDO. The work of the third author was supported in part by grant number A8180 of the Natural Sciences and Engineering Research Board of Canada.",

year = "1994",

month = may,

day = "9",

doi = "10.1016/0304-3975(94)90100-7",

language = "English",

volume = "127",

pages = "53--67",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Parallel RAM Algorithms for Factorizing Words

AU - Daykin, Jacqueline W.

AU - Iliopoulos, Costas S.

AU - Smyth, William F.

N1 - Funding Information: The first two authors wish to acknowledge the support of the UK Science and Engineering Research Council grant number GR/F 00898 during the course of this research. The second author was also partially supported by NATO grant CRG 900293 and Royal Society grant JD/MDO. The work of the third author was supported in part by grant number A8180 of the Natural Sciences and Engineering Research Board of Canada.

PY - 1994/5/9

Y1 - 1994/5/9

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0028769345

U2 - 10.1016/0304-3975(94)90100-7

DO - 10.1016/0304-3975(94)90100-7

M3 - Article

SN - 0304-3975

VL - 127

SP - 53

EP - 67

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -

Parallel RAM Algorithms for Factorizing Words

Crynodeb

Mynediad at Ddogfen

Cysylltiad parhaol

Ffeiliau eraill a chysylltiadau

Ôl bys

Dyfynnu hyn