An algorithm for distinguishing efficiently bit-strings by their subsequences

DOI10.1016/0304-3975(91)90170-7zbMath0724.68044OpenAlexW1971915878MaRDI QIDQ758204

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

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

Related Items (15)

Scattered Factor-Universality of Words ⋮ On the Simon's congruence neighborhood of languages ⋮ Absent Subsequences in Words ⋮ 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 ⋮ Simon's congruence pattern matching ⋮ Absent subsequences in words ⋮ Unnamed Item ⋮ The shortest common nonsubsequence problem is NP-complete ⋮ Nearly \(k\)-universal words -- investigating a part of Simon's congruence ⋮ On Simon's congruence closure of a string ⋮ Nearly \(k\)-universal words -- investigating a part of Simon's congruence ⋮ On Simon's congruence closure of a string

Cites Work

• A linear space algorithm for the LCS problem
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• Calcul de la distance par les sous-mots
• Unnamed Item

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