Optimal parallel algorithms for periods, palindromes and squares
From MaRDI portal
Publication:5204325
DOI10.1007/3-540-55719-9_82zbMath1425.68466OpenAlexW1519893856MaRDI QIDQ5204325
Alberto Apostolico, Dany Breslauer, Zvi Galil
Publication date: 4 December 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55719-9_82
Combinatorics on words (68R15) Parallel algorithms in computer science (68W10) Algorithms on strings (68W32)
Related Items (10)
Parallel two dimensional witness computation ⋮ Efficient algorithms for Lempel-Ziv encoding ⋮ Unnamed Item ⋮ A work-time optimal algorithm for computing all string covers ⋮ Finding maximal 2-dimensional palindromes ⋮ Parallel detection of all palindromes in a string ⋮ Fast parallel string prefix-matching ⋮ Approximate periods of strings ⋮ Finding approximate palindromes in strings ⋮ Testing string superprimitivity in parallel
Cites Work
- Unnamed Item
- Unnamed Item
- The equation \(a_ M=b^ Nc^ P\) in a free group
- An optimal algorithm for computing the repetitions in a word
- Optimal off-line detection of repetitions in a string
- Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
- Efficient parallel algorithms to test square-freeness and factorize strings
- Optimal parallel detection of squares in strings
- Transducers and repetitions
- Finding all periods and initial palindromes of a string in parallel
- An O(n log n) algorithm for finding all repetitions in a string
- An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
- Optimal parallel pattern matching in strings
- Relations between Concurrent-Write Models of Parallel Computation
- A Lower Bound for Parallel String Matching
- Fast Pattern Matching in Strings
- The Parallel Evaluation of General Arithmetic Expressions
- Optimal bounds for decision problems on the CRCW PRAM
- An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
This page was built for publication: Optimal parallel algorithms for periods, palindromes and squares
