Growth functions,rewriting systems,and the Euler characteristic

We present a formula that expresses the number of admissible words for an arbitrary system of prohibitions in terms of the generating series. We also indicate applications of this formula to the calculation of the topological entropy of symbolic systems and to the calculation of growth functions of groups and algebras. Translated fromMatematicheskie Zametki, Vol. 58, No. 5, pp. 653–668, November, 1995. This research was partially supported by the Russian Foundation for Basic Research under grant No. 94-01-00820 and by the International Science Foundation grant MV1000.