Geodesic
Growth functions, rewriting systems, and the Euler characteristic
Matematičeskie zametki, Tome 58 (1995) no. 5, pp. 653-668.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{MZM_1995_58_5_a1,
     author = {R. I. Grigorchuk},
     title = {Growth functions, rewriting systems, and the {Euler} characteristic},
     journal = {Matemati\v{c}eskie zametki},
     pages = {653--668},
     publisher = {mathdoc},
     volume = {58},
     number = {5},
     year = {1995},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1995_58_5_a1/}
}
TY  - JOUR
AU  - R. I. Grigorchuk
TI  - Growth functions, rewriting systems, and the Euler characteristic
JO  - Matematičeskie zametki
PY  - 1995
SP  - 653
EP  - 668
VL  - 58
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_1995_58_5_a1/
LA  - ru
ID  - MZM_1995_58_5_a1
ER  - 
%0 Journal Article
%A R. I. Grigorchuk
%T Growth functions, rewriting systems, and the Euler characteristic
%J Matematičeskie zametki
%D 1995
%P 653-668
%V 58
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_1995_58_5_a1/
%G ru
%F MZM_1995_58_5_a1
R. I. Grigorchuk. Growth functions, rewriting systems, and the Euler characteristic. Matematičeskie zametki, Tome 58 (1995) no. 5, pp. 653-668. http://geodesic.mathdoc.fr/item/MZM_1995_58_5_a1/

[1] Revesz G. I., Introduction to formal languages, McGraw–Hill Book Company, N. Y., 1983

[2] Lifshits A. N., “K probleme izomorfizma skhem Bernulli”, Teoriya veroyatn. i ee prilozh., 19:2 (1974), 409–416 | MR

[3] Grigorchuk R. I., Stepin A. M., “O kodirovanii sdvigov Markova”, Sb. dokladov VII Vsesoyuznoi konferentsii po teorii kodirovaniya i peredachi informatsii, Ch. 1, Moskva–Vilnyus, 1978, 41–46

[4] Stepin A. M., Tagi-Zade A. T., “O kombinatornoi interpretatsii entropii simvolicheskikh sistem”, Matem. zametki, 46:2 (1989), 114–121 | MR

[5] Anik D. J., “On the homology of associative algebras”, Trans. Amer. Math. Soc., 296 (1986), 641–659 | DOI | MR

[6] Golod E. S., Shafarevich I. R., “O bashne polei klassov”, Izv. AN SSSR. Ser. matem., 28 (1964), 261–272 | MR | Zbl

[7] Bourbaki N., Groups et algebres de Lie, Hermann, Paris, 1968

[8] Cannon J. W., The growth of the closed surface groups and the compact hyperbolic Coxeter groups, Preprint, Boston, 1979

[9] Serre J. P., “Cohomologie des groups discrets”, Prospects in Mathematics, Ann. Math. Stud., 70, Princeton, 1971

[10] Parry W., “Counterexamples involving growth series and the Euler characteristic”, Proc. Amer. Math. Soc., 102:1 (1988), 49–51 | DOI | MR | Zbl

[11] Cohen D. E., “String rewriting: a survey for group theorist”, Geometric Group Theory, V. 1 (Sussex, 1991), London Math. Soc. Lect. Note Series, 181, 1993, 37–47 | Zbl

[12] Epstein D. B. A., Cannon J. W., Holt D. F., Levy S. V. F., Paterson M. S., Thurston W. P., Word processing in groups, Jones and Bartlett, Boston, 1992 | Zbl

[13] Mamagani M. Dzh., “O funktsiyakh rosta grupp poverkhnostei”, Matem. zametki, 58:5 (1995), 681–693 | MR | Zbl

[14] Groves J. R. J., “Rewriting systems and homology of groups”, Proceedings of Conberra Group Theory Conf., Lect. Notes in Math., ed. L. G. Kovacs, Springer, N. Y., 1995

[15] Squier C. C., “Word problems and a homological finiteness conditions for monoids”, J. Pure Appl. Algebra, 49 (1987), 201–217 | DOI | MR | Zbl

[16] Brown K. S., “The geometry of rewriting systems: a proof of the Anik–Groves– Squier Theorem”, Algorithms and classification in Group Theory, MSRI Publication, 23, Springer, N. Y., 1992, 137–163

[17] Bergman G. M., “The diamond lemma for ring theory”, Adv. in Math., 29 (1978), 178–218 | DOI | MR | Zbl

[18] Smythe N., “Growth functions and Euler series”, Invent. math., 77 (1984), 517–531 | DOI | MR | Zbl

[19] Ufnarovskii V. A., “Ob ispolzovanii grafov dlya vychisleniya bazisa, ryadov Gilberta i rosta assotsiativnykh algebr”, Matem. sb., 180:11 (1989), 1548–1560 | MR | Zbl