A linear partitioning algorithm for Hybrid Lyndons using V-order

David E. Daykin, Jacqueline W. Daykin, William F. Smyth

Allbwn ymchwil: Cyfraniad at gyfnodolynErthygladolygiad gan gymheiriaid

11 Dyfyniadau (Scopus)
25 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

In this paper we extend previous work on unique maximal factorization families (UMFFs) and a total (but non-lexicographic) ordering of strings called V-order. We present new combinatorial results for V-order, in particular concatenation under V-order. We propose linear-time RAM algorithms for string comparison in V-order and for Lyndonlike factorization of a string into V-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.
Iaith wreiddiolSaesneg
Tudalennau (o-i)149-161
Nifer y tudalennau13
CyfnodolynTheoretical Computer Science
Cyfrol483
Dyddiad ar-lein cynnar10 Chwef 2012
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 29 Ebr 2013
Cyhoeddwyd yn allanolIe

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'A linear partitioning algorithm for Hybrid Lyndons using V-order'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn