A Lower Bound for Parallel String Matching

DOI10.1137/0221050zbMath0756.68048OpenAlexW2168396231MaRDI QIDQ4015971

Dany Breslauer, Zvi Galil

Publication date: 6 December 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221050

zbMATH Keywords

lower boundstring matchingperiodCRCW-PRAM

Mathematics Subject Classification ID

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

Related Items (13)

Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ Parallel two dimensional witness computation ⋮ Finding all periods and initial palindromes of a string in parallel ⋮ On the lower bound for parallel string matching ⋮ On the lower bound for parallel string matching ⋮ Towards optimal packed string matching ⋮ Efficient string matching on packed texts ⋮ Optimal parallel algorithms for Prefix Matching ⋮ A work-time optimal algorithm for computing all string covers ⋮ Fast parallel string prefix-matching ⋮ Optimal parallel algorithms for periods, palindromes and squares ⋮ Quasiperiodicity and string covering ⋮ Testing string superprimitivity in parallel

This page was built for publication: A Lower Bound for Parallel String Matching