Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917653268922368 |
|---|---|
| author | Bathie, Gabriel Kociumaka, Tomasz Starikovskaya, Tatiana |
| author_facet | Bathie, Gabriel Kociumaka, Tomasz Starikovskaya, Tatiana |
| contents | We study the online variant of the language distance problem for two classical formal languages, the language of palindromes and the language of squares, and for the two most fundamental distances, the Hamming distance and the edit (Levenshtein) distance. In this problem, defined for a fixed formal language $L$, we are given a string $T$ of length $n$, and the task is to compute the minimal distance to $L$ from every prefix of $T$. We focus on the low-distance regime, where one must compute only the distances smaller than a given threshold $k$. In this work, our contribution is twofold:
- First, we show streaming algorithms, which access the input string $T$ only through a single left-to-right scan. Both for palindromes and squares, our algorithms use $O(k \cdot\mathrm{poly}~\log n)$ space and time per character in the Hamming-distance case and $O(k^2 \cdot\mathrm{poly}~\log n)$ space and time per character in the edit-distance case. These algorithms are randomised by necessity, and they err with probability inverse-polynomial in $n$.
- Second, we show deterministic read-only online algorithms, which are also provided with read-only random access to the already processed characters of $T$. Both for palindromes and squares, our algorithms use $O(k \cdot\mathrm{poly}~\log n)$ space and time per character in the Hamming-distance case and $O(k^4 \cdot\mathrm{poly}~\log n)$ space and amortised time per character in the edit-distance case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_14788 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares Bathie, Gabriel Kociumaka, Tomasz Starikovskaya, Tatiana Data Structures and Algorithms We study the online variant of the language distance problem for two classical formal languages, the language of palindromes and the language of squares, and for the two most fundamental distances, the Hamming distance and the edit (Levenshtein) distance. In this problem, defined for a fixed formal language $L$, we are given a string $T$ of length $n$, and the task is to compute the minimal distance to $L$ from every prefix of $T$. We focus on the low-distance regime, where one must compute only the distances smaller than a given threshold $k$. In this work, our contribution is twofold: - First, we show streaming algorithms, which access the input string $T$ only through a single left-to-right scan. Both for palindromes and squares, our algorithms use $O(k \cdot\mathrm{poly}~\log n)$ space and time per character in the Hamming-distance case and $O(k^2 \cdot\mathrm{poly}~\log n)$ space and time per character in the edit-distance case. These algorithms are randomised by necessity, and they err with probability inverse-polynomial in $n$. - Second, we show deterministic read-only online algorithms, which are also provided with read-only random access to the already processed characters of $T$. Both for palindromes and squares, our algorithms use $O(k \cdot\mathrm{poly}~\log n)$ space and time per character in the Hamming-distance case and $O(k^4 \cdot\mathrm{poly}~\log n)$ space and amortised time per character in the edit-distance case. |
| title | Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2309.14788 |