Fast parallel Lyndon factorization with applications

DOI10.1007/BF01191471zbMath0815.68066MaRDI QIDQ4327381

Maxime Crochemore, Alberto Apostolico

Publication date: 5 April 1995

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

Lyndon decomposition

Mathematics Subject Classification ID

68Q42: Grammars and rewriting systems

Related Items

Suffix array and Lyndon factorization of a text, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, 2D Lyndon words and applications, Optimal algorithms for computing the canonical form of a circular string, Parallel RAM algorithms for factorizing words, Extended suffix array construction using Lyndon factors, Inverse Lyndon words and inverse Lyndon factorizations of words, Lyndon-like and V-order factorizations of strings, Indeterminate string factorizations and degenerate text transformations, Inferring strings from Lyndon factorization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A public key cryptosystem based on Lyndon words
• A linear time solution to the single function coarsest partition problem
• Parallel construction of a suffix tree with applications
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• Optimal canonization of all substrings of a string
• An improved algorithm to check for polygon similarity
• Factorizing words over an ordered alphabet
• Efficient Parallel Algorithms for String Editing and Related Problems
• Optimal parallel algorithms for string matching
• Relations between Concurrent-Write Models of Parallel Computation
• Fast canonization of circular strings
• Two-way string-matching
• Optimal bounds for decision problems on the CRCW PRAM
• Free differential calculus. IV: The quotient groups of the lower central series