An algorithm for distinguishing efficiently bit-strings by their subsequences

DOI10.1016/0304-3975(91)90170-7MaRDI QIDQ758204zbMATH OpenOpenAlexFDO

Authors Jean-Jacques Hébrard

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90170-7

zbMATH Keywords

factorizing stringsshortest subsequence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Parallel algorithms in computer science (68W10)

Cites work

• A faster algorithm computing string edit distances
• A linear space algorithm for the LCS problem
• A longest common subsequence algorithm suitable for similar text strings
• Calcul de la distance par les sous-mots
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)

Cited in

(29)

• The shortest common nonsubsequence problem is NP-complete
• Heuristic approaches to the distinguishing substring selection problem
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• On Simon's congruence closure of a string
• Absent subsequences in words
• Scattered Factor-Universality of Words
• On the Simon's congruence neighborhood of languages
• Absent Subsequences in Words
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• On Simon's congruence closure of a string
• Ranking and Unranking k-Subsequence Universal Words
• Longest Common Subsequence with Gap Constraints
• On Arch Factorization and Subword Universality for Words and Compressed Words
• Subsequences in bounded ranges: matching and analysis problems
• Combinatorial algorithms for subsequence matching: a survey
• Simon's congruence pattern matching
• Matching patterns with variables under Simon's congruence
• Tight bounds for the number of absent subsequences
• Subsequence matching and analysis problems for automata with translucent letters
• Jumbled scattered factors
• k-universality of regular languages
• k-universality of regular languages revisited
• The edit distance to k-subsequence universality
• \(k\)-universality of regular languages
• Longest common subsequence with gap constraints
• The edit distance to \(k\)-subsequence universality
• Efficiently testing Simon's congruence
• On strings having the same length-k substrings
• Subsequence matching and analysis problems for formal languages

This page was built for publication: An algorithm for distinguishing efficiently bit-strings by their subsequences

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