Optimal parallel algorithms for periods, palindromes and squares
From MaRDI portal
Publication:5204325
DOI10.1007/3-540-55719-9_82zbMath1425.68466MaRDI 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
parallel algorithm; string matching; palindromes; square-free words; input string; periods of a words
68R15: Combinatorics on words
68W10: Parallel algorithms in computer science
68W32: Algorithms on strings
Related Items
Approximate periods of strings, A work-time optimal algorithm for computing all string covers, Parallel detection of all palindromes in a string, Fast parallel string prefix-matching, Testing string superprimitivity in parallel, Finding maximal 2-dimensional palindromes, Finding approximate palindromes in strings, Parallel two dimensional witness computation
Cites Work
- 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
- Unnamed Item
- Unnamed Item
