Testing string superprimitivity in parallel

DOI10.1016/0020-0190(94)90060-4zbMath0795.68092OpenAlexW2024070750MaRDI QIDQ1318749

Dany Breslauer

Publication date: 5 April 1994

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

Full work available at URL: https://hal.inria.fr/inria-00070009/file/RT-0160.pdf

zbMATH Keywords

parallel algorithmsstring matchingperiodssuperprimitivityquasiperiods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Related Items

Finding all periods and initial palindromes of a string in parallel, Can we recover the cover?, Experimental evaluation of algorithms for computing quasiperiods, Efficient Computation of 2-Covers of a String., A work-time optimal algorithm for computing all string covers, Fast parallel string prefix-matching, ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS, Optimality of some algorithms to detect quasiperiodicities, Approximate periods of strings, Approximate cover of strings, Quasiperiodicity and string covering, Normal forms of quasiperiodic strings, Quasi-Periodicity Under Mismatch Errors

Cites Work

• Unnamed Item
• Fast parallel string prefix-matching
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• An on-line string superprimitivity test
• Finding all periods and initial palindromes of a string in parallel
• Covering a string
• An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
• A Lower Bound for Parallel String Matching
• Recursive Star-Tree Parallel Data Structure
• Efficiency of a Good But Not Linear Set Union Algorithm
• The Parallel Evaluation of General Arithmetic Expressions
• Optimal parallel algorithms for periods, palindromes and squares