# Difference between Stencil -structures and Cellular Automata Category-theoretically?

Definitions

Stencil = "For a given point, a stencil is a pre-determined set of nearest neighbors (possibly including itself)." (source)

Wikipedia's definition (source) =

It looks like CA (cellular automata) is a broader (and perhaps more sexy fuzzy populist) concept while the stencil (S) is more rigorous. Suppose a torus -topology in a grid and a simple structure where each state depends only on the next state (some transition rule, 4 neighbors but only next state matters). This I think is a Stencil, Cellular automaton, a grid, a mesh, easily described with Markov Chain -- and a structure. Now I am confused! So many different words for the same thing? Please, add references to quantify this concept, many authors seem to use different words for the same thing -- not sure what it is, some structure with function -definitions -- perhaps there exists some easy category-theoretic description for them?

If this is too elementary question, I would be happy about some reference covering definitions rigorously and doing some comparisons.

Perhaps related

1. Automatic Stencil Code Generation Ph.D. Thesis Proposal here. The author behind the last paper here, researching something about stencil things and a lot of perhaps related publications here, related to the last author.

2. Fey, Dietmar et al. (2010) Grid-Computing: Eine Basistechnologie für Computational Science. Page 439. (Source)

3. Complex Systems from the Perspective of Category Theory: I. Functioning of the Adjunction Concept here

• You will find that these are different (but related) concepts defined in different communities and used for different (and possibly unrelated) reasons. I suspect that you need to read more in detail about each of these concepts and understand them in their original setting, in isolation of other settings. Trying to find a description in terms of category theory will probably make things less easy to understand, unless you are very good with categories. – Dave Clarke Apr 25 '12 at 12:04

Judging from the source you provided, there appear to be two key differences: (1) stencils have numeric values in each cell and update the cells with functions defined numerically (typically using continuous functions) while cellular automata typically have only a finite set of values per cell and use functions that in general do not arise from numerical methods, and (2) stencils are updated by a sweep across the grid while in cellular automata generally all cells are updated simultaneously.

• Could you clarify "stencils are updated by a sweep across the grid"? What is a "sweep"? – hhh Apr 24 '12 at 23:53
• A sweep is a monotone traversal. – user6973 Apr 25 '12 at 0:05
• @RickyDemer: what is a "monotone traversal"? Monotonic function that traverse over the grid? – hhh Apr 25 '12 at 0:11
• Does this mean that the updating with stencil is not necessarily simultaneous? Is the word "sweep" meant here as a desciptive word (like a sweeping a table with finger) or does it have some rigorous definition? – hhh Apr 25 '12 at 0:21
• I just mean looping over the array elements one at a time in the sort of order you would get from a standard nested for-loop structure. – David Eppstein Apr 25 '12 at 1:25

There does indeed exist a category theoretic description of cellular automata. I don't know the details, but I can provide you with a reference. It doesn't look like an easy description, though.

S. Capobianco, T. Uustalu. A categorical outlook on cellular automata. In J. Kari, ed., Proc. of 2nd Symp. on Cellular Automata, JAC 2010 (Turku, Dec. 2010), v. 13 of TUCS Lecture Notes, pp. 88-99. Turku Centre for Computer Science, 2010.

• They use uniform spaces! I've been looking for an application of them to PL for some time now. Thanks! – Neel Krishnaswami Apr 25 '12 at 13:30
• Glad to be of assistance. – Dave Clarke Apr 25 '12 at 16:50