Composite and non-monotonic growth functions of Mealy automata

I.I.Reznykov

We introduce the notion of composite growth function and provide examples that illustrate fundamental properties of these growth functions. We provide examples of Mealy automata that have composite non-monotonic growth functions of the polynomial growth order. We described examples of Mealy automata that have composite monotonic growth functions of intermediate and exponential growth. Questions concerning the relationship between the notions ``composite'' and ``non-monotonic'' of a Mealy automaton growth function are formulated.

1. Andrews G.E. The Theory of Partitions, London, Amsterdam, Don Mills Ontario, Sydney, Tokio, Addison-Wesley Publishing Company, 1976, 255~pp.

2. Бабенко И.К. Проблемы роста и рациональности в алгебре и топологии, Успехи мат. наук, 41 (1986), no.2, 95--142.

3. Gecseg F. Products of automata, Berlin etc., Springer-Verlag, 1986, 107 pp.

4. Gill A. Introduction to the Theory of Finite-State Machines, New York, San Francisco, Toronto, London, McGraw-Hill Book Company, Inc., 1963, 272 pp.

5. Глушков~В.М. Абстрактная теория автоматов, Успехи мат. наук, 16 (1961), no.5, 3--62.

6. Григорчук ~Р.И. О полугруппах с сокращениями степенного роста, Матем. заметки, 43 (1988), no.3, 305--319.

7. Григорчук ~Р.И., Некрашевич~В.В., Сущанский~В.И. Автоматы, динамические системы и группы, Труды математического института им. В.А.Стеклова 231 (2000), 128--203,

8. Lallement G. Semigroups and combinatorial applications, New York, Chichester, Brisbane, Toronto, John Willey \& Sons, 1979, 400 pp.

9. Mealy G.H. A method for synthesizing sequential circuits, Bell System Tech. J. 34 (1955), 1045--1079,

10. Milnor J. Growth of finitely generated solvable groups, J. of Diff. Geom. 2 (1968), no.4, 447--451,

11. Резников І.І. Функції росту автоматів Мілі з двома станами над двоелементним алфавітом та напівгрупи, що ними породжуються, Київський Національний Університет ім. Т. Шевченка, Київ 2002, 135 c.

12. Reznykov I.I. On $2$-state Mealy automata of polynomial growth, Algebra and Discrete Mathematics (2003), no.4, 66--85,

13. Reznykov I.I., Sushchansky V.I. $2$-generated semigroup of automatic transformations, whose growth is defined by Fibonacci series, Mat. Studii, 17 (2002), no.1, 81--92.

14. Шварц ~А.С. Объемные инварианты покрытий, ДАН СССР, 105, 32--34.

15. Уфнаровский~В.А. Комбинаторные и асимптотические методы в алгебре, Итоги науки и техники, Т.57, 1990, с. 5--177,

	Composite and non-monotonic growth functions of Mealy automata
Author	I.I.Reznykov Illya.Reznykov@ikc5.com.ua 5, Krasnogvardeyskaya st., of. 2,02094, Kyiv, Ukraine
Abstract	We introduce the notion of composite growth function and provide examples that illustrate fundamental properties of these growth functions. We provide examples of Mealy automata that have composite non-monotonic growth functions of the polynomial growth order. We described examples of Mealy automata that have composite monotonic growth functions of intermediate and exponential growth. Questions concerning the relationship between the notions ``composite'' and ``non-monotonic'' of a Mealy automaton growth function are formulated.
Keywords	composite growth function, Mealy automata, polynomial growth
DOI	doi:10.30970/ms.22.2.202-214
Reference	1. Andrews G.E. The Theory of Partitions, London, Amsterdam, Don Mills Ontario, Sydney, Tokio, Addison-Wesley Publishing Company, 1976, 255~pp. 2. Бабенко И.К. Проблемы роста и рациональности в алгебре и топологии, Успехи мат. наук, 41 (1986), no.2, 95--142. 3. Gecseg F. Products of automata, Berlin etc., Springer-Verlag, 1986, 107 pp. 4. Gill A. Introduction to the Theory of Finite-State Machines, New York, San Francisco, Toronto, London, McGraw-Hill Book Company, Inc., 1963, 272 pp. 5. Глушков~В.М. Абстрактная теория автоматов, Успехи мат. наук, 16 (1961), no.5, 3--62. 6. Григорчук ~Р.И. О полугруппах с сокращениями степенного роста, Матем. заметки, 43 (1988), no.3, 305--319. 7. Григорчук ~Р.И., Некрашевич~В.В., Сущанский~В.И. Автоматы, динамические системы и группы, Труды математического института им. В.А.Стеклова 231 (2000), 128--203, 8. Lallement G. Semigroups and combinatorial applications, New York, Chichester, Brisbane, Toronto, John Willey \& Sons, 1979, 400 pp. 9. Mealy G.H. A method for synthesizing sequential circuits, Bell System Tech. J. 34 (1955), 1045--1079, 10. Milnor J. Growth of finitely generated solvable groups, J. of Diff. Geom. 2 (1968), no.4, 447--451, 11. Резников І.І. Функції росту автоматів Мілі з двома станами над двоелементним алфавітом та напівгрупи, що ними породжуються, Київський Національний Університет ім. Т. Шевченка, Київ 2002, 135 c. 12. Reznykov I.I. On $2$-state Mealy automata of polynomial growth, Algebra and Discrete Mathematics (2003), no.4, 66--85, 13. Reznykov I.I., Sushchansky V.I. $2$-generated semigroup of automatic transformations, whose growth is defined by Fibonacci series, Mat. Studii, 17 (2002), no.1, 81--92. 14. Шварц ~А.С. Объемные инварианты покрытий, ДАН СССР, 105, 32--34. 15. Уфнаровский~В.А. Комбинаторные и асимптотические методы в алгебре, Итоги науки и техники, Т.57, 1990, с. 5--177,
Pages	202-214
Volume	22
Issue	2
Year	2004
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html