Parallel RAM algorithms for factorizing words

DOI10.1016/0304-3975(94)90100-7zbMath0805.68057OpenAlexW1978807535MaRDI QIDQ1325834

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

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)

Related Items (15)

Inferring strings from Lyndon factorization ⋮ A linear partitioning algorithm for hybrid Lyndons using \(V\)-order ⋮ A new class of string transformations for compressed text indexing ⋮ Suffix array and Lyndon factorization of a text ⋮ Towards optimal packed string matching ⋮ PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS ⋮ Dynamic and internal longest common substring ⋮ Faster Lyndon factorization algorithms for SLP and LZ78 compressed text ⋮ String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time ⋮ Generic Algorithms for Factoring Strings ⋮ On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties ⋮ Inverse Lyndon words and inverse Lyndon factorizations of words ⋮ Lyndon-like and V-order factorizations of strings ⋮ Longest Lyndon Substring After Edit ⋮ Lyndon factorization of grammar compressed texts revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal algorithms for computing the canonical form of a circular string
• Factorizing words over an ordered alphabet
• Fast parallel Lyndon factorization with applications
• Free differential calculus. IV: The quotient groups of the lower central series

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