Fast parallel Lyndon factorization with applications

DOI10.1007/BF01191471zbMath0815.68066MaRDI QIDQ4327381

Alberto Apostolico, Maxime Crochemore

Publication date: 5 April 1995

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

zbMATH Keywords

Lyndon decomposition

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (19)

Parallel RAM algorithms for factorizing words ⋮ Extended suffix array construction using Lyndon factors ⋮ Indeterminate string factorizations and degenerate text transformations ⋮ Inferring strings from Lyndon factorization ⋮ Convexity preserving deformations of digital sets: characterization of removable and insertable pixels ⋮ Suffix array and Lyndon factorization of a text ⋮ On generalized Lyndon words ⋮ Finding the cyclic covers of a string ⋮ Dynamic and internal longest common substring ⋮ Optimal algorithms for computing the canonical form of a circular string ⋮ Faster Lyndon factorization algorithms for SLP and LZ78 compressed text ⋮ 2D Lyndon words and applications ⋮ On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties ⋮ Lyndon factorization algorithms for small alphabets and run-length encoded strings ⋮ Unnamed Item ⋮ 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
• 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

This page was built for publication: Fast parallel Lyndon factorization with applications