An on-line string superprimitivity test

DOI10.1016/0020-0190(92)90111-8MaRDI QIDQ1209376zbMATH OpenOpenAlexFDO

Authors Dany Breslauer

Publication date 16 May 1993

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0020-0190(92)90111-8

zbMATH Keywords

on-line linear-time algorithmperiodquasiperiodstring matchingsuperprimitivity

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Recommendations

• Optimal superprimitivity testing for strings
• Testing string superprimitivity in parallel
• Publication:4503964
• Enhanced string covering
• An optimal algorithm to compute all the covers of a string

Cites work

• Efficient detection of quasiperiodicities in strings
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• Optimal superprimitivity testing for strings

Cited in

(56)

• Quasiperiodicity and string covering
• Testing string superprimitivity in parallel
• An optimal algorithm to compute all the covers of a string
• Normal forms of quasiperiodic strings
• Repetitive perhaps, but certainly not boring
• Efficient algorithms for shortest partial seeds in words
• Crochemore's partitioning on weighted strings and applications
• String covering with optimal covers
• Computing regularities in strings: a survey
• An extension of the periodicity lemma to longer periods
• Finding all periods and initial palindromes of a string in parallel
• Covering a string
• k-approximate quasiperiodicity under Hamming and edit distance
• String covers of a tree
• Experimental evaluation of algorithms for computing quasiperiods
• On approximate enhanced covers under Hamming distance
• Universal reconstruction of a string
• Approximate cover of strings
• On left and right seeds of a string
• Computing the \(\lambda \)-covers of a string
• Two strings at Hamming distance 1 cannot be both quasiperiodic
• Can we recover the cover?
• Inferring strings from cover arrays
• Efficient seeds computation revisited
• Computing covers using prefix tables
• Efficient seed computation revisited
• Enhanced string covering
• The set of parameterized k-covers problem
• Identifying all abelian periods of a string in quadratic time and relevant problems
• Fast algorithm for partial covers in words
• Linear-time computation of prefix table for weighted strings {\&} applications
• Quasi-Periodicity in Streams
• Computing runs on a trie
• Quasi-periodicity under mismatch errors
• The ``runs theorem
• Generalized approximate regularities in strings
• ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS
• Efficient Computation of 2-Covers of a String.
• Shortest covers of all cyclic shifts of a string
• Approximate periods of strings
• Finding the cyclic covers of a string
• String Covering: A Survey
• Subsequence covers of words
• Verifying and enumerating parameterized border arrays
• Approximation and fixed parameter algorithms for the approximate cover problem
• String covers of a tree revisited
• A work-time optimal algorithm for computing all string covers
• Internal quasiperiod queries
• Shortest cover after edit
• Finding the cyclic covers of a string
• Subsequence covers of words
• Computing string covers in sublinear time
• String 2-covers with no length restrictions
• Covers in optimal space
• Optimal superprimitivity testing for strings
• Optimality of some algorithms to detect quasiperiodicities

This page was built for publication: An on-line string superprimitivity test

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