Information Technology Reference
In-Depth Information
2.1
Multiple Attractor Cellular Automata
The state transition graph of an
MACA
consists of a number of
cyclic
and
non-cyclic
states. The set of non-cyclic states of an
MACA
forms inverted
trees rooted at the cyclic states. The
cycles
are referred to as
attractors
.
Fig.1
depicts the state transition diagram of a 5-cell
MACA
with four attractors
{
00000,00011,00110,00101
}
having self loop. In rest of the paper, by an attrac-
tor we will refer to a cycle of length 1. The states of a tree rooted at the cyclic
state
α
forms the
α-basin
.
With reference to the state transition diagram of a
CA
, the
depth d
of the
CA
is the number of edges between a non-reachable state and the attractor. The
depth
d
of the 5-cell
MACA
of
Fig.1
is 3.
01000
01010
10100
10110
01001
01011
10101
10111
3
11100
11110
11111
11101
2
00010
00001
1
(0)
000
00
(3)
000
11
0
10010
10000
01110
01100
01101
01111
10011
10001
3
11000
11010
11001
11011
2
11000
11000
T =
01100
00101
00001
00100
00111
1
(6)
001
10
(5)
001
01
0
Fig. 1.
State transition diagram of a 5-cell
MACA
The detailed characterization of
MACA
is available in [1]. A few fundamen-
tal results for an
n
-cell
MACA
having
k
number of attractors is next outlined.
Result I:
The characteristic polynomial of the
MACA
is
x
n−m
(1 +
x
)
m
,
where
m
=
log
2
(
k
).
Result II:
The characteristic polynomial noted above can be also written
in elementary divisor form as
(1 +
x
)(1 +
x
)
··m times
x
d
1
x
d
2
··x
d
p
where
d
1
≥ d
2
·· ≥ d
p
and
d
1
+
d
2
····
+
d
p
=
n − m
.
Result III:
The minimal polynomial of an
MACA
is
x
d
1
(1 +
x
), where
depth =
d
1
.
Definition 1
An m-bit field of an n-bit pattern set is said to be pseudo-
exhaustive if all possible
2
m
patterns appear in the set.
