Longest Common Subsequence with Gap Constraints

DOI10.1007/978-3-031-33180-0_5arXiv2304.05270OpenAlexW4381302785MaRDI QIDQ6134862

Florin Manea, Stefan Siemer, Maria Kosche, Duncan Adamson, Tore Koß

Publication date: 25 July 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2304.05270

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (2)

Longest Common Subsequence with Gap Constraints ⋮ Simon's congruence pattern matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized Pascal triangle for binomial coefficients of words
• String matching with variable length gaps
• Another generalization of abelian equivalence: binomial complexity of infinite words
• An algorithm for distinguishing efficiently bit-strings by their subsequences
• Absoluteness of subword inequality is undecidable
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• Directed acyclic subsequence graph -- overview
• Subword histories and Parikh matrices
• Languages ordered by the subword order
• Connections between subwords and certain matrix mappings
• On the index of Simon's congruence for piecewise testability
• Unshuffling a square is NP-hard
• Searching subsequences
• Absent subsequences in words
• Algorithms for Computing the Longest Parameterized Common Subsequence
• Longest common subsequences of two random sequences
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Software Descriptions with Flow Expressions
• Algorithms for the Longest Common Subsequence Problem
• An approach to software system modelling and analysis
• The Complexity of Downward Closure Comparisons
• Querying Regular Languages over Sliding Windows
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
• Scattered Factor-Universality of Words
• The Subtrace Order and Counting First-Order Logic
• Consequences of Faster Alignment of Sequences
• The Height of Piecewise-Testable Languages with Applications in Logical Complexity
• Computing the \(k\)-binomial complexity of the Thue-Morse word
• Longest Common Subsequence with Gap Constraints
• Subsequences in bounded ranges: matching and analysis problems

This page was built for publication: Longest Common Subsequence with Gap Constraints