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)

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.
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
Pages402-418
Number of pages17
ISBN (Electronic)978-3-642-36899-8
ISBN (Print)978-3-642-36898-1
DOIs
Publication statusPublished - 16 Mar 2013
Externally publishedYes

Fingerprint

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

Cite this