Constructing premaximal ternary square-free words of any level

Abstract

We study extendability of ternary square-free words. Namely, we are interested in the square-free words that cannot be infinitely extended preserving square-freeness. We prove that any positive integer is the length of the longest extension of some ternary square-free word and thus solve an open problem by Allouche and Shallit. We also resolve the two-sided version of this problem. © 2012 Springer-Verlag.