Two-State Mealy Automata of Intermediate Growth over a Two-Letter Alphabet

I. I. Reznikov ; V. I. Sushchanskii

Matematičeskie zametki, Tome 72 (2002) no. 1, pp. 102-117.

Résumé

Two-state automata of intermediate growth over a two-letter alphabet are studied. The asymptotic behavior of the growth function is analyzed. A system of defining relations is found. It is proved that such a system cannot be finite.

Bibliographie

[1] Ufnarovskii V. A., “Kombinatornye i asimptoticheskie metody v algebre”, Itogi nauki i tekhniki. Sovremennye problemy matematiki. Fundamentalnye napravleniya, 57, VINITI, M., 1990, 5–177 | MR

[2] Babenko I. K., “Problemy rosta i ratsionalnosti v algebre i topologii”, UMN, 41:2 (1986), 95–142 | MR | Zbl

[3] Shvarts A. S., “Ob'emnye invarianty pokrytii”, Dokl. AN SSSR, 105 (1955), 32–34 | MR | Zbl

[4] Milnor J., “A note on curvature and fundamental groups”, J. Differental Geometry, 2 (1968), 1–7 | MR | Zbl

[5] Milnor J., “Growth of finitely generated solvable groups”, J. Differental Geometry, 2:4 (1968), 447–451 | MR

[6] Wolf J., “Growth of finitely generated solvable groups and curvature of Riemannian manifolds”, J. Differental Geometry, 2:4 (1968), 421–446 | MR | Zbl

[7] Gromov M., “Groups of polynomial growth and expanding maps”, Publ. Math. Inst. Hautes Etudes Sci., 53 (1981), 53–73 | DOI | MR

[8] Grigorchuk R. I., “O polugruppakh s sokrascheniyami stepennogo rosta”, Matem. zametki, 43:3 (1988), 305–319 | MR

[9] Grigorchuk R. I., “Stepeni rosta konechno-porozhdennykh grupp i teoriya invariantnykh srednikh”, Izv. AN SSSR. Ser. matem., 48:5 (1984), 939–985 | MR

[10] Grigorchuk R. I., “Stroenie $p$-grupp promezhutochnogo rosta, imeyuschikh kontinuum faktorgrupp”, Algebra i logika, 23:4 (1984), 383–394 | MR | Zbl

[11] Belyaev V. V., Sesekin N. F., Trofimov V. I., “Funktsii rosta polugrupp i lup”, Zapiski Uralskogo gos. un-ta, 10:3 (1977), 3–8 | MR | Zbl

[12] Lavrik-Mannlin A. A., On some semigroups of intermediate growth, Preprint of Department of Mathematics, ETH Zurich, Switserland, 2001

[13] Okninski J., Semigroups of Matrices, World Scientific, Singapore, 1988

[14] Shneerson L. M., “Relatively free semigroups of intermediate growth”, J. Algebra, 235 (2001), 484–546 | DOI | MR | Zbl

[15] Grigorchuk R. I., “Growth and amenability of a semigroup and its group of quotients”, Proceedings of the International Symposium on the Semigroup Theory, Kyoto, 1990, 103–108 | MR | Zbl

[16] Fabrykowski J., Gupta N., “On groups with sub-exponential growth functionsm, II”, J. Indian Math. Soc., 56:1–4 (1991), 217–228 | MR | Zbl

[17] Grigorchuk R. I., Nekrashevich V. V., Suschanskii V. I., “Avtomaty, dinamicheskie sistemy i gruppy”, Tr. MIAN, 231, Nauka, M., 2000, 134–214 | MR

[18] Bartholdi L., Croissance de groupes agissant sur des arbres, Ph. D. Dissertation, Univ. Geneve, Geneve, 2000 | Zbl

[19] Reznikov I. I., Suschanskii V. I., “O funktsiyakh rosta polugrupp, opredelennykh avtomatami Mili s dvumya sostoyaniyami nad dvukhbukvennym alfavitom”, Pratsi Tretïo Mizhnarodnoï Algebraïchnoï konferentsiï v Ukraïni, Sumi, 2001, 238–239

[20] Reznikov I. I., Suschanskii V. I., “Funktsii rosta avtomatov s dvumya sostoyaniyami nad dvukhelementnym alfavitom”, Dopovidi NAN Ukraïni, 2002, no. 1

[21] Reznikov I. I., “Avtomaty Mili s dvumya sostoyaniyami nad dvukhbukvennym alfavitom, kotorye porozhdayut svobodnuyu polugruppu”, Visnik Kiïvskogo universitetu, 2001, no. 3, 91–98 | MR

[22] Hardy G. H., Ramanujan S., “Asymptotic formulae in combinatory analysis”, Proc. London Math. Soc., 17:2 (1918), 75–115 | DOI

[23] Sachkov V. N., Kombinatornye metody diskretnoi matematiki, Nauka, M., 1977

[24] Birkgof G., Barti T., Sovremennaya prikladnaya algebra, Mir, M., 1976

[25] Glushkov V. M., “Abstraktnaya teoriya avtomatov”, UMN, 16:5 (1961), 3–62 | MR