A linear partitioning algorithm for Hybrid Lyndons using -order
Tools
Tools
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.
*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 |