Inverse Semigroups Generated by Two-State Mealy Partial Automata Over Two-Element Alphabet
by
V. I. Sushchansky
Institute of Mathematics Silesian Univesity, Gliwice, Poland
Coauthors: J.K. Slupik

We use definition from [1].

Let A = <X, Q, f , g > be a Mealy partial automaton over finite alphabet X, i.e. the transition function f :Q×X --> X and the output function g :Q×X --> X are partially defined. We call that A is invertible if g (·, q):X --> X is partial permutation over X for all q in Q. Every (partially defined) automaton A for any state q in Q definess the transformation

FA , q:X* --> X*

over the set X^* of all words in alphabet X, which is defined by recurrent rule

FA , q(e)=e ,

FA , q(ux)=FA , f (q, u)·g(q, x) .

The transformation F_{A , q} is partial bijection if only if A is invertible.

Semigroup S(A) generated by F_{A, q}, for q in Q is an inverse semigroup if only if A is invertible.

The main result of the talk is following:

1) Every inverse semigroup defined by invertible two-state automaton over two-symbol alphabet is finite.

2)There exist at least 36 pairwise nonisomorphic inverse semigroups defined by invertible two-state automata over two-symbol alphabet.

[1] R.I.Grigorchuk, V.V.Nekrashevich, V.I.Sushchansky : Automata, Dynamical Systems, and Groups, Trudy Matematicheskogo Instituta imeni V.A. Steklova, Vol. 231, 2000, pp. 134-214,

Date received: March 17, 2004