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
![](https://www.scirp.org/html/6-7401083\e4d22c00-c657-4c7e-ba94-14edb8353a88.jpg)
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 fa (and hence each fa 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 f0 is a homomorphism and c is constant. Let F be the matrix for f0 with respect to X. Invent a symbol e with
and
for all
. Then
![](https://www.scirp.org/html/6-7401083\da65ac6a-a229-4513-96d2-b850390e8be3.jpg)
Establishes an isomorphism between Maff(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 ![](https://www.scirp.org/html/6-7401083\a5418641-5265-4b32-b362-ca3e0591338e.jpg)
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
![](https://www.scirp.org/html/6-7401083\b29303a6-551f-460c-b6d2-ec76610ca58f.jpg)
We first focus our attention to
and put
for a moment
![](https://www.scirp.org/html/6-7401083\cab42926-b3ac-4d43-a83d-5437e791fdf0.jpg)
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: ![](https://www.scirp.org/html/6-7401083\24898e40-193e-4c71-b447-1b4e8798c2ed.jpg)
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 since
implies
, 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
![](https://www.scirp.org/html/6-7401083\d8b5c351-b110-4fa4-9deb-46d0e76ab210.jpg)
Series connection
s![](https://www.scirp.org/html/6-7401083\ff7ff4b6-439a-4f2e-9e95-856ef3ecc014.jpg)
outputs of
shall be the inputs of ![](https://www.scirp.org/html/6-7401083\6e15e9f0-0441-4f46-9154-50538d5aae2b.jpg)
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
,
,
![](https://www.scirp.org/html/6-7401083\652c7cd1-ed80-4787-8534-2e5d64712a2a.jpg)
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 ![](https://www.scirp.org/html/6-7401083\398271a0-9958-4b00-a519-e2de064441ae.jpg)
If
then
. Let
. Then
;
![](https://www.scirp.org/html/6-7401083\a0188ef2-dd1b-4c69-80db-e8090ed7ca6b.jpg)
and so on, hence
, whence
.
Similarly, if
and
then
![](https://www.scirp.org/html/6-7401083\b5517919-8ed2-4f4a-8cf4-9e1aad06a16f.jpg)
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, ![](https://www.scirp.org/html/6-7401083\23e8c99e-f144-43e7-b994-a5470f1ad3fe.jpg)
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,
![](https://www.scirp.org/html/6-7401083\c08086c9-1afa-4260-bc85-9074acdeb75c.jpg)
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) ![](https://www.scirp.org/html/6-7401083\0153999e-ed91-46d6-8438-dc4a2a066ffe.jpg)
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
.