2-Generated semigroup of automatic transformations whose
growth is defined by Fibonachi series

I. I. Reznykov; V. I. Sushchansky

All non-free semigroups of exponential growth defined by two-state Mealy automata over a two-symbol alphabet are described in terms of generators and defining relations. It was found out, that there are up to isomorphism seven such semigroups. The proofs for these semigroups are substantially similar, therefore we investigate in details one of them, the semigroup $\left\langle {\begin{array}{*{20}c} {f_1 ,f_2 } &| & {{f_2 ^2} \cdot f_1 = f_2 \cdot {f_1 ^2 }} \end{array}} \right\rangle$. It is proved that its growth function is sequences like a Fibonacci series.

1. Алешин С.В. Конечные автоматы и проблема Бернсайда о периодических группах // Математ. заметки. – 1972. – Т.11, № 3. – C.319–328.

2. Сущанский В.И. Периодические $p$-группы перестановок и неограниченная проблема Бернсайда // ДАН СССР. -- 1979. -- Т.247, № 3.\ -- C.557--561.

3. Григорчук Р.И. О проблеме Бернсайда в периодических полугруппах // Функциональный анализ и приложения. – 1980. – Т.14, № 1. – C.53–54.

4. Григорчук Р.И. Степень роста конечно порожденных групп и теория инвариантных значений // Изв. АН СССР, Серия: Математика. – 1984. – Т.48, № 5. – C.939–985.

5. Григорчук Р.И. Строение $p$-групп промежуточного роста, имеющих континуум факторгрупп // Алгебра и логика.\ -- 1984. -- Т.23, № 4.\ -- C.383--394.

6. Grigorchuk R.I. Just Infinite Branch Groups, in New Horizons in Pro-p Groups, du Sautoy, M.P.F., Segal, D., and Shalev, A., Eds. – Boston: Birkhauser, 2000. – P.121–179.

7. Резников И.И. Вільні напівгрупи перетворень, породжені автоматами з двома станами // Вісник Київського ун-ту. – 2001. - № 1–2. – C.41–46.

8. Олийнык А.С. О свободных полугруппах автоматных преобразований // Математ. заметки. – 1998. – Т.63, № 2. – C.248–259.

9. Grigorchuk R., Zuk A. The Lamplighter group as a group generated by a 2-state automaton and its spectrum, Preprint of Forschungsinst. Math, ETH-Zurich, 1999. – 35 pp.

10. Sidki S. Regular Trees and Their Automorphisms. – Rio de Janeiro: IMPA, 1998.

11. Григорчук Р.И., Некрашевич В.В., Сущанский В.И. Автоматы, динамические системы и группы // Труды математического института им. В.А.Стеклова. – 2000. – Т.231. – С.134–214.

12. Резников И.И., Сущанский В.И. О функциях роста полугрупп, определенных автоматами Мили с двумя состояниями над двухбуквенным алфавитом, Праці Третьої Міжнародної Алгебраїчної конференції в України, Суми – 2001. – С.238–239.

13. Уфнаровский В.А. Комбинаторные и асимптотические методы в алгебре. в кн. "Итоги науки и техники. Современные проблемы математики. Фундаментальные направления". – Т.57. – М.: ВИНИТИ. - 1990. – C.5–177.

14. Pierre de la Harpe Topics in Geometric Group Theory, Chicago & London: The University of Chicago Press. – 2000. – 310 pp.

15. Резников І.І. Автомати Мілі с двома станами над двобуквеним алфавітом, які породжують вільну напівгрупу // Вісник Київського Університету. – 2001. – № 3. (в друці)

16. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир, 1976. – 400 с.

17. Ferenc Gecseg, Products of automata. Berlin ets.: Springer-Verlag, 1986. – 107 pp.

18. Глушков В.М. Абстрактная теория автоматов // Успехи математических наук. – 1961. – Т.16, № 5. – C.3–62.

19. 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. – P.103–108.

20. Григорчук Р.И. О полугруппах с сокращениями степенного роста // Математические заметки. – 1988. – Т.43, № 3. – C.305–319.

21. Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969. – 328 с.

	2-Generated semigroup of automatic transformations whose growth is defined by Fibonachi series
Author	I. I. Reznykov, V. I. Sushchansky Kyiv National University, Ukraine, Silesian Technological University, ,Gliwice, Poland
Abstract	All non-free semigroups of exponential growth defined by two-state Mealy automata over a two-symbol alphabet are described in terms of generators and defining relations. It was found out, that there are up to isomorphism seven such semigroups. The proofs for these semigroups are substantially similar, therefore we investigate in details one of them, the semigroup $\left\langle {\begin{array}{*{20}c} {f_1 ,f_2 } &\| & {{f_2 ^2} \cdot f_1 = f_2 \cdot {f_1 ^2 }} \end{array}} \right\rangle$. It is proved that its growth function is sequences like a Fibonacci series.
Keywords	non-free semigroups, exponential growth, two-state Mealy automata, two-symbol alphabet, generators and defining relations, growth function, Fibonacci series
DOI	doi:10.30970/ms.17.1.81-92
Reference	1. Алешин С.В. Конечные автоматы и проблема Бернсайда о периодических группах // Математ. заметки. – 1972. – Т.11, № 3. – C.319–328. 2. Сущанский В.И. Периодические $p$-группы перестановок и неограниченная проблема Бернсайда // ДАН СССР. -- 1979. -- Т.247, № 3.\ -- C.557--561. 3. Григорчук Р.И. О проблеме Бернсайда в периодических полугруппах // Функциональный анализ и приложения. – 1980. – Т.14, № 1. – C.53–54. 4. Григорчук Р.И. Степень роста конечно порожденных групп и теория инвариантных значений // Изв. АН СССР, Серия: Математика. – 1984. – Т.48, № 5. – C.939–985. 5. Григорчук Р.И. Строение $p$-групп промежуточного роста, имеющих континуум факторгрупп // Алгебра и логика.\ -- 1984. -- Т.23, № 4.\ -- C.383--394. 6. Grigorchuk R.I. Just Infinite Branch Groups, in New Horizons in Pro-p Groups, du Sautoy, M.P.F., Segal, D., and Shalev, A., Eds. – Boston: Birkhauser, 2000. – P.121–179. 7. Резников И.И. Вільні напівгрупи перетворень, породжені автоматами з двома станами // Вісник Київського ун-ту. – 2001. - № 1–2. – C.41–46. 8. Олийнык А.С. О свободных полугруппах автоматных преобразований // Математ. заметки. – 1998. – Т.63, № 2. – C.248–259. 9. Grigorchuk R., Zuk A. The Lamplighter group as a group generated by a 2-state automaton and its spectrum, Preprint of Forschungsinst. Math, ETH-Zurich, 1999. – 35 pp. 10. Sidki S. Regular Trees and Their Automorphisms. – Rio de Janeiro: IMPA, 1998. 11. Григорчук Р.И., Некрашевич В.В., Сущанский В.И. Автоматы, динамические системы и группы // Труды математического института им. В.А.Стеклова. – 2000. – Т.231. – С.134–214. 12. Резников И.И., Сущанский В.И. О функциях роста полугрупп, определенных автоматами Мили с двумя состояниями над двухбуквенным алфавитом, Праці Третьої Міжнародної Алгебраїчної конференції в України, Суми – 2001. – С.238–239. 13. Уфнаровский В.А. Комбинаторные и асимптотические методы в алгебре. в кн. "Итоги науки и техники. Современные проблемы математики. Фундаментальные направления". – Т.57. – М.: ВИНИТИ. - 1990. – C.5–177. 14. Pierre de la Harpe Topics in Geometric Group Theory, Chicago & London: The University of Chicago Press. – 2000. – 310 pp. 15. Резников І.І. Автомати Мілі с двома станами над двобуквеним алфавітом, які породжують вільну напівгрупу // Вісник Київського Університету. – 2001. – № 3. (в друці) 16. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир, 1976. – 400 с. 17. Ferenc Gecseg, Products of automata. Berlin ets.: Springer-Verlag, 1986. – 107 pp. 18. Глушков В.М. Абстрактная теория автоматов // Успехи математических наук. – 1961. – Т.16, № 5. – C.3–62. 19. 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. – P.103–108. 20. Григорчук Р.И. О полугруппах с сокращениями степенного роста // Математические заметки. – 1988. – Т.43, № 3. – C.305–319. 21. Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969. – 328 с.
Pages	81-92
Volume	17
Issue	1
Year	2002
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html

2-Generated semigroup of automatic transformations whose growth is defined by Fibonachi series