Massively parallel fault tolerant computations on syntactical patterns.
The general capabilities of reliable computations in linear cellular arrays are investigated in terms of syntactical pattern recognition. We consider defects of the processing elements themselves and defects of their communication links. In particular, a processing element (cell) is assumed to behave as follows. Dependent on the result of a self-diagnosis it stores its working state locally such that it becomes visible to the neighbors. A defective cell cannot modify information but is able to transmit it unchanged with unit speed. Cells with link failures are not able to receive information via at most one of their both links to adjacent cells. Moreover, static and dynamic defects are distinguished.It is shown that fault tolerant real-time recognition capabilities of two-way arrays with static defects are characterizable by intact one-way arrays and that one-way arrays are fault tolerant per se. For arrays with dynamic defects it is proved that all failures can be compensated as long as the number of adjacent defective cells is bounded.In case of arrays with link failures it is shown that the sets of patterns that are reliably recognizable are strictly in between the sets of (intact) one-way and (intact) two-way arrays.
Introduction
Nowadays it becomes possible to build massively parallel computing systems
that consist of hundred thousands of processing elements. Each single component
is subject to failure such that the probability of misoperations and loss
of function of the whole system increases with the number of its elements. It
was von Neumann [19] who rst stated the problem of building reliable systems
out of unreliable components. Biological systems may serve as good examples.
Due to the necessity to function normally even in case of certain failures of
their components nature developed mechanisms which invalids the errors, with
other words, they are working in some sense fault tolerant. Error detecting and
correcting components should not be global to the whole system because they
themselves are subject to failure. Therefore, the fault tolerance has to be a
design feature of the single elements.
A model for massively parallel, homogenously structured computers are the cellular
arrays. Such devices of interconnected parallel acting nite state machines
have been studied from various points of view.
In [4, 5] reliable arrays are constructed under the assumption that a cell (and
not its links) at each time step fails with a constant probability. Moreover, such
a failure does not incapacitate the cell permanently, but only violates its rule
of operation in the step when it occurs. Under the same constraint that cells
themselves (and not their links) fail (i.e. they cannot process information but are
still able to transmit it unchanged with unit speed) fault tolerant computations
have been investigated, e.g. in [6, 14] where encodings are established that allow
the correction of so-called K-separated misoperations, in [9, 10, 17, 20] where the
famous ring squad synchronization problem is considered in defective cellular
arrays, and in terms of interacting automata with nonuniform delay in [7, 11]
where the synchronization of the networks is the main object either.
Here we are interested in more general computations. In terms of pattern recognition
the general capabilities of reliable computations are considered. Since cellular
arrays have intensively been investigated from a language theoretic point
of view, pattern recognition (or language acceptance) establishes the connection
to the known results and, thus, inheres the possibility to compare the fault
tolerant capabilities to the non fault tolerant ones.
In the sequel we distinguish three dierent types of defects.
Static defects are the main object of Section 3. It is assumed that each cell
has a self-diagnosis circuit which is run once before the actual computation.
The results are stored locally in the cells and subsequently no new defects may
occur. Otherwise the whole computation would become invalid. A defective cell
cannot modify information but is able to transmit it with unit speed. Otherwise
the parallel computation would be broken into two non interacting parts and,
therefore, would become impossible at all.
In Section 4 the defects are generalized. In cellular arrays with dynamic defects
it may happen that a cell becomes defective at any time. The formalization of
the corresponding arrays includes also the possibility to repair a cell dynamically

The remaining sections concern another natural type of defects. Not the cells
themselves cause the misoperation but their communication links. It is assumed
that a defective cell is not able to receive information via at most one of its both
links to adjacent cells. The corresponding model is introduced in Section 5 in
more detail. In Section 6 it is shown that the real-time arrays with link failures
are able to reliably recognize a wider range of sets of patterns than intact one-way
arrays. In order to prove this result some auxiliary algorithmic subroutines
are given. Section 7 concludes the investigations by showing that the devices
with link failures are strictly weaker than two-way arrays. Hence, link failures
cannot be compensated in general but, on the other hand, do not decrease the
computing power to that one of one-way arrays.
In the following section we dene the basic notions and recall the underlying
intact cellular arrays and their mode of pattern recognition.
Preliminaries
We denote the integers by Z, the positive integers f1; 2;   g by N and the
set N [ f0g by N 0 . X 1      X d denotes the Cartesian product of the sets
we use the notion X d
alternatively. We use  for
inclusions and  if the inclusion is strict. Let M be some set and
be a function, then we denote the i-fold composition of f by f [i] ,
A two-way resp. one-way cellular array is a linear array of identical nite state
machines, sometimes called cells, which are connected to their both nearest
neighbors resp. to their nearest neighbor to the right. The array is bounded by
cells in a distinguished so-called boundary state. For convenience we identify
the cells by positive integers. The state transition depends on the current state
of each cell and the current state(s) of its neighbor(s). The transition function
is applied to all cells synchronously at discrete time steps. Formally:
Denition 1 A two-way cellular array (CA) is a system hS; -; #; Ai, where
1. S is the nite, nonempty set of cell states,
2.
S is the boundary state,
3. A  S is the set of input symbols,
is the local transition function.
If the
ow of information is restricted to one-way (i.e. from right to left) the
resulting device is a one-way cellular array (OCA) and the local transition
function maps from (S [ f#g) 2 to S.
A conguration of a cellular array at some time t  0 is a description of its
global state, which is actually a mapping c t
The data on which the cellular arrays operate are patterns built from input
symbols. Since here we are studying one-dimensional arrays only the input
data are nite strings (or words). The set of strings of length n built from
symbols from a set A is denoted by A n , the set of all such nite strings by A  .
We denote the empty string by " and the reversal of a string w by w R . For its
length we write jwj. The set A + is dened to be A  n f"g.
In the sequel we are interested in the subsets of strings that are recognizable by
cellular arrays. In order to establish the connection to formal language theory
we call such a subset a formal language. Moreover, sets L and L 0 are considered
to be equal if they dier at most by the empty word, i.e. L n
Now we are prepared to describe the computations of (O)CAs. The operation
starts in the so-called initial conguration c 0;w at time 0 where each symbol of
the input string is fed to one cell: c 0;w During
a computation the (O)CA steps through a sequence of congurations whereby
successor congurations are computed according to the global transition function
be a conguration, then its successor conguration is as
follows:
c t+1
c t+1
for CAs and
c t+1
for OCAs. Thus,  is induced by -.
An input string w is recognized by an (O)CA if at some time i during its course
of computation the leftmost cell enters a nal state from the set of nal states
F  S.
Denition be an (O)CA and F  S be a set of nal
states.
1. An input w 2 A + is recognized by M at time step
the conguration c
2. recognizes w at some time stepg is the set of
strings (language) recognized by M.
3. mapping. If M can recognize all w 2 L(M)
within at most t(jwj) time steps, then M is said to be of time complexity t.
The family of all sets which are recognizable by some CA (OCA) with time
complexity t is denoted by L t (CA) (L t (OCA)). If t equals the identity function
recognition is said to be in real-time, and if t is equal to k  id for an
arbitrary rational number k  1, then recognition is carried out in linear-time.
Correspondingly, we write L rt ((O)CA) and L lt ((O)CA). In the sequel we will
use corresponding notations for other types of recognizers.
Now we are going to explore some general recognition capabilities of CAs that
contain some defective cells. The defects are in some sense static [17]: It is
assumed that each cell has a self-diagnosis circuit which is run once before the
actual computation. The result of that diagnosis is stored in a special register
of each cell such that intact cells can detect defective neighbors. Moreover
(and this is the static part), it is assumed that during the actual computation
no new defects may occur. Otherwise the whole computation would become
invalid. What is the eect of a defective cell? It is reasonable to require that a
defective cell cannot modify information. On the other hand, it must be able to
transmit information in order to avoid the parallel computation being broken
into two not interacting lines and, thus, being impossible at all.
The speed of information transmission is one cell per time step. Another point
of view on such devices is to dene a transmission delay between every two
adjacent cells and to allow nonuniform delays [7, 11]. Now the number of
defective cells between two intact ones determine the corresponding delay.
Since the self-diagnosis is run before the actual computation we may assume
that defective cells do not fetch an input symbol. Nevertheless, real-time is the
minimal possible time needed for non-trivial computations and, consequently,
is dened to be the number of all cells in the array. In order to obtain a
computation result here we require the leftmost cell not to be defective. Later
on we can omit this assumption.
Formally we denote CAs with static defects by SD-CA and the corresponding
language families by L t (SD-CA).
Considering the general real-time recognition capabilities of SD-CAs the best
case is trivial. It occurs when all the cells are intact: The capabilities are those
of CAs. On the other hand, fault tolerant computations are concerned with
the worst case (with respect to our assumptions on the model). The next two
results show that in such cases the capabilities can be characterized by intact
OCAs from what follows that the bidirectionality of the information
ow gets
lost.
Theorem 3 If a set is fault tolerant real-time recognizable by a SD-CA, then
it is real-time recognizable by an OCA.
Proof. Let D be a SD-CA and let k 2 N be an arbitrary positive integer.
Set the number of cells of D to 1. For the mapping f
ng.
Now assume the cells at the positions f(i), 1  i  k, are intact ones and all the
other cells are defective (cf. Figure 1). In between the cells f(i) and f(i
there are f(i) f(i
defective ones.
During a real-time computation the states of a cell f(i) at time t  2 i cannot
in
uence the overall computation result. The states would reach the leftmost
a
a 1 a
a 2 a 1 a
a 3
a 2
a 1
a 0
a 4 a 3 a 2 a 1 a
a 5 a 4 a 3 a 2 a 1 a 0 b 5 b 4 b 3
a 6
a 5
a 4
a 3
a 2
a 1
a 0
a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 b 7
a 8 a 7 a 6 a 5 a 4 a 3 a 2 a 1
a 9
a 8
a 7
a 6
a 5
a 4
a 3
a a 9 a 8 a 7 a 6 a 5
a a 9 a 8 a 7
a 12 a 11 a 10 a 9
a 13
a 12
a 11
a 14 a 13
a 15

Figure

1: One-way information
ow in SD-CAs.
cell after another f(i)
steps. This gives the arrival time which is greater
than real-time.
Conversely, the cell f(i) computes all its states up to time t  independently
of the states of its intact neighbors to the left: The nearest intact
neighbor to the left is cell f(i+1) and there are 2 i 1 defective cells in between
Up to now we have shown that the information
ow in D is one-way. But
compared to OCAs the cells in D are performing more state changes. It remains
to show that this does not lead to stronger capabilities.
Let i be some intact cell of D. As long as it operates independently on its
intact neighbors it runs through state cycles provided that the adjacent defective
regions are long enough. Let s  be such a cycle.
Now one can always enlarge the lengths of the defective regions such that they
correspond to j
Therefore, during their isolated computations the cells run through complete
cycles. Obviously, such a behavior can be simulated by the cells of an OCA
since the cycle lengths are bounded by the number of states of D. 2
In order to obtain the characterization of real-time SD-CAs by real-time OCAs
we need the converse of Theorem 3.
Theorem 4 If a set is real-time recognizable by an OCA, then it is fault tolerant
real-time recognizable by a SD-CA.
Proof. The idea of the simulation is depicted in Figure 2. Each cell of a
SD-CA that simulates a given OCA waits for the rst information from its
right intact neighbor. The waiting period is signaled to its left intact neighbor
by signals labeled . This information leads to a waiting period of the left
intact neighbor. Each intact cell performs a simulation step when it receives a
non-waiting signal.
It follows that a cell sends exactly as many waiting signals to the left as are
defective cells located to its right. Therefore, the leftmost cell needs exactly
one simulation step for each intact cell and one waiting step for each defective
cell and, thus, computes the result in real-time. 2
a 0
a 0
a 0
a 0
a 0
a 0
a 0
a 0
a 1
a 1
a 1
a 2
a 3
a 4

Figure

2: OCA simulation by SD-CAs.
The following corollary formalizes the characterization:
Corollary 5 L rt
From the previous results follows the interesting fact that OCAs are per se fault
tolerant. Additional defective cells do not decrease the recognition capabilities.
Corollary 6 L rt
It is often useful to have examples for string sets not recognizable by a certain
device.
Example 7 Neither the set of duplicated strings fww nor the set
of strings whose lengths are a power of 2 fw are
fault tolerant real-time recognizable by SD-CAs.
(It has been shown in [13] resp. [15] that they do not belong to the family
The previous results imply another natural question. Is it possible to regain
the recognition power of two-way CAs in fault tolerant SD-CA computations
by increasing the computation time? How much additional time would be
necessary? In [3, 18] it has been shown that an OCA can simulate a real-time
computation in twice real-time if the input word is reversed. It is an open
problem whether or not L rt (CA) is closed under reversal. But nevertheless, a
piece of good news is that only one additional time step for each intact cell is
necessary in order to regain the computation power in a fault tolerant manner.
Theorem 8 A set is recognizable by an OCA in twice real-time (and, thus, its
reversal by an CA in real-time) if and only if it is fault tolerant recognizable by
a SD-CA in real-time+m, where m denotes the number of intact cells.
Proof. Let L be a set that is recognizable by an OCA in twice real-time and
denote the length of an input word by n. Let us consider the situation in the
proof of Theorem 4 at real-time: The corresponding SD-CA has simulated n
steps of the corresponding OCA. But due to the previous delay, from now on
no further delay of the intact cells is necessary. Thus, the next n steps of the
OCA can be simulated in n steps by the SD-CA either. Since the number of
intact cells is exactly n the only if part follows.
Now let L be a set that is recognizable by a SD-CA in time real-time+m. We
follow the same idea as in the proof of Theorem 3. The distance between two
intact cells has to be enlarged. If we number the intact cells from right to left
by then the distance between cells i and has to be enlarged at
least by 2 i 1  (m 1) in order to prevent additional
ow of information. 2
One assumption on our model has been an intact leftmost cell. Due to Corollary
5 we can omit this requirement. Now the overall computation result is
indicated by the leftmost intact cell of the one-way array which operates per se
independently on its defective left neighbors.
In the following cellular arrays with dynamic defects (DD-CA) are introduced.
Dynamic defects can be seen as generalization of static defects. Now it becomes
possible that cells fail at any time during the computation. Afterwards they
behave as in the case of static defects.
In order to dene DD-CAs more formally it is helpful to suppose that the
state of a defective cell is a pair of states of an intact one. One component
represents the information that is transmitted to the left and the other one the
information that is transmitted to the right. By this formalization we obtain
the type indication of the cells (defective or not) for free: Defective cells are
always in states from S 2 and intact ones in states from S. A possible failure
implies a weak kind of nondeterminism for the local transition function.
Denition 9 A two-way cellular array with dynamic defects (DD-CA) is a
system hS; -; #; Ai, where
1. S is the nite, nonempty set of cell states which satises S \
2.
S is the boundary state,
3. A  S is the set of input symbols,
Sg is the local transition
function which satises -(s
If a cell works ne the local transition function maps to a state from S. Otherwise
it maps to a pair from S 2 indicating that the cell is now defective. The
denition includes the possibility to repair a cell during the computation. In
this case - would map from a pair to a state from S. Note that the nondeterminism
in a real computation is a determinism since the failure or repair of a
cell is in some sense under the control of the outside world.
We assume that initially all cells are intact and as in the static case that the
leftmost cell remains intact.
In the sequel we call an adjacent subarray of defective cells a defective region.
The next results show that dynamic defects can be compensated as long as the
lengths of defective regions are bounded.
Theorem 10 If a set is real-time recognizable by a CA, then it its real-time
recognizable by a DD-CA if the lengths of its defective regions are bounded by
some k 2 N 0 .
Proof. Assume for a moment that the lengths of the defective regions are
exactly k. A DD-CA D that simulates a given CA hS; -; #; Ai has the state set
The general idea of the proof is depicted in Figure 3. As long as a cell does
not detect a defective neighbor it stores the states of its neighbors and its own
state in some of its additional registers as shown in the gure.
time t the state of cell i might be as follows:
center
Assume now that the right neighbor of cell i becomes defective. Due to our
assumption we know that there must exist a defective region of length k at the
right of cell i. During the next k time steps cell i stores the received states and
computes missing states from its register contents as shown in Figure 3.
Subsequently its state might be as follows
| {z }
center
a
a 0
a 1
a 0
a 0
a
a t
a
c
a
d
e
c
d
e
a t
a t+1
a t
d
c
a t
c t+1
e
c
d
e
e t+1
d t+1
d t+2
c t+2
c t+3
a t+3
e t+2
d t+3
c t+4

Figure

3: Compensation of
From now on cell i receives the states that the intact cell
in at time t; t is able to compute the necessary intermediate states
from its register contents.
A crucial point is that the lengths of defective regions are xed to k. Due to
that assumption a cell i knows when it receives the valid states from its next
intact neighbor i+k+1 or i k 1. We can relax the assumption as required to
lengths of at most k cells by the following extension of the simulation. Each cell
is equipped with a modulo k counter. Since the current value of the counter is
part of the cell state it is also part of the transmitted information. A cell that
stores received information in its additional registers stores also the received
counter value. Now it can decide whether it receives the valid state from its
next intact neighbor by comparing the received counter value to the latest
stored counter value. If they are equal then the received information is from a
defective cell, otherwise it is valid and the cell uses no more additional registers.
New failures in subsequent time steps can be detected by the same method. If
the received counter value is equal to the latest stored counter value then additional
cells have become defective. In such cases the cell uses correspondingly
more additional registers in order to compensate the new defects.
It remains to explain what happens if two defective regions are joint by failure of
a single connecting intact cell. Up to now we have used the transmitted contents
of the main registers only. But actually the whole state, i.e. all register contents,
are transmitted. In the case in question the next intact cells to the left and
right of the joint defective region can ll additional registers as desired. 2
Corollary 11 If a set is real-time recognizable by an OCA, then it is real-time
recognizable by a DD-OCA if the lengths of its defective regions are bounded
by some k 2 N 0 .
In order to provide evidence for general fault tolerant DD-CA computations we
have to relax the assumption of bounded defective region lengths. We are again
concerned with the worst case. The hardest scenario is as follows. Initially all
cells are intact and thus fetching an input symbol. During the rst time step
all but the leftmost cell fail. (Needless to say, if the leftmost cell becomes also
defective then nobody would expect a reasonable computation result.)
It is easy to see that in such cases the recognition capabilities of DD-CAs are
those of a single cell, a nite state machine (see Figure 4).
Lemma 12 If a set is fault tolerant recognizable by a DD-CA, then it is recognizable
by a nite state machine and thus regular.
Corollary 13 If a set is fault tolerant recognizable by a DD-OCA, then it is
recognizable by a nite state machine and thus regular.
5 Devices with Link Failures
In Section 3 it has been shown for CAs with defective cells that in case of large
adjacent defective regions the bidirectional information
ow gets lost. This
means that the fault tolerant computation capabilities of two-way arrays are
those of one-way arrays. The observation gives rise to investigate cellular arrays
with defective links for their own. In order to explore the corresponding general
a
a 1
a
a
a
a 5 g 0
a 6
a 7 #
a 8

Figure

4: Worst case DD-CA computation.
reliable recognition capabilities we have to take a closer look on the device in
question.
Again we assume that each cell has a self-diagnosis circuit for its links which is
run once before the actual computation, and again the result of that diagnosis
is indicated by the states of the cells such that intact cells can detect defective
neighbors. What is the eect of a defective link? Suppose that each two
adjacent cells are interconnected by two unidirectional links. On one link information
is transmitted from right to left and on the other one from left to right.
both links are failing, then the parallel computation would be broken
into two not interacting lines and, thus, would be impossible at all. Therefore,
it is reasonable to require that at least one of the links between two cells does
not fail.
Suppose for a moment that there exists a cell that, due to a link failure, cannot
receive information from its right neighbor. This would imply that the overall
computation result (indicated by the leftmost cell) is obtained with no regard
to the input data to the right of that defective cell. So all reliable computations
would be trivial. In order to avoid this problem we extend the hardware such
that if a cell detects a right to left link failure it is able to reverse the direction
of the other (intact) link. Thereby we are always concerned with defective links
that cannot transmit information from left to right.
Another point of view on such devices is that some of the cells of a two-way
array behave like cells of a one-way array. Sometimes in the sequel we will call
them OCA-cells.
The result of the self-diagnosis is indicated by the states of the cells. Therefore
we have a partitioned state set.
Denition 14 A cellular array with defective links (mO-CA) is a system
is the partitioned, nite, nonempty set of cell states satisfying
2.
S is the boundary state,
3. A  S i is the set of input symbols,
4. m 2 N 0 is an upper bound for the number of link failures,
5. is the local transition function for intact cells,
is the local transition function for defective cells.
A reliable recognition process has to compute the correct result for all distributions
of the at most m defective links. In advance it is, of course, not known
which of the links will fail. Therefore, for mO-CAs we have a set of admissible
start congurations as follows.
For an input string the conguration c 0;w is an admissible
start conguration of an mO-CA if there exists a set D  ng of defective
cells, jDj  m, such that c 0;w ng n D and c 0;w
For a clear understanding we dene the global transition function  of mO-CAs
as follows: Let c t , t  0, be a conguration of an mO-CA with defective cells
D, then its successor conguration is as follows:
c t+1
c t+1
c t+1
c t+1
c t+1
c t+1
Due to our denition of - i and - d once the computation has started the set D
remains xed, what meets the requirements of our model.
In the following we are going to answer the following questions. Do some
link failures reduce the recognition power of intact CAs or is it possible to
compensate the defects by modications of the transition function as shown for
CAs with defective cells? Can mO-CAs recognize a wider range of string sets
than intact OCAs?
6 mO-CAs are Better than OCAs
The inclusions L rt (OCA)  L rt (mO-CA)  L rt (CA) are following immediately
from the denitions. Our aim is to prove that both inclusions are strict.
6.1 Subroutines
In order to prove that real-time mO-CAs are more powerful than real-time
OCAs we need some results concerning CAs and OCAs which will later on
serve as subroutines of the general construction.
6.1.1 Time Constructors
A strictly increasing mapping f : N ! N is said to be time constructible if there
exists a CA such that for an arbitrary initial conguration the leftmost cell
enters a nal state at and only at time steps f(j), 1  j  n. A corresponding
CA is called a time constructor for f . It is therefore able to distinguish the
time steps f(j).
The following lemma has been shown in [1].
Lemma 15 The mapping
Proof. The idea of the proof is depicted in Figure 5. At initial time the
leftmost cell of a CA sends a signal with speed 1=3 to the right. At the next
time step a second signal is established that runs with speed 1 and bounces
between the slow signal and the left border cell. The leftmost cell enters a
nal state at every time step it receives the fast signal. The correctness of the
construction is easily seen by induction. 2
Figure

5: A time constructor for 2 n .
A general investigation of time constructible functions can be found, e.g. in
[12, 2]. Especially, there exists a time constructor for 2 n that works with an
area of at most n cells.
Actually, we will need a time constructor for the mapping 2 2 n
. Fortunately, in
[12] the closure of these functions under composition has been shown.
Corollary 16 The mapping
There
exists a corresponding time constructor that works with an area of at most 2 n
cells.
6.1.2 Binary OCA-Counters
Here we need to set up some adjacent cells of an OCA as a binary counter.
Actually, we are not interested in the value of the counter but in the time
step at which it over
ows. Due to the information
ow the rightmost cell of
the counter has to contain the least signicant bit. Assume that this cell can
identify itself. In order to realize such a simple counter every cell has three
registers (cf. Figure 6). The third ones are working modulo 2. The second ones
are signaling a carry-over to the left neighbor and the rst ones are indicating
whether the corresponding cell has generated no carry-over (0), one carry-over
(1) or more than one carry-over (2) before. Now the whole counter can be tested
by a leftmoving signal. If on its travel through the counter all the rst registers
are containing 0 and additionally both carry-over registers of the leftmost cell
are containing 1, then it recognizes the desired time step. Observe that we need
the second carry-over register in order to check that the counter produces an
over
ow for the rst time.

Figure

binary OCA-counter.

Figure

7: A binary CA-shift-right-
counter.
6.1.3 Binary CA-Shift-Right Counters
For this type of counter we need two-way information
ow. It is set up in a
single (the leftmost) cell of a CA. Since we require the least signicant bit to
be again the rightmost bit in the counter we have to extend the counter every
time it produces an over
ow. The principle is depicted in Figure 7.
Each cell has two registers. One for the corresponding digit and the other
one for the indication of a carry-over. Due to the two-way information
ow
the leftmost cell can identify itself. Every time it generates a carry-over the
counter has to be extended. For this purpose the leftmost cell simulates an
additional cell to its left appropriately. This fact signals its right neighbor the
need to extend the counter by one cell. The right neighbor reacts by simulating
in addition the old process of the leftmost cell which now computes the new
most signicant bit. After the arrival of this extension signal at the rightmost
cell of the counter the extension is physically performed by the rst cell at the
right of the counting cells which now computes the least signicant bit.
Obviously, it can be checked again by a leftmoving signal whether the counter
represents a power of 2 or not.
6.2 Proof of the Strictness of the Inclusion
Now we are prepared to prove the main result of this section.
Let a set of strings L be dened as follows:
The easy part is to show that L does not belong to L rt (OCA).
Lemma
Proof. In [8] it has been shown that for a mapping f with the
property
lim
the set of strings fb n a f(n) j n 2 Ng does not belong to L rt (OCA). Applying
the result to L we obtain
lim
and therefore
It remains to show that L is real-time recognizable by some mO-CA.
Theorem
Proof. In the following a real-time 1O-CA M that recognizes L is constructed.
On input data b n a m we are concerned with three possible positions of the unique
defective cell:
1. The position is within the b-cells.
2. The position is within the leftmost 2 n a-cells.
3. The position is at the right hand side of the 2 n th a-cell.
At the beginning of the computation M starts the following tasks in parallel on
some tracks: The unique defective cell establishes a time constructor M 1 for
if it is an a-cell. The leftmost a-cell establishes another time constructor
and, additionally, a binary shift-right counter C 1 that counts the
number of a's. The rightmost b-cell starts a binary OCA-counter C 2 and, nally,
the rightmost a-cell sends a stop signal with speed 1 to the left.
According to the three positions the following three processes are superimposed.
Case 3. (cf. Figure 8) The shift-right counter is increased by 1 at every time
step until the stop signal  arrives. Each over
ow causes an incrementation (by
1) of the counter C 2 . Let i be the time step at which the stop signal arrives
at the shift-right counter C 1 and let l be the number of digits of C 1 . During
the next l time steps the signal travels through the counter and tests whether
its value is a power of 2, from which Subsequently, the signal
tests during another n time steps whether the value of the binary counter C 2 is
exactly 2 n , from which l = 2 n follows. If the tests are successful the input is
accepted because the input string is of the form b n a l a
a 2 l
and, thus, belongs to L.
OCA
b b a a a a a a a a a a a a a a a a a a a a
overflow

Figure

8: Example for case 3,
Case 2. (cf. Figure 9) In this case the space between the b's and the defective
cell is too small for setting up an appropriate counter as shown for Case 3.
Here a second binary counter C 3 within the b-cells is used. It is increased by
1 at every time step until it receives a signal from the defective cell and, thus,
contains the number of cells between the b-cells and the defective cell. Its value
x is conserved on an additional track. Moreover, at every time step at which
the time constructor M 1 marks the defective cell to be nal, a signal is sent
to the b-cells that causes them to reset the counter to the value x by copying
the conserved value back to the counter track. After the reset the counter is
increased by 1 at every time step. Each reset signal also marks an unmarked
b-cell.
The input is accepted if exactly at the arrival of the stop signal at the leftmost
OCA
b b a a a a a
a a a a a a a a a a a a a a a
overflow
f
f
f
f
f
f
f
overflow

Figure

9: Example for case 2,
cell the counter over
ows for the rst time and all b-cells are marked: Let the
last marking of M 1 happen at time
for some r 2 N. The corresponding
leftmoving signal arrives at time 2 2 r
x at the b-cells and resets the counter
C 3 to x. The stop signal arrives at time 2 2 r
N, at the
counter that has now the value x+ s. Since the counter produces an over
ow it
holds . Moreover, since M 1 has sent exactly r marking signals and
all b-cells are marked it follows Therefore, the stop signal arrives at the
rightmost b-cell at time 2 2 r
and the input belongs to L.
Case 1. Since the binary counter M 3 within the b-cells is an OCA-counter it
works ne even if the defective cell is located within the b-cells. Case 1 is a
straightforward adaption of case 2 (here M 2 is used instead of M 1 ). 2
Corollary 19 L rt (OCA)  L rt (1O-CA)
This result can be generalized to devices with a bounded number of defective
cells as follows.
Theorem 20 Let m 2 N be some constant then L 2 L rt (mO-CA).
Proof. If all defective cells are located within the b-cells, or within the rst
or within the last 2 2 n
a-cells, then the proof follows from the three
cases in the proof of Theorem 18. Otherwise we are concerned with two more
cases:
Case 4: The leftmost defective a-cell is not within the rst 1
a-cells. By
standard compression techniques we can simulate m cells by one. Now the
construction of Case 3 in the proof of Theorem solves this case.
Case 5: The leftmost defective a-cell is within the rst 1
a-cells. In order
to adapt Case 2 of the previous proof due to Corollary 16 we may assume the
time constructor for 2 n works in at most n cells. By standard compression
techniques we obtain at most 1
cells.
According to our assumption not all defective cells are within the rst 2 n a-
cells. So we have two defective cells with a distance of more than 1
cells. This allows us to use the compressed time constructor in that area. The
remaining construction has been shown in Case 2.
At the very beginning of the computation it is not know which area of the
possible m areas is the related one. In order to determine it we start time
constructors at each defective cell. Now we are able to choose a correct track
of a successful computation and the set is recognized if one of the m time
constructors recognizes the input. 2
Corollary be some constant then L rt (OCA)  L rt (mO-CA).
7 CAs are Better than mO-CAs
In order to complete the comparisons we have to prove that the computational
power of real-time mO-CAs is strictly weaker than those of CAs. For this
purpose we can adapt a method developed in [16] for proving that certain
string sets do not belong to L rt (OCA). The basic idea in [16] is to dene an
equivalence relation on string sets and bound the number of distinguishable
equivalence classes of real-time OCA computations.
be an OCA and X;Y  A  . Two strings w; w are
dened to be (M;X;Y )-equivalent i for all x 2 X and y 2 Y the leftmost
states of the congurations  [jwj] are equal
(cf.

Figure

10).
OCA

Figure

10: Principle of bounding real-time equivalence classes.
The observation is that the essential point of the upper bound on equivalence
classes is due to the fact that the input sequences x and y are computational
unrelated. Therefore, we can assume that the cell obtaining the rst symbol of
w resp. of w 0 as input is defective and so adapt the results in [16] to 1O-CAs
immediately:
Corollary be some constant, then
Corollary
Finally, it follows for a constant m 2 N:



--R


Some relations between massively parallel arrays



Fault tolerant cellular automata
The synchronization of nonuniform networks of
Pushdown cellular automata
Minimal time synchronization in restricted defective cellular automata

Synchronization of a line of
Signals in one dimensional cellular automata

Fault tolerant cellular spaces
Language recognition and the synchronization of cellular au- tomata
Language not recognizable in real time by one-way cellular automata
A fault-tolerant scheme for optimum-time ring squad synchro- nization
Deterministic one-way simulation of two-way real-time cellular automata and its related problems
Probabilistic logics and the synthesis of reliable organisms from unreliable components

--TR
On real-time cellular automata and trellis automata
Reliable computation with cellular automata
A simple three-dimensional real-time reliable cellular array
Minimal time synchronization in restricted defective cellular automata
The synchronization of nonuniform networks of finite automata
Language not recognizable in real time by one-way cellular automata
Some relations between massively parallel arrays
Pushdown cellular automata
Signals in one-dimensional cellular automata
Real-Time Language Recognition by One-Way and Two-Way Cellular Automata
static and dynamic defects;syntactical pattern recognition;fault-tolerance;link failures;cellular arrays