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.MFCS.2021.48
URN: urn:nbn:de:0030-drops-144886
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14488/
Gawrychowski, Paweł ;
Manea, Florin ;
Siemer, Stefan
Matching Patterns with Variables Under Hamming Distance
Abstract
A pattern α is a string of variables and terminal letters. We say that α matches a word w, consisting only of terminal letters, if w can be obtained by replacing the variables of α by terminal words. The matching problem, i.e., deciding whether a given pattern matches a given word, was heavily investigated: it is NP-complete in general, but can be solved efficiently for classes of patterns with restricted structure. In this paper, we approach this problem in a generalized setting, by considering approximate pattern matching under Hamming distance. More precisely, we are interested in what is the minimum Hamming distance between w and any word u obtained by replacing the variables of α by terminal words. Firstly, we address the class of regular patterns (in which no variable occurs twice) and propose efficient algorithms for this problem, as well as matching conditional lower bounds. We show that the problem can still be solved efficiently if we allow repeated variables, but restrict the way the different variables can be interleaved according to a locality parameter. However, as soon as we allow a variable to occur more than once and its occurrences can be interleaved arbitrarily with those of other variables, even if none of them occurs more than once, the problem becomes intractable.
BibTeX - Entry
@InProceedings{gawrychowski_et_al:LIPIcs.MFCS.2021.48,
author = {Gawrychowski, Pawe{\l} and Manea, Florin and Siemer, Stefan},
title = {{Matching Patterns with Variables Under Hamming Distance}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {48:1--48:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-201-3},
ISSN = {1868-8969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14488},
URN = {urn:nbn:de:0030-drops-144886},
doi = {10.4230/LIPIcs.MFCS.2021.48},
annote = {Keywords: Pattern with variables, Matching algorithms, Hamming distance, Conditional lower bounds, Patterns with structural restrictions}
}
|
Keywords: |
|
Pattern with variables, Matching algorithms, Hamming distance, Conditional lower bounds, Patterns with structural restrictions |
|
Collection: |
|
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
18.08.2021 |
