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

Electronic Journal Of Combinatorics

Kayleigh K. Hyde¹ 

关键词: automatic complexity;    nondeterministic finite automata;    almost square-free words;    strongly cube-free words;    combinatorics on words;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

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

【 授权许可】

Others