Symmetries of automata
For a given reachable automaton A, we prove that the (state-) endomorphism monoid End(A) divides its characteristic monoid M(A). Hence so does its (state-)automorphism group Aut(A), and, for finite A, Aut(A) is a homomorphic image of a subgroup of the characteristic monoid. It follows that in the pr...
Збережено в:
| Дата: | 2015 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2015
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/152786 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Symmetries of automata / A. Egri-Nagy, C.L. Nehaniv // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 48-57. — Бібліогр.: 7 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-152786 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1527862019-06-13T01:25:39Z Symmetries of automata Egri-Nagy, A. Nehaniv, C.L. For a given reachable automaton A, we prove that the (state-) endomorphism monoid End(A) divides its characteristic monoid M(A). Hence so does its (state-)automorphism group Aut(A), and, for finite A, Aut(A) is a homomorphic image of a subgroup of the characteristic monoid. It follows that in the presence of a (state-) automorphism group G of A, a finite automaton A (and its transformation monoid) always has a decomposition as a divisor of the wreath product of two transformation semigroups whose semigroups are divisors of M(A), namely the symmetry group G and the quotient of M(A) induced by the action of G. Moreover, this division is an embedding if M(A) is transitive on states of A. For more general automorphisms, which may be non-trivial on input letters, counterexamples show that they need not be induced by any corresponding characteristic monoid element. 2015 Article Symmetries of automata / A. Egri-Nagy, C.L. Nehaniv // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 48-57. — Бібліогр.: 7 назв. — англ. 1726-3255 2010 MSC:20B25, 20E22, 20M20, 20M35, 68Q70. http://dspace.nbuv.gov.ua/handle/123456789/152786 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
For a given reachable automaton A, we prove that the (state-) endomorphism monoid End(A) divides its characteristic monoid M(A). Hence so does its (state-)automorphism group Aut(A), and, for finite A, Aut(A) is a homomorphic image of a subgroup of the characteristic monoid. It follows that in the presence of a (state-) automorphism group G of A, a finite automaton A (and its transformation monoid) always has a decomposition as a divisor of the wreath product of two transformation semigroups whose semigroups are divisors of M(A), namely the symmetry group G and the quotient of M(A) induced by the action of G. Moreover, this division is an embedding if M(A) is transitive on states of A. For more general automorphisms, which may be non-trivial on input letters, counterexamples show that they need not be induced by any corresponding characteristic monoid element. |
| format |
Article |
| author |
Egri-Nagy, A. Nehaniv, C.L. |
| spellingShingle |
Egri-Nagy, A. Nehaniv, C.L. Symmetries of automata Algebra and Discrete Mathematics |
| author_facet |
Egri-Nagy, A. Nehaniv, C.L. |
| author_sort |
Egri-Nagy, A. |
| title |
Symmetries of automata |
| title_short |
Symmetries of automata |
| title_full |
Symmetries of automata |
| title_fullStr |
Symmetries of automata |
| title_full_unstemmed |
Symmetries of automata |
| title_sort |
symmetries of automata |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2015 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/152786 |
| citation_txt |
Symmetries of automata / A. Egri-Nagy, C.L. Nehaniv // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 48-57. — Бібліогр.: 7 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT egrinagya symmetriesofautomata AT nehanivcl symmetriesofautomata |
| first_indexed |
2025-07-14T04:16:51Z |
| last_indexed |
2025-07-14T04:16:51Z |
| _version_ |
1837594430775754752 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 19 (2015). Number 1, pp. 48–57
© Journal “Algebra and Discrete Mathematics”
Symmetries of automata1
Attila Egri-Nagy and Chrystopher L. Nehaniv
Communicated by V. I. Sushchansky
Abstract. For a given reachable automaton A, we prove
that the (state-) endomorphism monoid End(A) divides its char-
acteristic monoid M(A). Hence so does its (state-)automorphism
group Aut(A), and, for finite A, Aut(A) is a homomorphic image of
a subgroup of the characteristic monoid. It follows that in the pres-
ence of a (state-) automorphism group G of A, a finite automaton
A (and its transformation monoid) always has a decomposition as
a divisor of the wreath product of two transformation semigroups
whose semigroups are divisors of M(A), namely the symmetry group
G and the quotient of M(A) induced by the action of G. Moreover,
this division is an embedding if M(A) is transitive on states of A.
For more general automorphisms, which may be non-trivial on input
letters, counterexamples show that they need not be induced by any
corresponding characteristic monoid element.
1. Preliminaries
An automaton is a 3-tuple A = (X, Σ, δ : X × Σ → X), with state set
X, input alphabet Σ, and state-transition function δ, which given a state
and input letter returns the next state. This action on X by symbols Σ
naturally extends to words, i.e. sequences of symbols, by applying the
symbols sequentially from left to right. An automaton is said to be finite
if its state and input set are finite. Write x · a for δ(x, a) for x ∈ X, a ∈ Σ,
and extend this inductively to words w ∈ Σ∗ by x · aw = (x · a) · w, where
1This work was in part supported by the EU FP6 Project OPAALS (Contract No
IST-034824) and the FP7 EU Project BIOMICS (contract number CNECT-318202).
This support is gratefully acknowledged.
2010 MSC: 20B25, 20E22, 20M20, 20M35, 68Q70.
A. Egri-Nagy, Ch. L. Nehaniv 49
the empty word acts as the identity. (NB: Σ∗ is the free monoid on the
alphabet Σ, consisting of finite words over Σ under concatenation, while
Σ+ is the free semigroup consisting of non-empty words.) The transition
monoid (or characteristic monoid) of A is M(A) = Σ∗/≡, where w ≡ w′
if x · w = x · w′ for all x ∈ X, w, w′ ∈ Σ∗. A state y is reachable (or
accessible) from a state x if there exists a word w ∈ Σ∗ such that x ·w = y.
We say A is generated by a state x0 if each state of A can be reached
from x0. We then say x0 is an ‘initial state’ from which all other states
are reachable. We sometimes then say that (all of) A is ‘reachable’ from
x0. If each state of A has this property, the automaton is said to be
strongly connected. In this paper, we shall henceforth restrict attention to
automata all of whose states are reachable from some initial state.
Let A = (X, Σ, δ) and B = (Y, Σ′, δ′) be automata with characteristic
monoids M and M ′. A pair of functions (π, θ) with π : X → Y and
θ : Σ → Σ′ is a homomorphism of automata if π(x · s) = π(x) · θ(s) holds
for all x ∈ X and s ∈ Σ. It is an endomorphism of A if it maps A to
itself, i.e. B = A. If π and θ are bijective, then it is an isomorphism. An
endomorphism which is also an isomorphism is called an automorphism.
A morphism of automata is called a state-morphism (state-endomorphism,
state-automorphism, etc.) if Σ = Σ′ and θ is the identity function; that
is, all input letters are fixed under the morphism. Let End∗(A) denote
the monoid of endomorphisms of A. Let Aut∗(A) denote the group of
automorphisms of A. Let End(A) and Aut(A) be their submonoid and
subgroup, respectively, consisting just of state-morphisms.
A transformation semigroup (X, S) is a set X and subsemigroup S of
the semigroup XX of all functions from X under function composition
as the associative operation. If S consists of permutations of X, then
(X, S) is a permutation group. If s ∈ S and x ∈ X, we write x · s for
s(x). The permutation group (G, G) is the right regular representation
of G, where G acts on itself by right multiplication. For any automaton
A = (X, Σ, δ) with have its associated transformation semigroup (X, S(A))
with x · [w] = x · w for all x ∈ X and [w] ∈ S(A) = Σ+/ ≡, and its
associated transformation monoid (X, M(A)) with M(A) = Σ∗/≡, which
includes the identity mapping on X. Note that we can always regard a
transformation semigroup or monoid (X, S) as an automaton with input
letters S and transition function δ(x, s) = s(x).
The wreath product (X, S) ≀ (Y, T ) of transformation semigroups is the
transformation semigroup (X × Y, W ) where
W = {(s, f) : s ∈ S, f ∈ T X},
50 Symmetries of automata
whose elements map X × Y to itself as follows
(x, y) · (s, f) = (x · s, y · f(x))
for x ∈ X, y ∈ Y . Here T X is the semigroup of all functions f from X
to T (under pointwise multiplication), and we have write y · f(x) for the
element f(x) ∈ T applied to y ∈ Y . The wreath product of permutation
groups is again a permutation group. The wreath product construction is
associative on the class of transformation semigroups (up to isomorphism).
A morphism of transformation semigroups is defined in the obvious way.
One transformation semigroup divides another, (X, S) � (Y, T ), if (X, S)
is a homomorphic image of a substructure of (Y, T ): precisely, there
exists a subset Z ⊆ Y and a subsemigroup U 6 T , with a surjective
function θ1 : Z ։ Y and surjective homomorphism θ2 : U ։ S such that
θ1(z ·u) = θ1(z) ·θ2(u) for all z ∈ Z and u ∈ U . (NB: U is a subsemigroup
of Y Y , but not necessarily of ZZ , as distinct elements of U might map Z
to itself in the same way.) We write (X, S) 6 (Y, T ) and call the division
and embedding if θ1 and θ2 are injective. Similarly for semigroups, we
write S 6 T if S embeds in T . We write S � T and say S divides T , if S
is a homomorphic image of some subsemigroup U of T , i.e., S և U 6 T .
For more details on the basics of transformation semigroups and algebraic
automata theory, see e.g. [KRT68,Eil76,DN05,Rho10].
2. State-homomorphisms of reachable automata
From now on we consider only state-homomorphisms and reachable
automata unless otherwise stated . We show that a morphism is completely
determined by how it acts at an initial state.
Lemma 1. Let π : A → B be a morphism of automata and suppose A is
reachable from some state x0. Then π agrees with another such morphism
π′ at x0 if and only if π = π′.
Proof. Let x be any state of A. Then x = x0 · s for some s ∈ M(A),
whence
π(x) = π(x0 · s) = π(x0) · s = π′(x0) · s = π′(x0 · s) = π′(x).
Corollary 2. There can be at most |Y | distinct automata morphisms
from A = (X, Σ, δ) to B = (Y, Σ′, δ′).
A. Egri-Nagy, Ch. L. Nehaniv 51
These results can be used to construct efficient algorithms for calculat-
ing all morphisms, further improving backtrack based search techniques
for transformation semigroups [ABMN10].
Proposition 3. The (state-)endomorphism monoid End(A) of an au-
tomaton A is a homomorphic image of a certain submonoid J of the
characteristic monoid of A: M(A) > J
α
։ End(A).
Proof. First define a certain submonoid of M = M(A) consisting of all
elements of M that act like some endomorphism of A at the generating
state x0:
J = {s ∈ M : x0 · s = π(x0) for some π ∈ End(A)}.
We call J the Fleck submonoid of the characteristic monoid M(A). To
see that this is really a submonoid, observe (1) that corresponding to
identity endomorphism the identity element of M(A) is in J , and (2) J is
closed under multiplication: Take s1, s2 ∈ J . By definition, for i ∈ {1, 2},
we have some πi ∈ End(A) such that x0 · si = πi(x0). Now
x0 · s1s2 = (x0 · s1) · s2
= π1(x0) · s2 by choice of π1
= π1(x0 · s2) since π1 is an endomorphism
= π1(π2(x0)) by choice of π2
Therefore, since π1π2 ∈ End(A), we have that s1s2 ∈ J . Note: the action
of the characteristic monoid is on the right of states, while the action of
endomorphisms or automorphisms is on the left of states.
Now define α : J → End(A) by α(s) = π where x0 · s = π(x0),
with π ∈ End(A). (NB: π exists by definition of J .) The function α is
well-defined by Lemma 1.
Moreover, the above calculation shows that α(s1) = π1 and α(s2) = π2
implies that α(s1s2) = π1π2. So since α(1M(A)) = the identity morphism,
α is a monoid homomorphism.
Finally, given π ∈ End(A) consider the state π(x0). By reachability,
there is some s ∈ S with x0 · s = π(x0), whence s ∈ J and α(s) = π. This
proves α is surjective.
Proposition 4. The (state-)automorphism group Aut(A) of an automa-
ton A is a divisor of M(A), a homomorphic image of a submonoid of the
characteristic monoid of M(A).
52 Symmetries of automata
Proof. The proof of this is exactly like that of Proposition 3 except that one
replaces End(A) by Aut(A) the word ‘endomorphism’ by ‘automorphism’
throughout. Alternatively, this is immediate from the proposition since
Aut(A) is the group of units of End(A).
The following lemma is well-known (e.g. Proposition 1.11. in [DN05]).
Lemma 5. Let S be a finite semigroup.
1) If S maps homomorphically onto a group G, then there is a subgroup
G̃ of S mapping onto G.
2) If a group G divides S, then G divides a subgroup of S.
Proof. Suppose ϕ : S ։ G. Then the collection of subsemigroups of S
mapping onto G under ϕ is obviously non-empty. Let G̃ be a member
of this collection minimal under inclusion. (It must exist by finiteness.)
Then G̃G̃ is a subsemigroup with the same property and is contained in G̃.
Whence, by minimality, G̃2 = G̃. By finiteness, G̃ contains an idempotent
e2 = e since any finite semigroup does. By minimality eG̃e = G̃, and e is
thus a left- and right-identity for all elements of G̃, thus G̃ is a monoid.
To show that inverses exist take t ∈ eG̃e, and e′ be the unique idempotent
power of t (which exists again by finiteness). Then with same reasoning
eG̃e = e′G̃e′, for which both e′ and e are clearly left- and right- identity
elements, and so e = ee′ = e′, therefore e = e′. Thus for each t there exists
n > 1 such that tn = e, so ttn−1 = tn−1t = e. So G̃ is a group mapping
homorphically onto G. The second assertion is a trivial consequence of
the first.
Corollary 6. The (state-)automorphism group Aut(A) of a finite au-
tomaton A is a homomorphic image of a subgroup of its characteristic
monoid M(A).
Proof. This follows from the Proposition 4 by Lemma 5 and finiteness of
M(A).
Remark. Propositions 3 and 4 and Corollary 6 are due to the sec-
ond named author based on streamlining and generalizing the methods
of [Fle65].
Corollary 6 is the generalization of the result of Fleck [Fle65, The-
orem 2.4] from strongly connected automata to those each of whose
states are accessible from some initial state. That the result for reachable
automata is not a vacuous generalization can be clearly seen by many
examples of non-trivial state-automorphisms of automata which are not
strongly connected.
A. Egri-Nagy, Ch. L. Nehaniv 53
Examples 7. Reachable automata A1, A2, and A3 with state set X =
{1, 2, 3, 4}, input symbols Σ = {a, b}, and initial state 1: Each auto-
morphism group Aut(Ai) ∼= Z2 for 1 6 i 6 3, and it is also true that
Z2 6 M(Ai), as a is a transposition. These automata are not strongly
connected, as from states {3, 4} there is no way to states {1, 2}. All
automorphisms of these automata are state-automorphisms.
1 2
3 4
A1
a, b a, b
a
a
b b
1 2
3 4
A2
a a
a
a
b
b
b
1 2
3 4
A3a a
a
a
b b
b
b
Figure 1. Reachable, but not strongly connected automata with automorphism
group Z2.
3. Internal versus external automorphisms
3.1. Internal symmetries
Now we can answer the question ‘What is the relation between the
automorphism group of the automata and some subgroups of its charac-
teristic monoid?’ The results of the previous section can be interpreted
as saying that all state-automorphisms are ‘internal’, i.e. arise through
a homomorphism from some group element inside the characteristic
monoid. Similarly, Proposition 3 can be interpreted as saying that all
state-endomorphisms are ‘internal’, i.e. arise from some monoid element
inside the characteristic monoid.
54 Symmetries of automata
There is also a very fine distinction amongst internal automorphisms.
Being internal does not necessarily mean that an automorphism can
be realized by directly by the action of an element of the characteristic
semigroup on the states of A, but it is always realized as the image of an
element of the Fleck monoid under the map α defined previously.
Examples 8. Let A1, A2, and A3 be the automata from the Examples 7.
Then M(A1) is
{
a=( 1 2 3 4
2 1 3 4 ) , b=ba=( 1 2 3 4
3 4 3 4 ), ab=b2 =( 1 2 3 4
4 3 3 4 ), id=a2 =( 1 2 3 4
1 2 3 4 )
}
,
and Aut(A1) is the order 2 cyclic group Z2 generated by (1, 2)(3, 4)
(= ( 1 2 3 4
2 1 4 3 ) written in transformation notation), which is not an element
of the characteristic monoid. Similarly, Aut(A3) = 〈(1, 2)(3, 4)〉 ∼= Z2, and
no letter or word of A3 realizes this permutation. However, Aut(A2) is
also Z2 but generated by (1, 2) which is a = ( 1 2 3 4
2 1 3 4 ), a transformation
corresponding to an input symbol of A2. Although the automorphism
groups are internal in all three cases, the automorphisms are realized
by input words for A2, but not for A1 or A3. Nevertheless, in each case
Aut(Ai) = Aut∗(Ai) = 〈α(a)〉, where the action of the one-letter word a
at state 1 determines the generator (as in Proposition 3).
3.2. External symmetries
There exist automorphisms of automata which are not state-
automorphisms. An automorphism or endomorphism which is not the
identity on inputs cannot be realized by applying words to states since
these have no effect on input letters. These automorphisms are in a sense
‘external’.
Example 9. The flip-flop is a 2-state identity-reset automaton.
1 2
1, b 1, a
a
b
Figure 2. Flip-flop automaton F with two states, and three input letters:
the identity map and two resets.
A. Egri-Nagy, Ch. L. Nehaniv 55
The automorphism (π, θ) with π(1) = 2, π(2) = 1, θ(a) = b, θ(b) = a,
and θ(1) = 1 generates the automorphism group Aut∗(F) = Z2, while
M(F) is aperiodic (has no nontrivial subgroups).
Caveat: The group of general automorphisms need not divide the charac-
teristic monoid of the automaton. Here in Example 9, Aut∗(F) 6� M(F).
A symmetry of the diagram of the automaton does not entail the existence
of non-trivial subgroups in the characteristic monoid of the automaton,
unless these symmetries are internal automorphisms (i.e., the identity on
input letters).
4. Symmetries and wreath product
The presence of a non-trivial symmetry group of state-automorphisms
permits better understanding of an automaton’s structure. Formally, the
‘better understanding’ corresponds to a wreath product decomposition.
4.1. Quotient of an automaton by a group of symmetries
Let A = (X, Σ, δ) be an automaton and let G be a group of symmetries
(via state-automorphisms) of A. An equivalence relation on X is given
by x ≡ x′ iff there exists an symmetry π ∈ G, π(x) = x′, Denote by [x]
the set of all states x′ ∈ X equivalent to x under the action of G. Let
XG = {[x] : x ∈ X} be the set of orbits under the action of G, i.e., the
partition blocks of this equivalence relation. Let [x] · a = [x · a] for each
[x] ∈ XG and a ∈ Σ. Since x′ = π(x) implies x′ · a = π(x) · a = π(x · a),
so x′ · a ∈ [x · a], the action of the inputs is well-defined on XG. We write
ΣG for set of the induced mappings by inputs Σ on the quotient set XG.
Thus the quotient automaton AG = (XG, ΣG, δG) is well-defined for any
group of state-automorphism symmetries G, and its characteristic monoid
M(AG) is clearly a quotient of M(A).
4.2. Wreath product decomposition under symmetries
The following theorem generalizes [Rho10, Fact 4.7] or the result of
[Neh96, Sec. 4.2].2
Theorem 10. Let A = (X, Σ, δ) be an automaton and let G 6 Aut(A)
be any group of symmetries of A consisting of state-automorphisms. Then
2These references treat only the transitive case, and do not include the result that
the automorphism group divides the original monoid.
56 Symmetries of automata
1) A 6 (X, M(A)) � (XG, M(AG)) ≀ (G, G)
2) If M(A) acts transitively on X, then this division is an embedding.
3) The group G divides M(A) and, if A is a finite automaton, then G
is a homomorphic image of a subgroup of M(A).
In particular, we have the new result that the algebraic components
of the decomposition, G and M(AG), both divide M(A). Hence internal
symmetries result in a decomposition into ‘pieces’ existing in the original
characteristic monoid of A.
Proof. For each [x] ∈ XG, choose a representative [x] ∈ [x]. Then if x ∈ [x],
there exists π with π([x]) = x. Now each x in X is then coordinatized
as ([x], π), and we have ϕ([x], π) = π([x]) = x. For s ∈ Σ, we lift s to
s̃ with ([x], π) · s̃ = ([x] · s, π · π′), where π′ ∈ G is chosen such that
π′([x · s]) = [x] · s. Then s̃ has component action in M(AG) at the top
level, and component action given by π′ ∈ G, with π′ depending only on
[x] and s. It follows that
ϕ(([x], π) · s̃) = ϕ([x · s], ππ′) = ππ′([x · s])
= π(π′([x · s])) = π([x] · s)
= π([x]) · s = x · s
= ϕ([x], π) · s,
establishing (1)). (2)) Suppose M(A) acts transitively on X. Then we show
G acts regularly on X. For if x 6= x′ ∈ X, there exist s1, . . . , sk ∈ M(A)
with x · s1 . . . sk = x′. Then, π(x′) = π(x · s1 . . . sk) = π(x) · s1 . . . sn. So if
π ∈ G fixes any x ∈ X, then π fixes all x′ ∈ X as well. Thus, if π1([x]) = x
and π2([x]) = x for any π1, π2 ∈ G, then π−1
2 π1([x]) = [x]. Therefore π−1
2 π1
fixes all x′ ∈ X, and so π1 = π2. Thus the coordinatization of x as ([x], π) is
unique. This shows state embedding. Next we show semigroup embedding:
in the lift s̃ of s, π′ : XG → G is uniquely determined for each [x] by
the condition that π′([x · s]) = [x] · s, since another π2 with this property
would equal π′ since π−1
2 π′ would fix [x ·s] and hence all of X. Thus lifting
is injective. It follows also that it is a homomorphism of transformation
semigroups. (3)) follows from Proposition 4 and Corollary 6.
Theorem 10 says non-trivial state-automorphisms entail a non-trivial
wreath product decomposition using only semigroups dividing the charac-
teristic monoid. In contrast, for non-state-automorphisms, the situation
is different: in the flip-flop automaton (Example 9), there is an order 2
A. Egri-Nagy, Ch. L. Nehaniv 57
automorphism but no corresponding wreath product decomposition with
the group generated by this external symmetry as a factor, and moreover
this group does not divide the characteristic monoid.
References
[ABMN10] J. Araújo, P.V. Bünau, J.D. Mitchell, and M. Neunhöffer. Computing
automorphisms of semigroups. Journal of Symbolic Computation, 45(3):373
– 392, 2010.
[DN05] Pál Dömösi and Chrystopher L. Nehaniv. Algebraic Theory of Finite
Automata Networks: An Introduction, volume 11 of SIAM Series on Dis-
crete Mathematics and Applications. Society for Industrial and Applied
Mathematics, 2005.
[Eil76] Samuel Eilenberg. Automata, Languages and Machines, volume B. Aca-
demic Press, 1976.
[Fle65] A. C. Fleck. On the automorphism group of an automaton. Journal of the
Association for Computing Machinery, 12(4):566–569, 1965.
[KRT68] Kenneth Krohn, John L. Rhodes, and Bret R. Tilson. The prime de-
composition theorem of the algebraic theory of machines. In Michael A.
Arbib, editor, Algebraic Theory of Machines, Languages, and Semigroups,
chapter 5, pages 81–125. Academic Press, 1968.
[Neh96] Chrystopher L. Nehaniv. Algebra and formal models of understanding. In
Masami Ito, editor, Semigroups, Formal Languages and Computer Systems,
volume 960, pages 145–154. Kyoto Research Institute for Mathematics
Sciences, RIMS Kokyuroku, August 1996.
[Rho10] John Rhodes. Applications of Automata Theory and Algebra via the Math-
ematical Theory of Complexity to Biology, Physics, Psychology, Philosophy,
and Games. World Scientific Press, 2010. Foreword by Morris W. Hirsch,
edited by Chrystopher L. Nehaniv (Unpublished version: University of
California at Berkeley, Mathematics Library, circa 1971).
Contact information
Attila
Egri-Nagy
Centre for Research in Mathematics, SCEM,
University of Western Sydney (Parramatta Campus)
Locked Bag 1797, Penrith, NSW 2751, Australia
E-Mail(s): a.egri-nagy@uws.edu.au
Web-page: www.egri-nagy.hu
Chrystopher L.
Nehaniv
Centre for Computer Science & Informatics Research,
University of Hertfordshire, College Lane, Hatfield,
Herts AL10 9AB, United Kingdom
E-Mail(s): C.L.Nehaniv@herts.ac.uk
Web-page: homepages.stca.herts.ac.uk/~nehaniv
Received by the editors: 02.05.2014
and in final form 12.01.2015.
|