On Nonstandard Varieties and Lattice of Pseudovarieties of Finite Algebraic Automata
by
Tatyana M. Otryvankina
Saratov State University, Russia

In this note we investigate the lattice of all pseudovarieties of finite algebraic automata with the help of nonstandard analysis methods elaborated in the papers [1, 2]. We assume that basic sets of any considered mathematical structure belong to the standard set-theoretical universe U.

We fix an algebraic type \Omega, consisting of finitary operations. By a finite algebraic automaton (FAA for short) we mean a two-sorted algebra A=(\Gamma, S, o ), where \Gamma is a some fixed finite semigroup of input signals, S is a finite \Omega-algebra of automaton states and a binary operation o : S×\Gamma --> S satisfies the following conditions:

1) f_S(s₁, ..., s_n) o \gamma = f_S(s₁ o \gamma, ..., s_n o \gamma),  2) s o \gamma₁\gamma₂=(s o \gamma₁) o \gamma₂, where f in \Omega,  s, s₁, ..., s_n  in  S,  \gamma, \gamma₁, \gamma₂ in \Gamma.

By analogy with [1] to describe properties of FAA we use a nonstandard formal language L over set Z. Nonstandard terms of the language L are elements of nonstandard extension ^*W, where W=W_\Omega'(Z) is the \Omega'-algebra of \Omega'-words over Z for the type \Omega'=\Omega \cup \Gamma. Formulas of L are defined on induction by usual way. An interpretation of L in FAA A=(\Gamma, S, o ) is defined with the help of mapping \theta: Z --> S which is canonically extended to the homomorphism ^*\theta: ^*W --> S.

A class of FAA K is said to be a nonstandard variety, if it is axiomatizable by a class of nonstandard identities. A structural characterization of nonstandard varieties of finite algebraic automata are described in the following modification of Birkhoff theorem.

Theorem 1. A class of finite algebraic automata K is a nonstandard variety if and only if it is closed under the formation of subsystems, homomorphic images and finite direct products, i.e. K is a pseudovariety.

Using this result we investigate the lattice L of all pseudovarieties of finite algebraic automata.

By analogy with [2] an equivalence \epsilon on ^*W is called invariant nonstandard congruence if (i) for any x, y in ^*W, the condition x \not \equiv y (\epsilon) implies that there is L subset A satisfying \epsilon(^*L) subset ^*L and x in ^*L, y \not in ^*L, (ii) it is preserved under actions of all internal translations and standard endomorphisms of the ^*W, (iii) the equivalence \epsilon has hyperfinite index.

Denote the set of all invariant nonstandard congruences on ^*W by INCon ^*W.

Theorem 2. The sets L and INCon^*W are dually isomorphic complete lattices.

References

[1]  Molchanov V.A., Nonstandard characterization of pseudovarieties // Algebra Universalis, 33 (1995) 533-547.

[2]  Molchanov V.A., Nonstandard congruences and lattices of pseudovarieties , Semigroups, automata and languages. (J. Almeida, Ed.) Wold Scientific, Singapore-New Jersey-London, 1996. P. 183-193.

Date received: May 12, 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-25.