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

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• 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

Cited in

(17)

• On Arch Factorization and Subword Universality for Words and Compressed Words
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• Heuristic approaches to the distinguishing substring selection problem
• Longest Common Subsequence with Gap Constraints
• Absent subsequences in words
• Ranking and Unranking k-Subsequence Universal Words
• Subsequences in bounded ranges: matching and analysis problems
• On the Simon's congruence neighborhood of languages
• On Simon's congruence closure of a string
• The shortest common nonsubsequence problem is NP-complete
• Absent Subsequences in Words
• Matching patterns with variables under Simon's congruence
• Simon's congruence pattern matching
• Scattered Factor-Universality of Words
• Combinatorial algorithms for subsequence matching: a survey
• On Simon's congruence closure of a string
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence

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)