Testing string superprimitivity in parallel

DOI10.1016/0020-0190(94)90060-4MaRDI QIDQ1318749zbMATH OpenOpenAlexFDO

Authors 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 algorithmsperiodsstring matchingsuperprimitivityquasiperiods

Mathematics Subject Classification ID

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

Recommendations

• Optimal superprimitivity testing for strings
• An on-line string superprimitivity test
• Efficient parallel algorithms to test square-freeness and factorize strings
• Efficient parallel string comparison
• Parallel and sequential approximation of shortest superstrings
• scientific article; zbMATH DE number 4205980
• Optimal parallel detection of squares in strings
• Sequential and Parallel Approximation of Shortest Superstrings
• On testing consecutive-ones property in parallel
• A Lower Bound for Parallel String Matching

Cites work

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

Cited in

(15)

• A work-time optimal algorithm for computing all string covers
• Quasi-periodicity under mismatch errors
• Efficient Computation of 2-Covers of a String.
• Optimality of some algorithms to detect quasiperiodicities
• Approximate cover of strings
• ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS
• Can we recover the cover?
• Normal forms of quasiperiodic strings
• Quasiperiodicity and string covering
• Experimental evaluation of algorithms for computing quasiperiods
• Finding all periods and initial palindromes of a string in parallel
• An on-line string superprimitivity test
• Fast parallel string prefix-matching
• Approximation and fixed parameter algorithms for the approximate cover problem
• Approximate periods of strings

This page was built for publication: Testing string superprimitivity in parallel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1318749)