Lyndon-like and V-order factorizations of strings

DOI10.1016/S1570-8667(03)00039-XzbMath1100.68087WikidataQ114120140 ScholiaQ114120140MaRDI QIDQ1827280

Jacqueline W. Daykin, David E. Daykin

Publication date: 6 August 2004

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

zbMATH Keywords

lexicographic orderstringwordLyndon factorizationB-orderChen-Duval-Fox factorizationmaximal factorizationT-orderV-order

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (11)

Indeterminate string factorizations and degenerate text transformations ⋮ \(V\)-order: new combinatorial properties \& a simple comparison algorithm ⋮ A linear partitioning algorithm for hybrid Lyndons using \(V\)-order ⋮ Reconstructing a string from its Lyndon arrays ⋮ A survey of string orderings and their application to the Burrows-Wheeler transform ⋮ PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS ⋮ A bijective variant of the Burrows-Wheeler transform using \(V\)-order ⋮ Binary block order Rouen transform ⋮ String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time ⋮ Generic Algorithms for Factoring Strings ⋮ Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nonexistence of a Kruskal-Katona type theorem for subword orders
• Optimal canonization of all substrings of a string
• Optimal algorithms for computing the canonical form of a circular string
• Parallel RAM algorithms for factorizing words
• Factorizing words over an ordered alphabet
• Fast parallel Lyndon factorization with applications
• Ordering Integer Vectors for Coordinate Deletions
• On Burnside's Problem
• Free differential calculus. IV: The quotient groups of the lower central series
• On deleting coordinates from integer vectors

This page was built for publication: Lyndon-like and V-order factorizations of strings