ABSTRACT

In this paper, we have established an intimate connection between near-nings and linear automata, and obtain the following results: 1) For a near-ring N there exists a linear GSA S with iff (a) is abelian, (b) N has an identity 1, (c) There is some such that is generated by {1,d}; 2) Let be a GSAepimorphism. Then there exists a near-ring epimorphism from to with for all and; 3) Let be a GA. Then (a) is accessible, (b) Q = 0N(A), (c) with and is reduced, (d) is minimal.

1. Introduction

Automata consist of inputs, states, and outputs, together with maps which describe how new inputs affect the state and the output. A semi-automation is a triple, where Q and A are sets, called the state set and input set, and F is a function from in Q, called the state-transition function. If Q is a group, we call a group-semiautomaton and abbreviate this by GSA. Automata consist of inputs, states, and outputs, together with maps which describe how new inputs affect the state and the output. A semiautomaton is a triple, where Q and A are sets, called the state set and the input set, and F is a function from in Q, called the state-transition function. If Q is a group (we always write it additively), we call a group-semiautomaton and abbreviate this by GSA. For and we interprete as the new state obtained from the old state q by mean of the input a [1].

If is a semiautomaton, we get a collection of mappings from Q to Q, one for each, which are given by. Hence describes the effect of the input a on the state set Q of.

If the input is followed by the input, the semiautomaton moves from the state first into and then into. We extend (as usual) A to the free monoid over A consisting of all finite sequences of elements of A, including the empty sequence, and get, i.e. the map is a monomorphism from into the transformation monoid over Q with. In the case of, we are also able to study the superposition (defined pointwisely) of two simultaneous inputs. Hence it is natural to consider and all of its sums and products (composition of maps). The obvious framework for that is, of course, the structure of a near ring.

Let be a, The subnear-ring of generated by and all is called the syntactic near-ring of. Thus is always a near-ring with identity. If Q is finite, then is finite, too [2].

2. Discussion

1) The homomorphism case. Let Q and A be additive groups with zero 0 and F a homomorphism from the direct product. We then call a homomorphic. Because of , we get , where is a homomorphism (i.e. a distributive element in N(Q)), while is the map with constant value. If no input can change the zero state, i.e. if for all, then obviously is a distributively generated near-ring, consisting of -sums of powers of which are endomorphisms, we also get a distributively generated near-ring if F is additive in the first component. For homomorphic one sees by induction that , where the map in brackets is constant. Each power is a homomorphism [3].

2) The linear case is a special case of the homomorphism case in which Q and A are Abelian groups (or more generally, R-modules for some ring R) and where F is linear. Let Q and A be free R-modules with finite base X, Y respectively. Let. Then the action of F can be described by an -matrix over R if we replace each element of Q and of A by its decomposition induces a decomposition of Z such that

We then get

. If, in particular, , we get and is a ring, generated by B and the unit matrix I [4]. on the other hand, if, then. We get iff.

Anyhow, each f_a (and hence each f_a for) is an affine map from Q to Q. If Q is free on X with then we can extend the idea of matrix representations from linear maps to affine maps. Let f be an affine map. Then f decomposes as where f₀ is a homomorphism and c is constant. Let F be the matrix for f₀ with respect to X. Invent a symbol e with and for all. Then

Establishes an isomorphism between M_aff(Q) (all affine of Q) and a subnear-ring of all matrices over [3].

3. Main Results

Theorem 1. Let be a homomorphic GSA, Then

Proof. is clear. Conversely it suffices to show that N is a near-ring, since obviously N contains all and. In fact, we show that N is a subnear-ring of M(Q)

Take . It is clear that. So consider

.

Hence we only look at the last expression in (a), let. Then

We first focus our attention to and put for a moment

Therefore we get with

.

By induction, this is in N Let be homomorphic. The zero-symmetric part, and consists of all finite sums of elements of the form with and.

In fact, all elements are in. Conversely, take. Then

. By standard group theory, we can arrange

into sums and differences of elements of the form, where c is the sum of some [5]. If be linear. Then (with)

(n is non negative integer ), Hence is the subnear-ring of generated by. Since is a ring, is a ring, too [6].

We can find a group Q such that N is isomorphic to a subnear-ring of. Let A be an index set for , i.e.. Let. Then with. Since every nearring can be embedded in a near-ring with identity, we get every near-ring can be embedded in the near-ring of some GSA [7]

Theorem 2. For a near-ring N there exists a linear GSA with iff (a) is Abelian, (b) N has an identity 1, (c) There is some such that is generated by.

Proof. Let N be a near-ring with (a)-(c), we know that N is isomorphic to a subnear-ring of [2]. Let and be the images of d and 1 in. Since d is distributive, is an endomorphism of and is generated by id and, whence

(n is non negative integer). Now let and. Then is a linear GSA, Since is abelian. Since we get. Furthermore, take. We get

with

.

This shows. Conversely, every (with constant value c) is in since. Hence.

It is customary in algebraic automata theory to consider the semigroup-epimorphism given by. The idea of simultaneous inputs enables us to transfer this epimorphism from semigroups to nearrings. We can, for instance, interpret as being the complex input “input sequence together with the simultaneous input (in double strength)”. We extend A to the free near-ring A^# over A. If is a word in A^# we define , and. Thus we get an extended simultaneous sequential GSA . Let I be { is the zero map}. Then I is a near-ring ideal and we get by the homomorphism theorem:

If we had used right near-rings, we would have anti-isomorphic to. Hence can be viewed as a homomorphic image of. It is, however, impossible to give a nice canonical form for all elements of.

A possible relief comes from the observation that one might replace by, the free algebra in a variety v of near-rings containing (for instance, one might take v as the variety generated by).

Attention! If A already bears some additive structure, this new addition can (and in most cases will) be different from the given addition in A! In particular, our new addition is one in and not in.

In the linear case we saw that is an affine nearring. Since the class of all affine near-rings is known to form a variety, it makes sense to look at free affine nearrings, the more so since we know how this monsters look like.

Let A be a set, A^* the free monoid over A and the free affine near-ring over A. Then every element of is a finite sum of elements with. In fact. Since and are laws in the variety of affine near-rings, we can bring all expressions into -sums of elements which are products of elements in (observe that we use left near-rings!)

Let be a GSA and the free nearring on A. is accessible from if there is some with. is accessible if each state q is accessible from each other state. is not only a near-ring, but it also operates on Q. obviously Q is an group via in the usual meaning. is accessible from iff. Alternatively, Q can be viewed as an -group via. We have is accessible iff Q is an -group with. In fact, if is accessible then obviously. Conversely, suppose that. If then, and is shown to be accessible.

It might be most useful to examine the relationship between generators, primitivity and accessibility more closely. Now we look at constructions of semiautomata and their corresponding syntactic near-rings.

Let and be GSA with identical input sets. A group homomorphism is called a GSA-homomorphism if holds for all and (with of course).

Theorem 3. Let be a GSA-epimorphism. Then there exists a near-ring epimorphism from to with for all and.

Proof. If, n is a word

in. Then

by induction on the length of w. Define. is well-defined sinceimplies, for all

. Since h is surjective, follows. Obviously, is a near-ring epimorphism and is also true for all and.

An automaton is a quintuple, where is a semiautomaton, B a set (the output set) and a function (called the output function of). If Q is a group, is called a groupautomaton (abbreviated by GA). We call a homomorphic GA if Q, A, B are groups and F, G are homomorphisms. is called a linear GA or linear automaton or linear sequential machine if Q, A, B are R-modules for some ring R and F, G are R-linear maps [1].

In many cases, however, outputs do play an essential role. For instance, if one wants to connect two (or more) automata in series. For doing that, consider and. The

Series connection s

outputs of shall be the inputs of

More formally, s with

and

.

If and are linear GA then is the near-ring additively generated by all pairs of the form (n is non negative integer)the constant-map-pairs and all

(n is non negative integer), with .

Let A^* and B^* denote the free monoids over A and B, respectively. For let be defined by

, ,

and proceed inductively with

.

is called the sequential (input-output-) function of at q. If is a GA, is called the sequential function of A. Furthermore, call equivalent states () if (i.e. if and induce the same input-output-behaviour).

It might make sense to extend from to, where and are the free near-rings [2] in a variety which contains the one generated by if we define

.

If is homomorphic we get for

If then. Let. Then;

and so on, hence, whence.

Similarly, if and then

and induction shows. We there fore get Theorem 4. Let be a homomorphic GA. Then ~ is a congruence relation in the -group Q. and (a) is an ideal of; (b) for all.

We might ask what means in detail Theorem 5. Let be homomorphic and

. Then For any non negative integer k,

Proof. Let. We use induction on k and start with. If then

.

Since we get. Now suppose theorem 5 holds for all words of length. Then for all, , hence, we have,

Similarly,

hence and we get

. The converse is shown similarly.

A GA is reduced if ~ is the equality. If is accessible (i.e. if (Q, A, F)is accessible) and reduced then is called minimal [1]. Obviously, a homomorphic GA is reduced iff, we have Corollary 6. Let be a GA. Then

(a)

is accessible; (b); (c)

with

and is reduced; (d) is minimal.

The proofs are straightforward. In looking for criteria to decide if a given GA is minimal or not, we obviously have to view Q not only as an -group but also have to care about B.

Corollary 7. Let A be a homomorphic GA. Then A is reduced iff has no non-zero ideals with.

Proof. If has no such ideals then and is reduced. So suppose that conversely is reduced and that has for all. If, we see by similar arguments that, hence, whence.

From corollary 7 we get Corollary 8. Let be a homomorphic GA. Then A is minimal iff is generated by 0 and does not contain non-zero ideals which are annihilated by.

REFERENCES