Generic Algorithms for Factoring Strings

DOI10.1007/978-3-642-36899-8_18MaRDI QIDQ4915247zbMATH OpenOpenAlexFDO

Authors Jacqueline W. Daykin, Costas S. Iliopoulos, W. F. Smyth, David E. Daykin

Publication date 9 April 2013

Published in Information Theory, Combinatorics, and Search Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-36899-8_18

zbMATH Keywords

\(V\)-order\(V\)-wordcirc-UMFFcomplexityfactorgeneric algorithmslexicographic orderLyndon wordparallel algorithmPRAMRAMsequential algorithm

Mathematics Subject Classification ID

Combinatorics on words (68R15) Parallel algorithms in computer science (68W10) Algorithms on strings (68W32)

Recommendations

• Computing equality-free string factorisations
• Computing equality-free and repetitive string factorisations
• Enhanced string factoring from alphabet orderings
• String factorisations with maximum or minimum dimension
• Generalized factorizations of words and their algorithmic properties
• Efficient parallel algorithms to test square-freeness and factorize strings
• scientific article; zbMATH DE number 7651108
• Off-line and on-line algorithms for closed string factorization
• Factorizing a String into Squares in Linear Time
• Factorizing strings into repetitions

Cites work

• A bijective variant of the Burrows-Wheeler transform using V-order
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• 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
• scientific article; zbMATH DE number 417855 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1146223 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Infinite Lyndon words
• Lyndon + Christoffel = digitally convex
• Lyndon-like and V-order factorizations of strings
• Optimal algorithms for computing the canonical form of a circular string
• Parallel RAM algorithms for factorizing words
• Periodic musical sequences and Lyndon words
• PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS
• Properties of the extremal infinite smooth words
• Simple real-time constant-space string matching
• String comparison and Lyndon-like factorization using V-order in linear time
• Two-way string-matching

Cited in

(17)

• Parallel RAM algorithms for factorizing words
• Reconstructing a string from its Lyndon arrays
• Enhanced string factoring from alphabet orderings
• Lyndon-like and V-order factorizations of strings
• Lyndon factorization algorithms for small alphabets and run-length encoded strings
• String factorisations with maximum or minimum dimension
• A bijective variant of the Burrows-Wheeler transform using V-order
• Computing equality-free and repetitive string factorisations
• String comparison and Lyndon-like factorization using V-order in linear time
• Algorithms for the Lyndon unique maximal factorization
• Combinatorics of unique maximal factorization families (UMFFs)
• PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• Fast parallel Lyndon factorization with applications
• Analyzing strings with ordered Lyndon-like structures
• Factorizing a String into Squares in Linear Time
• scientific article; zbMATH DE number 7740932 (Why is no real title available?)

This page was built for publication: Generic Algorithms for Factoring Strings

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