A lattice model for cellular (systolic) algorithms (Q1079019)

The author proposes a lattice model for (homogeneous) cellular algorithms based on moving data streams. The model can be alternatively described in standard terminology as an ordinary euclidean n-dimensional cellular automaton in which (a) the neighborhood of a cell \(x\in Z^ n\) consists of k-cells \(x-v_ 1,...,x-v_ k\) for fixed distinct vectors \(v_ i\), (b) each cell consists of k registers each holding an independent variable that takes on values of a certain predefined type, and (c) the transition function is evaluated jointly at the contents of x and all of its neighbors, except that f is not applied if one of the registers in a neighbor cell does not have a value. Such a lattice algorithm can be regarded as computing a function of k-tuples of variables whose values are initially assigned to some cells of \(Z^ n\). Two theorems provide sufficient conditions for different lattice models to be equivalent (i.e., compute the same function): if the space-time diagram of instantaneous description of \(Z^ n\) is transformed by: 1. a strong linear mapping (i.e., increasing on time components); or, 2. non-time- collapsing transformations and an associative transition function, then the two lattice algorithms are equivalent. Although lattices are emphasized throughout, they do not seem to play any crucial role in the above results.