License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17349/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-ISAAC-2022-64.pdf (1 MB)

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
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI