Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.64
URN: urn:nbn:de:0030-drops-173493
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17349/
Day, Joel D. ; Kosche, Maria ; Manea, Florin ; Schmid, Markus L.
Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems
| pdf-format: |
|
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_1, C_2, …, 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.
BibTeX - Entry
@InProceedings{day_et_al:LIPIcs.ISAAC.2022.64,
author = {Day, Joel D. and Kosche, Maria and Manea, Florin and Schmid, Markus L.},
title = {{Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {64:1--64:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17349},
URN = {urn:nbn:de:0030-drops-173493},
doi = {10.4230/LIPIcs.ISAAC.2022.64},
annote = {Keywords: String algorithms, subsequences with gap constraints, pattern matching, fine-grained complexity, conditional lower bounds, parameterised complexity}
}
| Keywords: | String algorithms, subsequences with gap constraints, pattern matching, fine-grained complexity, conditional lower bounds, parameterised complexity | |
| Seminar: | 33rd International Symposium on Algorithms and Computation (ISAAC 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 |
