Catalog Home Page

Generic algorithms for factoring strings

Daykin, D.E., Daykin, J.W., Iliopoulos, C.S. and Smyth, W.F. (2013) Generic algorithms for factoring strings. Lecture Notes in Computer Science, 7777 . pp. 402-418.

Link to Published Version: http://dx.doi.org/10.1007/978-3-642-36899-8_18
*Subscription may be required

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.

Publication Type: Journal Article
Publisher: Springer Verlag
Copyright: 2013 Springer-Verlag Berlin Heidelberg
URI: http://researchrepository.murdoch.edu.au/id/eprint/28234
Item Control Page Item Control Page