Nondeterministic automatic complexity of overlap-free and almost square-free words

Kayleigh Hyde, Bjørn Kjos-Hanssen

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…