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

Shallit and Wang studied deterministic automatic complexity of words.  They showed that the automatic Hausdorff dimension $I(\mathbf t)$ of the infinite Thue word satisfies $1/3\le I(\mathbf t)\le 1/2$.   We improve that result by showing that $I(\mathbf t)= 1/2$.  We prove that the nondeterministic automatic complexity $A_N(x)$ of a word $x$ of length $n$ is bounded by $b(n):=\lfloor n/2\rfloor + 1$.  This enables us to define the complexity deficiency $D(x)=b(n)-A_N(x)$.  If $x$ is square-free then $D(x)=0$. If $x$ is almost square-free in the sense of Fraenkel and Simpson, or if $x$ is a overlap-free binary word such as the infinite Thue--Morse word, then $D(x)\le 1$.  On the other hand, there is no constant upper bound on $D$ for overlap-free words over a ternary alphabet, nor for cube-free words over a binary alphabet. The decision problem whether $D(x)\ge d$ for given $x$, $d$ belongs to $\mathrm{NP}\cap \mathrm{E}$.

Nondeterministic Automatic Complexity of Overlap-Free and Almost Square-Free Words