Some remarks about stabilizers

We continue our study of stabilizers of infinite words over finite alphabets, begun in [D. Krieger, On stabilizers of infinite words, Theoret. Comput. Sci. 400 (2008), 169-181]. Let w be an aperiodic infinite word over a finite alphabet, and let Stab(w) be its stabilizer. We show that Stab(w) can be partitioned into the monoid of morphisms that stabilize w by finite fixed points and the ideal of morphisms that stabilize w by iteration. We also settle a conjecture given in the paper mentioned above, by showing that in some cases -Stab(w) is infinitely generated. If the aforementioned ideal is nonempty, then it contains either polynomially growing morphisms or exponentially growing morphisms, but not both. Moreover, in the polynomial case, the degree of the polynomial is fixed. We also show how to compute the polynomial degree from the dependency graph of a polynomially growing morphism. (C) 2009 Elsevier B.V. All rights reserved.