On Stricter Reachable Repetitiveness Measures
Gonzalo Navarro and Cristian Urbina
The size b of the smallest bidirectional macro scheme, which is arguably
the most general copy-paste scheme to generate a given sequence, is considered
to be the strictest reachable measure of repetitiveness. It is strictly
lower-bounded by measures like γ and δ, which are known or believed to be unreachable and to capture the entropy of repetitiveness.
In this paper we study another sequence generation mechanism, namely
compositions of a morphism. We show that these form another plausible
mechanism to characterize repetitive sequences and define NU-systems, which
combine such a mechanism with macro schemes. We show that the size ν
≤ b of the smallest NU-system is reachable and can be o(δ) for some
string families, thereby implying that the limit of compressibility of
repetitive sequences can be even smaller than previously thought. We also
derive several other results characterizing ν.