Nonstandard Approach to Generally Rational Languages
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 permits us to transfer basic notions of the standard theory of finite words (see, for example, [2]) on arbitrary words (both finite and infinite in any direction) and to generalize these results on recognizable sets of finite words to infinite words.

In particular, we generalize the well-known Kleene's theorem proving that the class of recognizable languages (i.e. those recognized by a finite Büshi automaton), coincides with the class of generally rational languages (i.e. the smallest set of languages over an alphabet A containing finite languages and closed under three special operations).

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.

Date received: February 28, 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-07.