2
$\begingroup$

Definitions

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

Wikipedia's definition (source) = enter image description here

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Apr 25, 2012 at 12:04

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Could you clarify "stencils are updated by a sweep across the grid"? What is a "sweep"? $\endgroup$
    – hhh
    Apr 24, 2012 at 23:53
  • 1
    $\begingroup$ A sweep is a monotone traversal. $\endgroup$
    – user6973
    Apr 25, 2012 at 0:05
  • $\begingroup$ @RickyDemer: what is a "monotone traversal"? Monotonic function that traverse over the grid? $\endgroup$
    – hhh
    Apr 25, 2012 at 0:11
  • $\begingroup$ 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? $\endgroup$
    – hhh
    Apr 25, 2012 at 0:21
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 25, 2012 at 1:25
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ They use uniform spaces! I've been looking for an application of them to PL for some time now. Thanks! $\endgroup$ Apr 25, 2012 at 13:30
  • $\begingroup$ Glad to be of assistance. $\endgroup$ Apr 25, 2012 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.