Generic Algorithms for Factoring Strings

David E. Daykin, Jacqueline W. Daykin, Costas S. Iliopoulos, W. F. Smyth

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

4 Citations (SciVal)


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.
Original languageEnglish
Title of host publicationInformation Theory, Combinatorics, and Search Theory
Subtitle of host publicationIn Memory of Rudolf Ahlswede
EditorsHarout Aydinian, Ferdinando Cicalese, Christian Deppe
PublisherSpringer Nature
Number of pages17
ISBN (Electronic)978-3-642-36899-8
ISBN (Print)978-3-642-36898-1
Publication statusPublished - 16 Mar 2013
Externally publishedYes


Dive into the research topics of 'Generic Algorithms for Factoring Strings'. Together they form a unique fingerprint.

Cite this