Cellular automata may be viewed as computational models of complex systems. They also
can be seen as continuous functions on a particular family of compact metric spaces. This …

It is shown that f (n)-time one-way cellular automata are equivalent to f (n)-time trellis
automata, the real-time one-way cellular automata languages are closed under reversal, the …

Characterizations of various types of linear iterative (systolic) arrays in terms of single
processor sequential machines are given. Using these characterizations, new or improved …

There are two simple models of parallel language recognizes: one-way cellular array (OCA)
and one-way iterative array (OIA). For inputs of length n, both arrays consist of n identical …

A new type of a systolic automaton, referred to as a systolic trellis automaton, is investigated.
It consists of a triangularly shaped system of hexagonally connected processors (functional …

The advantages of homogeneous arrays of interacting processing elements are simplicity
and uniformity. It turned out that a large array of not very powerful elements operating in …

We look at a simple, but general model, of a systolic system called a trellis automaton (TA). A
TA is equivalent in computational power to a one-dimensional unbounded cellular …

On real time and linear time cellular automata Page 1 RAIRO INFORMATIQUE
THÉORIQUE W. BUCHER K. CULIK II On real time and linear time cellular automata RAIRO …

In this paper, a very simple model of parallel computation is considered, and the question of
how restricting the flow of data to be one way compares with two-way flow is studied. It is …

We analyse some properties of two-dimensional iterative and cellular arrays. For example,
we show that arrays operating in T (n) time can be sped up to operate in time n+ (T (n)− n) k …