Forbidden words in symbolic dynamics

We introduce an equivalence relation similar or equal to between functions from N to N. By describing a symbolic dynamical system in terms of forbidde n words, we prove that the similar or equal to -equivalence class of the fu nction that counts the minimal forbidden words of a system is a topological invariant of the system. We show that the new invariant is independent fro m previous ones, but it is not characteristic. In the case of sofic systems , we prove that the similar or equal to equivalence of the corresponding fu nctions is a decidable question. As a more special application, we show, by using the new invariant, that two systems associated to Sturmian words hav ing "different slope" are not conjugate. (C) 2000 Academic Press.