Normal Sequences with Non-Maximal Automatic Complexity

Abstract

This paper examines Automatic Complexity, a complexity notion introduced by Shallit and Wang in 2001. We demonstrate that there exists a normal sequence $T$ such that $I(T)=0$ and $S(T)\le 1/2$, where $I(T)$ and $S(T)$ are the lower and upper automatic complexity rates of $T$ respectively. We furthermore show that there exists a Champernowne sequence $C$, i.e. a sequence formed by concatenating all strings of length $1$ followed by concatenating all strings of length $2$ and so on, such that $S(C)\le 2/3$.

Conference Version: FSTTCS 2021: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - December 2021 - Gao, India

References in corpus (3)

• Finite-State Dimension and Lossy Decompressors
• Automatic complexity of shift register sequences
• A Normal Sequence Compressed by PPM${}^{\ast }$ but not by Lempel-Ziv 78