Parallel RAM algorithms for factorizing words

DOI10.1016/0304-3975(94)90100-7zbMATH Open0805.68057OpenAlexW1978807535MaRDI QIDQ1325834FDOQ1325834

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

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

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)

Cites Work

• Title not available (Why is that?)
• Factorizing words over an ordered alphabet
• Free differential calculus. IV: The quotient groups of the lower central series
• Title not available (Why is that?)
• Optimal algorithms for computing the canonical form of a circular string
• Fast parallel Lyndon factorization with applications

Cited In (18)

• On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties
• Longest Lyndon Substring After Edit
• Title not available (Why is that?)
• Inferring strings from Lyndon factorization
• Lyndon factorization of grammar compressed texts revisited
• Dynamic and internal longest common substring
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• Suffix array and Lyndon factorization of a text
• Dynamic programming on the word RAM
• Towards optimal packed string matching
• PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS
• String comparison and Lyndon-like factorization using V-order in linear time
• Lyndon-like and V-order factorizations of strings
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Fast parallel Lyndon factorization with applications
• Generic Algorithms for Factoring Strings
• 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)