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

The so-called "one-bit catastrophe" for the compression algorithm LZ'78 askswhether the compression ratio of an infinite word can change when a single bitis added in front of it. We answer positively this open question raised by Lutzand others: we show that there exists an infinite word $w$ such that$\rho_{sup}(w)=0$ but $\rho_{inf}(0w)>0$, where $\rho_{sup}$ and $\rho_{inf}$are respectively the $\limsup$ and the $\liminf$ of the compression ratios$\rho$ of the prefixes. To that purpose we explore the behaviour of LZ'78 onfinite words and show the following results:  - There is a constant $C>0$ such that, for any finite word $w$ and any letter$a$, $\rho(aw)\leq C\sqrt{\rho(w)\log|w|}$. Thus, sufficiently compressiblewords ($\rho(w)=o(1/\log|w|)$) remain compressible with a letter in front;  - The previous result is tight up to a multiplicative constant for anycompression ratio $\rho(w)=O(1/\log|w|)$. In particular, there are infinitelymany words $w$ satisfying $\rho(w)=O(1/\log|w|)$ but $\rho(0w)=\Omega(1)$.

Lempel-Ziv: a "one-bit catastrophe" but not a tragedy