Searching subsequences

DOI10.1016/0304-3975(91)90358-9zbMath0717.68070OpenAlexW2914364168MaRDI QIDQ2638800

Ricardo A. Baeza-Yates

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)90358-9

zbMATH Keywords

finite automatonlongest common subsequence problemsubsequence search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Related Items (29)

Subsequence automata with default transitions ⋮ A survey of temporal data mining ⋮ Fast and compact regular expression matching ⋮ The parameterized complexity of sequence alignment and consensus ⋮ Longest common subsequences ⋮ Absent Subsequences in Words ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ Longest Common Subsequence with Gap Constraints ⋮ Longest bordered and periodic subsequences ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Existential Definability over the Subword Ordering ⋮ Absent subsequences in words ⋮ Quadratic-time algorithm for a string constrained LCS problem ⋮ Verifying and enumerating parameterized border arrays ⋮ Unnamed Item ⋮ Asynchronous trace-matching automata ⋮ Order Preserving Pattern Matching on Trees and DAGs ⋮ Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts ⋮ Compressed subsequence matching and packed tree coloring ⋮ On trace inclusion optimization problems ⋮ Finite automata based algorithms on subsequences and supersequences of degenerate strings ⋮ Missing pattern discovery ⋮ Counting Parameterized Border Arrays for a Binary Alphabet ⋮ Matching subsequences in trees ⋮ Directed acyclic subsequence graph -- overview ⋮ The size of subsequence automaton ⋮ Multi-subsequence searching ⋮ Compact recognizers of episode sequences ⋮ A practical algorithm to find the best subsequence patterns

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Computing a longest common subsequence for a set of strings
• The smallest automaton recognizing the subwords of a text
• The longest common subsequence problem revisited
• The string merging problem
• An information-theoretic lower bound for the longest common subsequence problem
• On the computational power of pushdown automata
• Calcul de la distance par les sous-mots
• Bounds on the Complexity of the Longest Common Subsequence Problem
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences

This page was built for publication: Searching subsequences