Finite automata based algorithms on subsequences and supersequences of degenerate strings

DOI10.1016/j.jda.2008.10.004zbMath1201.68066OpenAlexW1994713788MaRDI QIDQ972350

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

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)

Related Items (8)

Indeterminate string factorizations and degenerate text transformations ⋮ Palindromic subsequence automata and longest common palindromic subsequence ⋮ Computing the longest common almost-increasing subsequence ⋮ Doubly-constrained LCS and hybrid-constrained LCS problems revisited ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New efficient algorithms for the LCS and constrained LCS problems
• The constrained longest common subsequence problem
• The string merging problem
• A simple algorithm for the constrained sequence problems
• Searching subsequences
• Calcul de la distance par les sous-mots
• 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 Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• Algorithms on Strings, Trees and Sequences
• The String-to-String Correction Problem
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

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