Efficient parallel algorithms to test square-freeness and factorize strings

DOI10.1016/0020-0190(91)90223-5MaRDI QIDQ1178198zbMATH OpenOpenAlexFDO

Authors Wojciech Rytter, Maxime Crochemore

Publication date 26 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90223-5

zbMATH Keywords

CRCW PRAM

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computing methodologies for text processing; mathematical typography (68U15) Distributed algorithms (68W15)

Recommendations

• Optimal parallel detection of squares in strings
• An Optimal O(\log \log N)-Time Parallel Algorithm for Detecting all Squares in a String
• Simple parallel algorithms for primality testing and integer factorization
• Computing equality-free and repetitive string factorisations
• scientific article; zbMATH DE number 1424533
• Optimal parallel algorithms for periods, palindromes and squares (extended abstract)
• Computing equality-free string factorisations
• scientific article; zbMATH DE number 554529
• scientific article; zbMATH DE number 4165009

Cites work

• A universal algorithm for sequential data compression
• An O(logn) parallel connectivity algorithm
• An O(n log n) algorithm for finding all repetitions in a string
• An optimal algorithm for computing the repetitions in a word
• scientific article; zbMATH DE number 4205980 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3913711 (Why is no real title available?)
• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• Optimal off-line detection of repetitions in a string
• Parallel construction of a suffix tree with applications
• Transducers and repetitions

Cited in

(24)

• Optimal parallel detection of squares in strings
• Testing string superprimitivity in parallel
• Parallel RAM algorithms for factorizing words
• P-complete problems in data compression
• Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.
• Lempel-Ziv data compression on parallel and distributed systems
• Detecting regularities on grammar-compressed strings
• Computing equality-free and repetitive string factorisations
• On prefix/suffix-square free words
• Un réseau linéaire pour la reconnaissance des mots sans carré
• Efficient string matching on packed texts
• An efficient algorithm to test square-freeness of strings compressed by straight-line programs
• Generic Algorithms for Factoring Strings
• Optimal parallel algorithms for periods, palindromes and squares (extended abstract)
• Factorizing a String into Squares in Linear Time
• An efficient algorithm to test square-freeness of strings compressed by balanced straight line programs
• An Optimal O(\log \log N)-Time Parallel Algorithm for Detecting all Squares in a String
• Parallelism and dictionary based data compression
• scientific article; zbMATH DE number 7740932 (Why is no real title available?)
• Sublinear time Lempel-Ziv (LZ77) factorization
• New advances in rightmost Lempel-Ziv
• Optimal bounds for distinct quartics
• Counting distinct square substrings in sublinear time
• An efficient algorithm for online square detection

This page was built for publication: Efficient parallel algorithms to test square-freeness and factorize strings

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