Journal article
Generic algorithms for factoring strings
Information Theory, Combinatorics, and Search Theory, Vol.7777, pp.402-418
2013
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.
Details
- Title
- Generic algorithms for factoring strings
- Authors/Creators
- D.E. Daykin (Author/Creator) - University of ReadingJ.W. Daykin (Author/Creator) - Royal Holloway University of LondonC.S. Iliopoulos (Author/Creator) - The University of Western AustraliaW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- Information Theory, Combinatorics, and Search Theory, Vol.7777, pp.402-418
- Publisher
- Springer Verlag
- Identifiers
- 991005545031007891
- Copyright
- 2013 Springer-Verlag Berlin Heidelberg
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
30 Record Views