Directed acyclic subsequence graph -- overview

DOI10.1016/S1570-8667(03)00029-7MaRDI QIDQ1827273zbMATH OpenOpenAlexFDO

Authors Maxime Crochemore, Bořivoj Melichar, Zdeněk Troníček

Publication date 6 August 2004

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1570-8667(03)00029-7

zbMATH Keywords

Directed acyclic subsequence graphSearching subsequencesSubsequence automation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Searching subsequences
• scientific article; zbMATH DE number 1452985
• scientific article; zbMATH DE number 1962790
• scientific article; zbMATH DE number 2114411

Cites work

• Calcul de la distance par les sous-mots
• Computing a longest common subsequence for a set of strings
• Searching subsequences

Cited in

(26)

• A compact DAG for storing and searching maximal common subsequences
• Longest common subsequence with gap constraints
• Enumeration of maximal common subsequences between two strings
• On strings having the same length-k substrings
• Longest Common Subsequence with Gap Constraints
• Absent subsequences in words
• Quadratic-time algorithm for a string constrained LCS problem
• On trace inclusion optimization problems
• scientific article; zbMATH DE number 2114411 (Why is no real title available?)
• Subsequences in bounded ranges: matching and analysis problems
• On problems related to absent subsequences
• The edit distance to \(k\)-subsequence universality
• Efficiently testing Simon's congruence
• The size of subsequence automaton
• Absent Subsequences in Words
• Matching patterns with variables under Simon's congruence
• Fast algorithms for window accumulated subsequence matching problem
• Tight bounds for the number of absent subsequences
• McDag: indexing maximal common subsequences in practice
• Combinatorial algorithms for subsequence matching: a survey
• k-universality of regular languages revisited
• Subsequence matching and analysis problems for formal languages
• Searching subsequences
• Fast and compact regular expression matching
• The edit distance to k-subsequence universality
• Chaining of maximal exact matches in graphs

This page was built for publication: Directed acyclic subsequence graph -- overview

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