Matrix extension of binary relation semigroup and its application to the theory of words on finite automata and semigroups
by
Vladimir A. Molchanov
Saratov State University, Russia

Using methods of the nonstandard analysis [1], we elaborate a general approach to the theory of words on finite automata and semigroups. This approach makes it possible to transfer basic notions of the standard theory of finite words to arbitrary words (both finite and infinite in any direction) and to generalize well-known results on recognizable sets of finite words [2] to infinite words.

The main results of [3] show that infinite products of elements of a standard sequence in finite semigroups can be viewed as a two-sided algebraic counterpart of finite products of a special kind. Based on these results we obtain a canonical extension of a finite semigroup S to the four-sorted algebra with infinite powers S by adding the infinite components to the semigroup S. These results make it possible to introduce the following notion of a recognizable language on finite semigroups. Let S be a finite semigroup and f a mapping of A to S.. We say that a mapping f recognizes a language L of arbitrary words over a finite alphabet A if there is a (four-sorted) subset P of the four-sorted algebra with infinite powers S such that L is the set of arbitrary words w over a finite alphabet A, for which f(w) belongs to P.

The purpose of this talk is to prove the following modification of the well-known Kleen's theorem states the equivalence between automata, finite semigroups and rational expressions.

General Kleene's theorem. For a language L of arbitrary words over a finite alphabet A the following conditions are equivalent:

1)  L is recognized by a finite semigroup;
2)  L is recognized by a finite ip-semigroup;
3)  L is recognized by a finite semigroup equipped with three associative infinite operations;
4)  L is recognized by a finite Büchi automaton;
5)  L is general rational, i.e. L belongs to the smallest set of languages over alphabet A containing finite languages and closed under three special operations (finite union, ternary product and power). .

REFERENCE

[1] M. H. A. Devis, Applied Nonstandard Analysis , Wiley & Sons. New York, 1977.

[2] J. E. Pin., Finite semigroups and recognizable languages: an introduction , Semigroups, Formal Languages and Groups, NATO ASI Series C: Mathematical and Physical Sciences 466 (1993) 1-32.

[3] V. A. Molchanov , Nonstandard approach to algebraic theory of words on finite automata and semigroups , Summaries of Talks, International Nebraska Conference on Groups and Semigroups ICGS2000, Lincoln, Nebraska, 2000.

Date received: November 3, 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 # cafo-10.