Semigroups of Automaton Transformations
by
V.I. Sushchansky
Silesian University of Technology, Kyiv National University

Let X be a finite alphabet, X^* be the set of words over the alphabet X. Every initial ( not necessary finite) Mealy's automaton define a transformation on the set X^*. The set SA(X) of all automaton transformations over X form a semigroup under the composition of transformations (see [1]). The semigroup SA(X) may be constructed from the full symmetric semigroup on X by using the operation of the ( infinite iterated ) wreath product ( for definition see [2]). In the talk we study some properties of SA(X):

- the Green's relations;

- standard subsemigroups;

- the conjugacy relation.

We study also the properties of the actions of SA(X) on X^* and on the set of infinite words over alphabet X. We describe the class of all semigroups which has an exact representation by automaton transformations and concrete representations of some well-known semigroups.

[1] F. Geczeg, I.Peak. Algebraic Theory of Automata. Akademiai Kiado, Budapest, 1972

[2] J.D.P. Meldrum. Wreath Products of Groups and Semigroups. Longman, Harlow, 1995

Date received: May 22, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caee-56.