D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction
Подождите немного. Документ загружается.
7.5.
Asynchronous
Automata Networks
231
= a
v
(
(T(n
— 1), v) + 1) by
definition
of
local update
in A,
=
a
v
(k(i(ri),
v))
since
at
time t(ri) there
is a
real update
at v.
This shows (1).
Also
by
definition
of 8
V
, we
have that
the
second component
of
a
v
(r(n)) equals
the
first
component
of
a
v
(r(n
—
1)),
so
by
induction hypothesis,
again since
at time
r(n) there
is a
real
update
at v.
This shows
(2) and
completes
the
induction.
The
lemma
is
proved.
Remark.
By
Lemma 7.26,
for
each node
VQ
e V,
A(r(n),
VQ)
takes
all
nonnegative
integer
values,
so
Proposition 7.27 shows
how to
recover
the
entire
history
of
node
v
in
A:
just
record
the first
component
of the
state
at
node
v in A
every
time
there
is a
real
update
at v.
Thus
the
sequence
of
global states a(0),
a(l),...
of
Asunder
a
given
external
input
sequence
x\, *2, • • • can be
recovered
from
any
behavior
of
A
started
in
state
a
v
(0)
=
(a
v
(0), a
u
(0),
3) for all v e V
with
the
same
input
sequence.
The
results above establish
all the
properties asserted
for A in the
statement
of
Theorem 7.22, whose proof
is now
complete.
Definition.
For a
given external
input
sequence
{jc
n
}
M>
o
and
update
pattern
(r, U), any
Junction
r]
: N x V -+ R
+
satisfying,
for all v € V, n e N,
is^called
a
spatial-temporal section
of
the
behavior
of
the
asynchronous automata network
A
mapping
onto
the
behavior
of
the
synchronous automata network
A
Corollary
7.28
(existence
of
spatial-temporal
sections).
Letrj
r
: NX V ->• R
+
be
defined
by
rj
r
(n,
v) = the
least r(m) with
m e N
such that
A.(r(m),
i>)
is n.
Then
rj
r
is a
spatial-temporal
section
of
the
behavior
of
the
asynchronous
automata network
A
mapping
onto
the
behavior
of
the
synchronous automata network
A
Proof.
As
noted
in the
above remark,
for
every node
u,
local
time
A.(r(m),
v)
takes
all
values
n e N, so
r]
T
is
well defined.
By
Proposition 7.27, this function
is a
spatial-temporal
section.
The
function
rj
r
of
Corollary 7.28
is
called
the
natural
spatial-temporal
section
for
fixed
external input sequence
{JC
M
}
W
>O
and
update pattern
(r, U) of the
behavior
of A.
Generalized
Cellular
Automata
and
Cellular
Automata.
A
synchronous
or
asynchronous
automata network
is
said
to be a
generalized
cellular automaton
if its
external input alphabet
232
Chapter
7.
Finite
State-Homogeneous
and
Asynchronous
Automata Networks
X
is a
singleton.
In the
synchronous case,
the
external input serves,
in
effect,
only
as a
global synchronous update signal
for A,
i.e.,
a
clock tick,
but
does
not
otherwise
affect
the
state
of
A.
44
Similarly,
in the
asynchronous case,
the
external input letter serves
as a
local
update
signal
for A
v
whenever
v e
U
T
(
n
)
and
p
v
(i(n
—
!)) = 1.
A
generalized cellular automaton
A is a
cellular automaton
if it
satisfies
the
following:
(1)
The
edge relation
E is a
symmetric relation
on V\ (2) for
every
u, w e V, A
w
= A
v
,
that
is, a
copy
of the
same local automaton occurs
at
each node;
(3) for
every
v, w e V,
there
is a
corresponding graph automorphism
TT
: D ->
T>
with
jr(i>)
= w
such that
for all
a
e A,
Conditions
(2) and (3)
imply that
the
automata network
is
highly homogeneous
in
that
every
vertex
in the
network
has an
isomorphic local neighborhood and, also,
the
component
automaton
at
each vertex computes
the
same transition function
of the
states
of
component
automata
in its
local
neighborhood
as
computed
by any
other component automaton
in the
network.
(In
particular
a
cellular automaton
is
state-homogeneous.)
The
isomorphic local automata
at any two
nodes
v and v' in a
cellular automaton
are
sometimes referred
to as
cells
of A.
(For automata networks
in
general,
the
local automata
A
v
are
sometimes referred
to as the
cells
of A,
too.)
Corollary 7.29
(asynchronous
emulation
of
generalized
cellular automata).
If
A is
a
synchronous generalized cellular automaton, then
there
is an
emulating asynchronous
automata
network
satisfying
the
same conclusions
as in
Theorem
7.22,
but
also
A is an
asynchronous
generalized cellular automaton.
Proof.
This
is of
course just
a
special case
of
Theorem 7.22, with
the
additional observation
that
A is an
asynchronous generalized cellular automaton since
it has the
same singleton
alphabet
as A.
But
it is
worth remarking that
in
this case
a
further
simplification
is
possible. Since
the
external input alphabet
X =
{x},
all
input letters
in the
infinite
external input sequence
are
identical. Thus
it is
possible
to
completely ignore
the
external input letter
in the
feedback
functions
<p
v
,
and, moreover,
it is
unnecessary
to
keep track
locally
of
which letter
in the
infinite
word
is
available
for
reading. Therefore
the
definition
of
p
v
(a)
can be
simplified
to be
constant
p
v
(a)
= 1 for all v G V and a e A
without
affecting
the
global run.
The
resulting asynchronous generalized cellular automata never waits before reading
a
letter,
node
v is
updated exactly when
v e U
t
, and no
wait symbol cases
are
needed
for the
feedback
functions; i.e.,
we
restrict
<p
v
to A x X > X
v
using
X
rather than
X
9
Since
X is
a
singleton
we may as
well simplify feedback functions
to
have
form
<p
v
: A -> X
v
.
Thus,
the
local transition
functions
then simplify
to
^The
reader familiar with
cellular
automata
may find it
helpful
to
think
of A as a
cellular
automaton, except
that
the
interconnection graph
D is not
required
to be
regular,
the
local
automata
A
v
are not
required
to
be
isomorphic,
and
neighborhoods
are not
required
to be
symmetric,
(v €
N(v')
does
not
necessarily imply
v'
€
N(v)
for
vertices
v,
v'.)
7.5. Asynchronous Automata Networks
233
where
c is an
arbitrary
state
of A
such
that
for
each
w e
N(v),
Corollary
7.30
(asynchronous
emulation
of
cellular
automata).
If
A is a
synchronous
cellular automaton, then there
is an
emulating asynchronous generalized cellular automa-
ton
satisfying
the
same conclusions
as in
Corollary 7.29,
but
also
A is an
asynchronous
cellular automaton.
Proof.
This
is
clear
since
the
digraph
D of A is
identicaUo
the
digraph
D of A
except
pos-
sibly
that
all
nodes
become
neighbors
of
themselves
in
D,
and so A
inherits
the
conditions
in
the
definition
of
cellular
automata
satisfied
by A.
Remarks
on
Local
External
Inputs.
By
applying
the
asynchronous emulation theorem
for
automata networks,
the
results
of
this section
easily
generalize
to the
case where local
automata
at
each node
v
have access
to
separate input external sequences from possibly
different
external alphabets depending
on v: One
simply
replaces
the
external alphabet
X
by
a new
external alphabet
Z
which
is the
product
of
the
external
alphabets
for
each node
and
only
allows
the
feedback function
at v to
depend
on the
projection
of
an
external letter
of
Z
giving
the
external
input
for
node
v.
Remark
on
Asynchronous
Universal
Computation.
One-dimensional cellular automata
(cellular
automata over
the
digraph
Z of
integers
as
nodes, with edges from
an
integer
to
integers
differing
by a
most one)
are
computationally universal:
One can
encode
any
universal
Turing
machine
U
into this cellular space
by
letting state
at a
node
keep
track
of
(I)
contents
of the
corresponding cell
on the
Turing
machine's
tape,
(2)
whether
the
read-write
head
of
the
Turing
machine
is
present
in the
given location,
and (3) the
state
of
the finite-state
memory
of
read-write head controller
if
it is
present
in the
given cell. Since
transitions
in the
Turing
machine's computation (changes
of
contents
of
the
cell being
read,
movement
left
or
right,
and
changes infinite-state controller)
are
determined locally, these
transitions
can be
encoded
in a
corresponding cellular automaton rule giving
a
cellular
automaton
U
over
Z
whose behavior
on any
starting
configuration
is
that
the
same
as
that
ofU.
By the
results
on
asynchronous emulation
of
cellular automata (Corollary 7.30),
there
is a
one-dimensional asynchronous cellular automaton
U
over
the
same digraph that
emulates
U,
i.e.,
can
compute
any
partial
recursive function.
Remarks
on
Implementations
and
State
Number.
(1) The
need
for a
global clock
that
is
required
by
synchronous automata networks
and
(generalized)
cellular automata
is
eliminated
by the
asynchronous emulation theorem.
It
constructively shows
how an
asyn-
chronous emulation
can be
implemented, e.g.,
on
parallel, distributed, and/or asynchronous
234
Chapter
7.
Finite State-Homogeneous
and
Asynchronous Automata Networks
computational devices, without global clocks,
and how the
synchronous behavior
can be
recovered.
(2) In
computational implementations
of
synchronous cellular automata
on
present-day sequential computers
it is
usual
to
keep
two
copies
of
the
state space,
one for
current state
of
the
entire space
and one for the
next state into which
updated
local states
are
written
as
they
are
computed.
Before
the
next global time step,
the two
global copies
are
exchanged,
and
then
the
process
is
repeated. Thus
in
practice
for
each cell
A
v
in the
space,
one
keeps
two
copies
of
local states.
So
if
there
are
\A
V
\
=n
possible states
in
each
cell,
this corresponds
to n
2
possible
states
for
each cell
in an
implementation.
For
asynchronous cellular automata,
our
construction
of
A for
Corollary 7.30 (and
for
asynchronous automata networks more generally
in
Theorem 7.22) uses local automata
that
for
each
of the
corresponding synchronous local automaton keep
a
copy
of
current
local
state (their
first
component), which
is
current according
to
local time X(t,
v), and a
copy
of
the
previous local state
(in
their second component),
and in
addition
a
modulo
3
counter value.
There
are
thus
3n
2
=
\A
V
\
=
\A
V
\
x
\A
V
\
x 3
possible local states.
But if
v, v' € U
t
implies d(v,
t/) 1
(e.g.,
if
only
a
single random node
is
updated
at a
time),
then
it
unnecessary
to
keep auxiliary copies
of
the
entire state space
(or
even
of
the
portion
to be
updated)
in a
sequential implementation.
The
only
essential increase
in
memory
usage
is
then
the
addition
of
local modulo
3
counters
at
each node.
Remark
on
Local
Synchronization
with
Modulo
n
Counters.
It is
straightforward
to
modify
the
proof
of
Theorem 7.22
to
obtain
a
variant result using modulo
n
counters,
for
n > 3,
rather than modulo
3
counters
for
local synchronization. This
of
course results
in
corresponding variants
of
Corollaries 7.29
and
1.30
for
asynchronous emulation
in the
realms
of
generalized cellular
and
cellular automata.
Problem
7.31.
The
asynchronous emulation theorem (Theorem 1.22) allows
the
update sets
U
r
(
n
)for
n > 0 to be
arbitrary subject only
to
having
v e
U
r
(
n
)for
infinitely
many
n.
Thus,
for
example, deterministic
or
nondeterministic, sequential,
uniformly
random,
or
Poisson-
distributed,
locally synchronous,
and
other choices
of
update
patterns
are
permitted.
(1)
For
particular
types
of
update
patterns
and
network topologies, derive precise bounds
on the
rate
of
local real update. Given
v e V
study
the
relative passage
of
local time
in
the
asynchronous model
at
node
v as
compared
to the
synchronous one; i.e.,
for
synchronous global time
t e N
determine bounds
on the
ratio
for
t > 0, and
study
its
behavior
as t
—>
.
Under
what circumstances does
the
ratio remain bounded away from zero?
(2)
Also
determine
the
precise
(or
expected)
number E(t$)
of
asynchronous
updates
for
local
time
to
exceed
t$;
i.e., determine E(to)
e E
+
with
Under
what circumstances
is
E(to) independent
ofv?
(3)
Extend
the
asynchronous emulation theorem
and its
corollaries
to
networks
in
which
the
underlying graph
is
permitted
to
change over time, i.e., with addition
or
deletion
of
new
edges
and
nodes.
7.6.
Bibliographical
Remarks
235
(4)
Extend
the
results
to the
case when state changes
are not
instantaneous,
and a
node
may
receive
delayed
information
concerning
the
states
of
its
neighbors.
(5)
Develop
methods
for
synchronous
and
asynchronous
automata
networks
to
cope
with
defective
local
automata
and
errors
in
transmission
of
local
state
to
neighbors.
(6) Is it
possible
to
obtain analogous
results
to
those
of
this paper
if
sometimes
letters
of
external
input
have
not yet
arrived
at
nodes
reading
them?
This
would
represent
a
strengthening
of
the
asynchronous
emulation theorem (but
not for the
generalized
cellular
automata
analogues),
since
it
would
then
not
need
to be
assumed
that
the
next
letter
of
global
input
were
always
available
for
local
reading,
thus
allowing
for
delays
in the
external
input
reaching
local
nodes
of
the
network.
7.6
Bibliographical Remarks
Section
7.1. Technical results
on finite
state-homogeneous networks given
in
this section
were
described
by P.
Domosi
and C. L.
Nehaniv
[1997,1998].
Section
7.2. Lemma 7.10
and
Propositions 7.11
and
7.12
can
also
be
derived
from
results
in
Domosi
and
Nehaniv [1998]. Theorem 7.13
is due to M.
Tchuente [1988]. Theorem
7.14
was
proved
in
Domosi
and
Kovdcs [1992].
Section
7.3. Complete
finite
network graphs with minimal number
of
edges were com-
pletely characterized
by P.
Domosi
and C. L.
Nehaniv
[1999].
Section
7.4.
The
results
of
this section
was
given
in
Domosi
and
Nehaniv
[1998].
Section
7.5. Cellular automata were introduced
by J. von
Neumann
and S.
Ulam;
an
important early study
is by J. von
Neumann
[1966].
See
also
E. F.
Codd
[1968]
and
A.
W.
Burks
[1970].
Studies
of
asynchronous automata networks with applications
to
computer
and
electrical engineering include, e.g., Varshavsky [1965 (with
B. L.
Osievich),
1968, 1969, 1990]
and his
collaborators
M.
Kishinevsky
et al.
[1994a,
1994b]
and
also
J. A.
Brzozowski
and
C.-J. Seger [1995],
J. A.
Brzozowski
[2000],
and
many others.
Theorem 7.22,
its
corollaries,
and all
other results
of
Section
7.5 are due to C. L.
Nehaniv
[2002a
and in
press]
and
follow
the
proofs
in C. L.
Nehaniv
[in
press].
The
observation that
synchronous
cellular automata
can
perform universal computation
is due to A. R.
Smith
IE
[1971].
The
asynchronous emulation theorem (Theorem 7.22),
its
corollaries
(Corollaries
7.29
and
7.30, which extend previously known constructions
but
incompletely proved
results),
and all
other results shown here
are due
independently
to C. L.
Nehaniv [2002a
and
in
press]. Formulations equivalent
to
Corollary 7.30 were
found
by K.
Nakamura [1974],
who
sketched
a
proof
of
freedom
from
deadlocks,
and
independently
by C. L.
Nehaniv
[2002a
and in
press],
and
also
in
related, weaker
form
but
without complete proof
by
T.
Toffoli
[1978]
and T.
Toffoli
and N.
Margolus
[1987].
Applications exhibiting
the
details
of the
construction
in the
simplified case
of em-
ulating synchronous cellular automata
by
asynchronous cellular automata,
and the first
examples
of
self-replication
and of
evolution
in
implemented asynchronous cellular
au-
tomata,
as
well
as
remarks
on
universal computation
in
asynchronous cellular automata,
were
given
by C. L.
Nehaniv [2002b,
2002c].
This page intentionally left blank
Bibliography
A.
Adam
[1996],
Behavior
and
Simplicity
of
Moore
Automata. Akademiai Kiado, Budapest,
1996.
G. P.
Agibalov
and N. V.
EvtuSenko
[1979],
Characterization condition
of
existence
and
other problems
of
cascade connections
of
finite
automata
(in
Russian).
MTA
SZTAKI
Tanulmdnyok,
99
(1979),
181-197.
G. P.
Agibalov
and N. V.
Evtusenko
[1984],
Algebraic characterization
of
permutation
automata
decomposable into cascade connection
of
smaller components
(in
Russian).
Kibernetika,
1
(1984),
9-15.
S. V.
AleSin
[1970a],
Bases
in
groups
of
automaton permutations
(in
Russian). Diskret.
Analiz.,
17
(1970),
3-8.
S. V.
AleSin
[1970b],
On the
absence
of
bases
in
certain classes
of
finite
automata
(in
Russian). Problemy Kibernet.,
22
(1970),
67-74, 296-297.
D. S.
Ananichev,
P.
Domosi,
and C. L.
Nehaniv. Some properties
of
digraphs
and
semi-
groups, Acta Cybernet.,
to
appear.
M. A.
Arbib
(ed.)
[1968], Algebraic
Theory
of
Machines,
Languages
and
Semigroups,
with
a
Major
Contribution
by K.
Krohn
and J. L.
Rhodes. Academic Press,
New
York,
1968.
B.
Austin,
K.
Henckell,
C.
Nehaniv,
and J.
Rhodes [1995], Subsemigroups
and
complexity
via the
presentation lemma.
J.
PureAppl. Algebra,
101
(1995),
245-289.
I.
Babcsanyi
and A.
Nagy [2004], Homomorphic direct product
of
automata, Publ. Math.,
in
press.
A.-L. Barabasi [2002],
Linked,
The
Neve
Science
of
Networks.
Perseus, Cambridge, Mass.,
2002.
A.-L. Barabasi
and E.
Bonabeau
[2003],
Scale-free networks.
Scientific
American,
May
2003,
60-69.
W.
A.
Barret
and J. D.
Couch,
Compiler
Construction:
Theory
and
Practice.
Science
Research Associates,
Inc.,
Chicago,
1979.
237
238
Bibliography
M.
Bartha
and M.
Kresz
[2000],
Elementary decomposition
of
soliton automata. Acta
Cybernet.,
14
(2000),
631-652.
R.
Bartlett
and M.
Garzon [1993], Monomial cellular automata.
Complex
Systems,
7
(1993),
367-388.
R.
Bartlett
and M.
Garzon
[1995],
Bilinear cellular automata.
Complex
Systems,
9
(1995),
455^76.
Z.
Bavel [1983],
Introduction
to the
Theory
of
Automata.
Reston Publishing Company, Inc.,
Reston,Va.,
1983.
T.
L.
Booth
[1967],
Sequential
Machines
and
Automata
Theory.
John Wiley
and
Sons, Inc.,
New
York,
1967.
J. G.
Brookshear [1989],
Theory
of
Computation:
Formal
Languages, Automata,
and
Complexity.
Benjamin/Cummings Publishing Company,
Inc.,
Redwood City, Calif.,
1989.
A.
Briiggemann,
L.
Priese,
D.
Rodding
and R.
Scha'tz [1983], Modular decomposition
of
automata.
In
Logics
and
Machines:
Decision Problems
and
Complexity,
E.
Borger,
G.
Hasenjaeger,
D.
Rodding,
eds.,
Lecture Notes
in
Comput.
Sci. 171,
Springer-
Verlag,
New
York,
1983,
198-236.
A.
Briiggermann-Klein
and R.
Klein [1987],
On the
minimality
of K, F, and D or: Why
Loten
is
non-trivial.
In
Computation
Theory
and
Logic, Egon Borger
ed.,
Lecture
Notes
in
Comput.
Sci. 270,
Springer-Verlag,
New
York, 1987,
59-66.
J. A.
Brzozowski [2000], Delay-insensitivity
and
ternary simulation.
Theoret.
Comput.
Sci.,
245
(2000),
3-25.
J.
A.
Brzozowski
and
C.-J.
Seger
[1995],
Asynchronous
Circuits.
Springer-Verlag,
New
York,
1995.
A.
W.
Burks (ed.) [1970],
Essays
on
Cellular
Automata.
University
of
Illinois
Press, Urbana,
1970.
G.
Chartrand
and F.
Harary [1967], Planar permutation graphs. Ann. Inst. Henri Poincare,
N.
Ser,
Sect.
B, 3
(1967),
433^38.
C.
Choffrut
(ed.) [1986], Automata
Networks.
Lecture Notes
in
Comput. Sci. 316, Springer-
Verlag,
New
York,
1986.
M.
Ciric,
B.
Imreh,
and M.
Steinby [1999], Subdirectly irreducible definite, reverse definite,
and
generalized definite automata. Publ. Electrotechn. Fak. Ser. Mat.,
10
(1999),
69-79.
A. H.
Clifford
and G. B.
Preston
[1961],
The
Algebraic
Theory
of
Semigroups,
Vol.
I.
Math.
Surveys
7.1, AMS, Providence, R.I.,
1961.
A.
H.
Clifford
and G. B.
Preston
[1967],
The
Algebraic
Theory
of
Semigroups,
Vol.
n.
Math.
Surveys
7.2,
AMS, Providence, R.I.,
1967.
Bibliography
239
E. F.
Codd
[1968],
Cellular
Automata. Academic Press,
New
York,
1968.
D. I. A.
Cohen
[1977],
Introduction
to
Computer
Theory,
2nd ed.
John Wiley
and
Sons,
New
York, 1991.
M.
Conner
[1990],
Sequential machines
realized
by
group representations.
Inform,
and
Comput.,
85
(1990),
183-201.
M.
Conner
and R.
Tolimieri [1986], Group representation
for
multi-valued sequential
machines.
In
Proc.
Sixteenth
International
Symposium
on
Multivalued
Logic, Blacks-
burg,
Va., 1986,
258-265.
J. H.
Conway
[1971],
Regular
Algebra
and
Finite
Machines.
Chapman
and
Hall,
London,
1971.
B.
Csakany
and F.
Gecseg
[1965],
On the
group
of
automaton permutations
(in
Russian).
Kibernetika,
1
(1965),
14-17;
translated
as
Cybernetics,
1
(1965),
13-15.
J.
Dassow [1981],
Completeness
Problems
in the
Structural
Theory
of
Automata.
Akademie-
Verlag,
Berlin, 1981.
J.
Dassow
and H.
Jurgensen
[1990],
Soliton automata.
J.
Comput.
System
Sci.,
40
(1990),
154-181.
J.
Dassow
and H.
Jurgensen
[1991],
Soliton automata with
a
single exterior node.
Theoret.
Comput.
Sci.,
84
(1991),
281-292.
J.
Dassow
and H.
Jurgensen
[1993],
Soliton automata with
at
most
one
cycle.
J.
Comput.
System
Sci.,
46
(1993),
155-197.
M.
Demlova,
J.
Demel,
and V.
Koubek
[1981],
On
subdirectly irreducible automata.
RAIRO
Inform.
Theor.,
15
(1981), 23-6.
J.
Denes
[1986],
Research problem
40.
Period.
Math.
Hung.,
17
(1986),
245-246.
J.
Denes
and P.
Hermann [1982],
On the
product
of all
elements
in a finite
group. Ann.
Discrete
Math.,
15
(1982),
105-109.
P.
Denning,
J. B.
Dennis,
and J. E.
Qualitz
[1978],
Machines,
Languages,
and
Computation.
Prentice-Hall, Inc., Englewood
Cliffs,
N.J., 1978.
P.
Domosi [1972],
On the
semigroup
of
automaton mappings with
finite
alphabet. Acta
Cybernet.,
1
(1972),
251-254.
P.
Domosi [1975],
On
superpositions
of
automata. Acta
Cybernet.,
2
(1975),
335-343.
P.
Domosi [1976],
On
minimal
R
-complete systems
of finite
automata. Acta
Cybernet.,
3
(1976),
37-41.
P.
Domosi [1980],
On
homomorphically QD-complete systems
of
automata.
In
Papers
on
Automata
Theory,
II,
Karl Marx University
of
Economics, Budapest, 1980,
79-97.
P.
Domosi
[1981],
On
homomorphically -simple automata.
In
Papers
on
Automata The-
ory,
III, Karl Marx University
of
Economics, Budapest, 1981,
93-124.
240
Bibliography
P.
Domosi [1982],
On
homomorphically -complete systems
of
automata.
In
Papers
on
Automata
Theory,
IV,
Karl Marx University
of
Economics, Budapest,
1988, 57-68.
P.
Domosi [1983],
On
homomorphically -complete systems
of
finite
automata. Acta
Cybernet.,
6
(1983),
85-88.
P.
Domosi
[1984],
On
cascade products
of
standard automata.
In
Conference
on
Automata,
Languages
and
Mathematical
Systems,
Salgotarjan,
Karl Marx University
of
Economics, Budapest,
1984, 37-5.
P.
Domosi
[1986],
On
complete systems
of
automata.
In
Conference
on
Automata,
Lan-
guages
and
Programming
Systems,
Salgotarjan,
Karl Marx University
of
Economics,
Budapest,
1986, 87-95.
P.
Domosi
[1988],
On
temporal products
of
automata.
In
Papers
on
Automata
and
Lan-
guages,
X,
Karl Marx University
of
Economics, Budapest,
1988, 49-62.
P.
Domosi
[1990],
Products
of
automata
and
homomorphic simulation. Pure
Math.
Appl,
Ser.A,
1(1990),
11-19.
P.
Domosi [1992], Complete classes
of
finite
automata
and
simulation.
In
Proceedings
of
the
International
Conference
on
Words,
Languages
and
Combinatorics,
II,
Kyoto
Sangyo University, Kyoto, Japan,
M. Ito and H.
Jurgensen,
eds.,
World Scientific,
1994,
98-104.
P.
Domosi
[1996],
On
-v
3
-products
of
automata. Publ.
Math.,
48
(1996),
233-242.
P.
Domosi
and Z.
Esik
[1986],
On
homomorphic realization
of
automata with
-products.
In
Papers
on
Automata
and
Languages, VIII, Karl Marx University
of
Economics, Budapest,
1986, 63-97.
P.
Domosi
and Z.
Esik
[1987],
On
homomorphic simulation
of
automata
by
v
1
-products.
In
Papers
on
Automata
and
Languages,
IX,
Karl Marx University
of
Economics, Budapest,
1987, 91-112.
P.
Domosi
and Z.
Esik [1988a],
Critical
classes
for the
-product.
Theoret.
Comput.
Sci.,
61
(1988),
17-24.
P.
Domosi
and Z.
Esik [1988b],
On
homomorphic simulation
of
automata
by
-products. Acta
Cybernet.,
8
(1988),
315-323.
P.
Domosi
and Z.
Esik
[1988c],
On
homomorphic realization
and
homomorphic
simulation
of
automata
by
-products.
In
Second
Conference
on
Automata,
Lan-
guages
and
Programming
Systems,
Salgotarjan,
Karl Marx University
of
Economics,
Budapest,
1988, 89-98.
P.
Domosi andZ. Esik
[1988d],
On the
hierarchy
of
v
i
,-products
of
automata. Acta
Cybernet.,
8
(1988),
253-258.
P.
Domosi
and Z.
Esik [1990], Product hierarchies
of
automata
and
homomorphic simula-
tion. Acta
Cybernet.,
9
(1990),
371-373.