Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems

2022/06/28 by Day, Joel D., Kosche, Maria, Manea, Florin +1 · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2206.13896

Abstract

We consider subsequences with gap constraints, i.e., length-k subsequences p that can be embedded into a string w such that the induced gaps (i.e., the factors of w between the positions to which p is mapped to) satisfy given gap constraints gc = (C₁, C₂, ..., C_k-1); we call p a gc-subsequence of w. In the case where the gap constraints gc are defined by lower and upper length bounds C_i = (L^-_i, L⁺_i) ∈ ℕ² and/or regular languages C_i ∈ REG, we prove tight (conditional on the orthogonal vectors (OV) hypothesis) complexity bounds for checking whether a given p is a gc-subsequence of a string w. We also consider the whole set of all gc-subsequences of a string, and investigate the complexity of the universality, equivalence and containment problems for these sets of gc-subsequences.

Cited by

• Are Depth-2 Regular Expressions Hard to Intersect?

Related

• Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
• Longest Common Subsequence with Gap Constraints
• Subsequences in Bounded Ranges: Matching and Analysis Problems
• Subsequence Matching and LCS with Segment Number Constraints
• Gap theorems for robust satisfiability: Boolean CSPs and beyond