Parallel RAM algorithms for factorizing words

DOI10.1016/0304-3975(94)90100-7MaRDI QIDQ1325834zbMATH OpenOpenAlexFDO

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

Publication date 26 January 1995

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

Full work available at URL https://doi.org/10.1016/0304-3975(94)90100-7

zbMATH Keywords

Lyndon factorizationCRCW PRAM algorithmunbounded alphabet

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Distributed algorithms (68W15)

Recommendations

• Fast parallel Lyndon factorization with applications
• Generic Algorithms for Factoring Strings
• scientific article; zbMATH DE number 18629
• Efficient parallel algorithms to test square-freeness and factorize strings
• Factorizing words over an ordered alphabet

Cites work

• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Factorizing words over an ordered alphabet
• Fast parallel Lyndon factorization with applications
• Free differential calculus. IV: The quotient groups of the lower central series
• Optimal algorithms for computing the canonical form of a circular string

Cited in

(18)

• PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS
• Fast parallel Lyndon factorization with applications
• Generic Algorithms for Factoring Strings
• Lyndon factorization of grammar compressed texts revisited
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties
• Longest Lyndon Substring After Edit
• String comparison and Lyndon-like factorization using V-order in linear time
• Suffix array and Lyndon factorization of a text
• Dynamic and internal longest common substring
• scientific article; zbMATH DE number 18629 (Why is no real title available?)
• Inferring strings from Lyndon factorization
• Lyndon-like and V-order factorizations of strings
• Towards optimal packed string matching
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Dynamic programming on the word RAM
• Inverse Lyndon words and inverse Lyndon factorizations of words
• A new class of string transformations for compressed text indexing

This page was built for publication: Parallel RAM algorithms for factorizing words

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