On transition functions of Mealy automata of finite growth

A.S.Antonenko

The transition functions of Mealy automata that generate finite automaton transformation semigroups are considered in the paper. We formulate conditions on transition functions such that any Mealy automaton with this transition generates a finite semigroup. Also we prove that these requirements are ``maximal'', because for any transition function that does not satisfies them there exists an output function such that the Mealy automaton defines an infinite semigroup.

1. Horejs J. Преобразования, определенные конечными автоматами // Пробл. Кибернетики. -- 1963. -- № 9. -- С. 23--26.

2. Чакань Б., Гечег Ф. О группе автоматных подстановок // Кибернетика. -- 1965. -- № 5. -- С. 14--17.

3. Gecseg F., Peak I., Algebraic theory of automata, Budapest:Academiai kiado, 1972.

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

5. Олийнык А.С., Резников И.И., Сущанский В.И. Полугруппы преобразований, задаваемых автоматами Мили над конечным алфавитом // Алгебраїчні структури та їх застосування: Праці Українського математичного конгресу -- 2001. -- Київ: Ін-т математики НАН України, 2002. -- С. 80--99.

6. Резников І.І. Автомати Мілі з двома над двоелементним алфавітом, які породжують скінченні напівгрупи перетворень // Вісн. Київ Універ. Сер. фіз.-мат. наук. -- 2001. -- № 4. -- С.78--86.

7. Резников~И.И., Сущанский~В.И. Функции роста автоматов с двумя состояниями над двухэлементным алфавитом // Доповіді НАН України -- 2002. -- № 2. -- С.76--81.

8. A.S. Antonenko, E.L. Berkovich, On some algebraic properties of Mealy automata, Kalmar Workshop on Logic and Computer Science, Szeged, 2003, P. 59--68.

9. Руссєв А.В. Про скінченні та абелеві групи, породжені скінченними автоматами // Математичні Студії. -- 2005. -- Т.24, № 2. -- C. 139--146.

10. George~H.~Mealy, A method for synthesizing sequential circuits// Bell System Tech. J. -- 1955. -- T.34. -- 1045--1079

11. Глушков В.М. Абстрактная теория автоматов // Успехи матем. наук. -- 1961. -- T.16, № 5. -- С. 3--62.

12. Ferenc Gécseg, Products of automata, EATCS Monographs on Theoretical Computer Science, 7, Springer-Verlag, Berlin, 1986, viii+107 p.

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

14. C.K.Gupta, V.I. Sushchansky, Semigroups of Automatic Transformations, Quaderni di Matematica, Volume 8, 2000.

15. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997.

	On transition functions of Mealy automata of finite growth
Author	A.S.Antonenko aantonenko@mail.ru Department of Computer Algebra and Discrete Mathematics, Institute of Mathematics, Economics and Mechanics, Odessa I.I. Mechnikov National University,Dvoryanskaya st.,2,65026 Odessa, Ukraine
Abstract	The transition functions of Mealy automata that generate finite automaton transformation semigroups are considered in the paper. We formulate conditions on transition functions such that any Mealy automaton with this transition generates a finite semigroup. Also we prove that these requirements are ``maximal'', because for any transition function that does not satisfies them there exists an output function such that the Mealy automaton defines an infinite semigroup.
Keywords	transition function, Mealy automata, finite growth
DOI	doi:10.30970/ms.29.1.3-17
Reference	1. Horejs J. Преобразования, определенные конечными автоматами // Пробл. Кибернетики. -- 1963. -- № 9. -- С. 23--26. 2. Чакань Б., Гечег Ф. О группе автоматных подстановок // Кибернетика. -- 1965. -- № 5. -- С. 14--17. 3. Gecseg F., Peak I., Algebraic theory of automata, Budapest:Academiai kiado, 1972. 4. Григорчук Р.И., Некрашевич В.В., Сущанский В.И. Автоматы, динамические системы и группы // Тр. Математ. ин-та им. В.А.Стеклова. -- 2000. -- Т.231. -- С. 134--214. 5. Олийнык А.С., Резников И.И., Сущанский В.И. Полугруппы преобразований, задаваемых автоматами Мили над конечным алфавитом // Алгебраїчні структури та їх застосування: Праці Українського математичного конгресу -- 2001. -- Київ: Ін-т математики НАН України, 2002. -- С. 80--99. 6. Резников І.І. Автомати Мілі з двома над двоелементним алфавітом, які породжують скінченні напівгрупи перетворень // Вісн. Київ Універ. Сер. фіз.-мат. наук. -- 2001. -- № 4. -- С.78--86. 7. Резников~И.И., Сущанский~В.И. Функции роста автоматов с двумя состояниями над двухэлементным алфавитом // Доповіді НАН України -- 2002. -- № 2. -- С.76--81. 8. A.S. Antonenko, E.L. Berkovich, On some algebraic properties of Mealy automata, Kalmar Workshop on Logic and Computer Science, Szeged, 2003, P. 59--68. 9. Руссєв А.В. Про скінченні та абелеві групи, породжені скінченними автоматами // Математичні Студії. -- 2005. -- Т.24, № 2. -- C. 139--146. 10. George~H.~Mealy, A method for synthesizing sequential circuits// Bell System Tech. J. -- 1955. -- T.34. -- 1045--1079 11. Глушков В.М. Абстрактная теория автоматов // Успехи матем. наук. -- 1961. -- T.16, № 5. -- С. 3--62. 12. Ferenc Gécseg, Products of automata, EATCS Monographs on Theoretical Computer Science, 7, Springer-Verlag, Berlin, 1986, viii+107 p. 13. Григорчук Р.И. О полугруппах с сокращениями степенного роста // Матем. зам. -- 1988. -- T.43, № 3. -- С. 305--319. 14. C.K.Gupta, V.I. Sushchansky, Semigroups of Automatic Transformations, Quaderni di Matematica, Volume 8, 2000. 15. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997.
Pages	3-17
Volume	29
Issue	1
Year	2008
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html