Nonstandard Approach to Algebraic Theory of Words on Finite Automata and Semigroups
by
Vladimir A. Molchanov
Saratov State University, Saratov, Russia

Using methods of the nonstandard analysis [1], we elaborate a general approach to the theory of arbitrary words (both finite and infinite in any direction) and generalize the well-known Kleene's theorem (see, for example, [2]) proving that the class of recognizable languages (i.e. those recognized by either a finite Büshi automaton or a finite semigroup), 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: April 29, 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 # caec-14.