Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

Item 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