Finite automata based algorithms on subsequences and supersequences of degenerate strings

DOI10.1016/J.JDA.2008.10.004MaRDI QIDQ972350zbMATHOpenAlexFDO

Authors Costas S. Iliopoulos, M. Sohel Rahman, Michal Voráček, Ladislav Vagner

Publication date 25 May 2010

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

Full work available at URL https://doi.org/10.1016/j.jda.2008.10.004

zbMATH Keywords

finite automatalongest common subsequenceshortest common supersequenceconstrained longest common subsequencedegenerate strings

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithms on strings (68W32)

Recommendations

• The Constrained Longest Common Subsequence Problem for Degenerate Strings
• scientific article; zbMATH DE number 1962790
• The longest common subsequence problem -- a finite automata approach
• Algorithms for two versions of LCS problem for indeterminate strings
• The finite automata approaches in stringology

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Algorithms for two versions of LCS problem for indeterminate strings
• Algorithms on Strings, Trees and Sequences
• An Extension of the String-to-String Correction Problem
• Calcul de la distance par les sous-mots
• Linear Algorithm for Data Compression via String Matching
• New efficient algorithms for the LCS and constrained LCS problems
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Searching subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• The constrained longest common subsequence problem
• The string merging problem

Cited in

(9)

• Doubly-constrained LCS and hybrid-constrained LCS problems revisited
• Indeterminate string factorizations and degenerate text transformations
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• The finite automata approaches in stringology
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Computing the longest common almost-increasing subsequence
• Constrained sequence analysis algorithms in computational biology
• Palindromic subsequence automata and longest common palindromic subsequence
• A new approach to regular \& indeterminate strings

This page was built for publication: Finite automata based algorithms on subsequences and supersequences of degenerate strings

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