Home
Scholarly Works
Generic Algorithms for Factoring Strings
Conference

Generic Algorithms for Factoring Strings

Abstract

In this paper we describe algorithms for factoring words over sets of strings known as circ-UMFFs, generalizations of the well-known Lyndon words based on lexorder, whose properties were first studied in 1958 by Chen, Fox and Lyndon. In 1983 Duval designed an elegant linear-time sequential (RAM) Lyndon factorization algorithm; a corresponding parallel (PRAM) algorithm was described in 1994 by Daykin, Iliopoulos and Smyth. In 2003 Daykin and Daykin introduced various circ-UMFFs, including one based on V-words and V-ordering; in 2011 linear string comparison and sequential factorization algorithms based on V-order were given by Daykin, Daykin and Smyth. Here we first describe generic RAM and PRAM algorithms for factoring a word over any circ-UMFF; then we show how to customize these generic algorithms to yield optimal parallel Lyndon-like V-word factorization.

Authors

Daykin DE; Daykin JW; Iliopoulos CS; Smyth WF

Series

Lecture Notes in Computer Science

Volume

7777

Pagination

pp. 402-418

Publisher

Springer Nature

Publication Date

January 1, 2013

DOI

10.1007/978-3-642-36899-8_18

Conference proceedings

Lecture Notes in Computer Science

ISSN

0302-9743

Labels

View published work (Non-McMaster Users)

Contact the Experts team