Subsequences with gap constraints: complexity bounds for matching and analysis problems

DOI10.4230/LIPICS.ISAAC.2022.64MaRDI QIDQ6602491zbMATH OpenFDO

Authors Joel D. Day, Maria Kosche, Florin Manea, Markus L. Schmid

Publication date 11 September 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2022.64

zbMATH Keywords

conditional lower boundsfine-grained complexityparameterised complexitypattern matchingstring algorithmssubsequences with gap constraints

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(7)

• Fast algorithms for window accumulated subsequence matching problem
• Tight bounds for the number of absent subsequences
• Subsequences with generalised gap constraints: upper and lower complexity bounds
• k-universality of regular languages revisited
• Longest common subsequence with gap constraints
• Generalized Parikh matrices for tracking subsequence occurrences
• Subsequence matching and analysis problems for formal languages

This page was built for publication: Subsequences with gap constraints: complexity bounds for matching and analysis problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6602491)