Finite automata based algorithms on subsequences and supersequences of degenerate strings

DOI10.1016/J.JDA.2008.10.004zbMATH Open1201.68066OpenAlexW1994713788MaRDI QIDQ972350FDOQ972350

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

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

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)

Cites Work

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

Cited In (9)

• The finite automata approaches in stringology
• Palindromic subsequence automata and longest common palindromic subsequence
• 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
• Computing the longest common almost-increasing subsequence
• A new approach to regular \& indeterminate strings
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Constrained sequence analysis algorithms in computational biology

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)