{"ID":2886816,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.02231","arxiv_id":"2508.02231","title":"Testing Quasiperiodicity","abstract":"A cover (or quasiperiod) of a string $S$ is a shorter string $C$ such that every position of $S$ is contained in some occurrence of $C$ as a substring. The notion of covers was introduced by Apostolico and Ehrenfeucht over 30 years ago [Theor. Comput. Sci. 1993] and it has received significant attention from the combinatorial pattern matching community. In this note, we show how to efficiently test whether $S$ admits a cover. Our tester can also be translated into a streaming algorithm.","short_abstract":"A cover (or quasiperiod) of a string $S$ is a shorter string $C$ such that every position of $S$ is contained in some occurrence of $C$ as a substring. The notion of covers was introduced by Apostolico and Ehrenfeucht over 30 years ago [Theor. Comput. Sci. 1993] and it has received significant attention from the combin...","url_abs":"https://arxiv.org/abs/2508.02231","url_pdf":"https://arxiv.org/pdf/2508.02231v1","authors":"[\"Christine Awofeso\",\"Ben Bals\",\"Oded Lachish\",\"Solon P. Pissis\"]","published":"2025-08-04T09:31:09Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}