2026-07-18T09:53:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8705 2024-03-06T10:43:00Z ddc:004 open_access

Quasi-Periodicity Under Mismatch Errors Amir, Amihood Levy, Avivit Porat, Ely Periodicity Quasi-Periodicity Cover Approximate Cover Tracing regularities plays a key role in data analysis for various areas of science, including coding and automata theory, formal language theory, combinatorics, molecular biology and many others. Part of the scientific process is understanding and explaining these regularities. A common notion to describe regularity in a string T is a cover or quasi-period, which is a string C for which every letter of T lies within some occurrence of C. In many applications finding exact repetitions is not sufficient, due to the presence of errors. In this paper we initiate the study of quasi-periodicity persistence under mismatch errors, and our goal is to characterize situations where a given quasi-periodic string remains quasi-periodic even after substitution errors have been introduced to the string. Our study results in proving necessary conditions as well as a theorem stating sufficient conditions for quasi-periodicity persistence. As an application, we are able to close the gap in understanding the complexity of Approximate Cover Problem (ACP) relaxations studied by [Amir 2017a, Amir 2017b] and solve an open question. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amihood Amir and Avivit Levy and Ely Porat 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.4 urn:nbn:de:0030-drops-87054 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.4 eng https://creativecommons.org/licenses/by/3.0/legalcode