Nonstandard Theory of Many-Sorted Finite Models and its Application to Semigroups and Automata on Infinite Words

Vladimir A. Molchanov

The new approach to pseudovarieties of finite algebraic systems based on the nonstandard analysis methods was elaborated in the paper [1]. The purpose of this talk is to generalize this approach on pseudovarieties of many-sorted finite models and to apply it to the theory of arbitrary words (both finite and infinite in any direction) on finite automata and semigroups. This includes (i) the introduction of the nonstandard lower predicate language with many-sorted variables and its interpretation in finite many-sorted algebraic systems; (ii) the characterization of such pseudovarieties as equational classes defined by identities of this language and (iii) the investigation of the interplay between nonstandard varieties of four-sorted semigroup algebras and varieties of generally regular languages of arbitrary words on semigroups and automata.

By a four-sorted semigroup algebra (shortly 4-semigroup) we mean a four-sorted algebra S = (S, S^{→}, S^{←}, S^{↔}) equipped with six operations: an associative product on S, mixed products S×S^{→} → S^{→}, S^{←}×S → S^{←}, S^{←} × S^{→} → S^{↔} and maps S → S^{→}, S → S^{←} (denoted s ↦ s^{+ω}, s ↦ s^{−ω}), satisfying, for every s, t ∈ S, x ∈ S^{←}, y ∈ S^{→} and n ∈ N, the equations x(st) = (xs)t, (st)y = s(ty), (xs)y = x(sy), s(ts)^{+ω} = (st)^{+ω}, (ts)^{−ω}t = (st)^{−ω}, (s^{n})^{+ω} = s^{+ω}, (s^{n})^{−ω} = s^{−ω}.

An important example of 4-semigroup gives us the algebraic system W = (W_{fin}(A), A^{N}, A^{−N}, A^{Z}) equipped with the usual concatenation product, where W_{fin}(A) is the semigroup of finite words over a finite alphabet A, Z is the set of integers, N and −N are the sets of positive and negative integers, respectively.

Using methods of the nonstandard analysis, we elaborate a general approach to the theory of arbitrary words and generalize the well-known Kleene’s theorem proving that the class of recognizable languages (i.e. those recognized by either a finite Büshi automaton, or a finite semigroup, or a finite 4-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).

[1] V. A. Molchanov, Nonstandard characterization of pseudovarieties, Algebra Universalis, 1995, V. 33. P. 533–547.

Address: Department of Mathematics and Physics, Pedagogical Institute of Saratov State University, Michurina 92, Saratov 410028, Russia

E-mail: souslin@sgu.ssu.runnet.ru