English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the online variant of the language distance problem for twoclassical formal languages, the language of palindromes and the language ofsquares, and for the two most fundamental distances, the Hamming distance andthe edit (Levenshtein) distance. In this problem, defined for a fixed formallanguage $L$, we are given a string $T$ of length $n$, and the task is tocompute the minimal distance to $L$ from every prefix of $T$. We focus on thelow-distance regime, where one must compute only the distances smaller than agiven threshold $k$. In this work, our contribution is twofold:  - First, we show streaming algorithms, which access the input string $T$ onlythrough a single left-to-right scan. Both for palindromes and squares, ouralgorithms use $O(k \cdot\mathrm{poly}~\log n)$ space and time per character inthe Hamming-distance case and $O(k^2 \cdot\mathrm{poly}~\log n)$ space and timeper character in the edit-distance case. These algorithms are randomised bynecessity, and they err with probability inverse-polynomial in $n$.  - Second, we show deterministic read-only online algorithms, which are alsoprovided 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 theHamming-distance case and $O(k^4 \cdot\mathrm{poly}~\log n)$ space andamortised time per character in the edit-distance case.

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares