Catalog Home Page

A linear partitioning algorithm for Hybrid Lyndons using -order

Daykin, D.E., Daykin, J.W. and Smyth, W.F. (2013) A linear partitioning algorithm for Hybrid Lyndons using -order. Theoretical Computer Science, 483 . pp. 149-161.

Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2012.02.001
*Subscription may be required

Abstract

In this paper we extend previous work on unique maximal factorization families (UMFFs) and a total (but non-lexicographic) ordering of strings called VV-order. We present new combinatorial results for VV-order, in particular concatenation under VV-order. We propose linear-time RAM algorithms for string comparison in VV-order and for Lyndon-like factorization of a string into VV-words. This asymptotic efficiency thus matches that of the corresponding algorithms for lexicographical order. Finally, we introduce Hybrid Lyndon words as a generalization of standard Lyndon words, and hence propose extensions of factorization algorithms to other forms of order.

Publication Type: Journal Article
Publisher: Elsevier BV
Copyright: © 2012 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/28230
Item Control Page Item Control Page