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

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.

Item 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