A linear partitioning algorithm for hybrid Lyndons using V-order

DOI10.1016/J.TCS.2012.02.001MaRDI QIDQ390899zbMATH OpenOpenAlexFDO

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

Publication date 9 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.02.001

zbMATH Keywords

lexicographic orderconcatenationstring comparison\(V\)-orderfactorization algorithms\(V\)-wordalphabetcirc-UMFFhybrid Lyndon wordslinear-time RAM algorithmspartitioning algorithmtotal orderunique maximal factorization family (UMFF)

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• String comparison and Lyndon-like factorization using V-order in linear time
• V-order: new combinatorial properties \& a simple comparison algorithm
• Generic Algorithms for Factoring Strings
• Lyndon-like and V-order factorizations of strings
• Applications of \(V\)-order: suffix arrays, the Burrows-Wheeler transform \& the FM-index

Cites work

• scientific article; zbMATH DE number 417855 (Why is no real title available?)
• scientific article; zbMATH DE number 3914379 (Why is no real title available?)
• scientific article; zbMATH DE number 68337 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 1146223 (Why is no real title available?)
• A note on the Burrows-Wheeler transformation
• Algorithms for the Lyndon unique maximal factorization
• Combinatorics of unique maximal factorization families (UMFFs)
• Computation of words satisfying the ``rhythmic oddity property (after Simha Arom's works)
• Factorizing words over an ordered alphabet
• Free differential calculus. IV: The quotient groups of the lower central series
• Generic Algorithms for Factoring Strings
• Lyndon-like and V-order factorizations of strings
• Optimal algorithms for computing the canonical form of a circular string
• PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS
• Parallel RAM algorithms for factorizing words
• Periodic musical sequences and Lyndon words
• String comparison and Lyndon-like factorization using V-order in linear time

Cited in

(14)

• A bijective variant of the Burrows-Wheeler transform using V-order
• Analyzing strings with ordered Lyndon-like structures
• A Linear Time Algorithm for Ordered Partition
• Simple linear comparison of strings in \(V\)-order
• \(V\)-words, Lyndon words and substring circ-UMFFs
• V-order: new combinatorial properties \& a simple comparison algorithm
• Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order
• A survey of string orderings and their application to the Burrows-Wheeler transform
• Reconstructing a string from its Lyndon arrays
• String comparison and Lyndon-like factorization using V-order in linear time
• Lyndon-like and V-order factorizations of strings
• Linear construction of a left Lyndon tree
• Simple linear comparison of strings in \(V\)-order (extended abstract)
• Generic Algorithms for Factoring Strings

Describes a project that uses

Uses Software

• STAR

This page was built for publication: A linear partitioning algorithm for hybrid Lyndons using \(V\)-order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390899)