<p>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.</p>

CC BY-SA 3.0
2012-04-24T23:53:02.197Z
Could you clarify `"stencils are updated by a sweep across the grid"`? What is a `"sweep"`?
hhh
CC BY-SA 3.0
2012-04-25T00:11:40.660Z
@RickyDemer: what is a `"monotone traversal"`? Monotonic function that traverse over the grid?
hhh
CC BY-SA 3.0
2012-04-25T00:21:19.363Z
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
CC BY-SA 3.0
2012-04-25T01:25:20.217Z
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
CC BY-SA 3.0
2012-04-24T23:45:30.310Z
2012-04-24T23:45:30.310Z
David Eppstein
<p>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 <em>easy</em> description, though.</p>

<p>S. Capobianco, T. Uustalu. <a href="http://cs.ioc.ee/~tarmo/papers/jac10.pdf" rel="nofollow">A categorical outlook on cellular automata.</a>
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.</p>

CC BY-SA 3.0
2012-04-25T13:30:49.737Z
They use uniform spaces! I've been looking for an application of them to PL for some time now. Thanks!
Neel Krishnaswami
CC BY-SA 3.0
2012-04-25T16:50:50.120Z
Glad to be of assistance.
Dave Clarke
CC BY-SA 3.0
2012-04-25T11:34:06.023Z
2012-04-25T11:34:06.023Z
Dave Clarke
<blockquote>
  <p><strong>Definitions</strong></p>
  
  <p><strong>Stencil</strong> =
  <em>"For a given point, a stencil is a pre-determined set of nearest
  neighbors (possibly including itself)."</em>
  <a href="http://www.cs.berkeley.edu/~kdatta/pubs/mspc06_slides.pdf" rel="nofollow noreferrer">(source)</a></p>
  
  <p><strong>Wikipedia's definition (<a href="http://en.wikipedia.org/wiki/Stencil_codes" rel="nofollow noreferrer">source</a>) =</strong>
  <img src="https://i.sstatic.net/Lj6nG.png" alt="enter image description here"></p>
</blockquote>

<p>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?</p>

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

<p><strong>Perhaps related</strong></p>

<ol start="2">
<li><p>Automatic Stencil Code Generation Ph.D. Thesis Proposal <a href="http://www.cs.berkeley.edu/~kdatta/talks/quals_proposal_07.pdf" rel="nofollow noreferrer">here</a>. The author behind the last paper <a href="http://www.cs.berkeley.edu/~kdatta/" rel="nofollow noreferrer">here</a>, researching something about stencil things and a lot of perhaps related publications <a href="https://ftg.lbl.gov/staff/swwilliams/" rel="nofollow noreferrer">here</a>, related to the last author.</p></li>
<li><p>Fey, Dietmar et al. (2010) Grid-Computing: Eine Basistechnologie für Computational Science. Page 439. (<a href="http://en.wikipedia.org/wiki/Stencil_codes#cite_note-Fey-2" rel="nofollow noreferrer">Source</a>)</p></li>
<li><p>Complex Systems from the Perspective of Category
Theory: I. Functioning of the Adjunction Concept <a href="http://philsci-archive.pitt.edu/1236/1/Axiomath.pdf" rel="nofollow noreferrer">here</a></p></li>
</ol>

CC BY-SA 3.0
2012-04-25T12:04:05.550Z
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
<computability><terminology><ct.category-theory><machine-models><cellular-automata>
Difference between Stencil -structures and Cellular Automata Category-theoretically?
hhh
# Difference between Stencil -structures and Cellular Automata Category-theoretically?

(Asked by: username_0 on 2012-04-24)

> **Definitions**
>
> **Stencil** =
> *"For a given point, a stencil is a pre-determined set of nearest
> neighbors (possibly including itself)."*
> [(source)](http://www.cs.berkeley.edu/~kdatta/pubs/mspc06_slides.pdf)
>
> **Wikipedia's definition ([source](http://en.wikipedia.org/wiki/Stencil_codes)) =**
> ![enter image description here](https://i.sstatic.net/Lj6nG.png)

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**

2. Automatic Stencil Code Generation Ph.D. Thesis Proposal [here](http://www.cs.berkeley.edu/~kdatta/talks/quals_proposal_07.pdf). The author behind the last paper [here](http://www.cs.berkeley.edu/~kdatta/), researching something about stencil things and a lot of perhaps related publications [here](https://ftg.lbl.gov/staff/swwilliams/), related to the last author.
3. Fey, Dietmar et al. (2010) Grid-Computing: Eine Basistechnologie für Computational Science. Page 439. ([Source](http://en.wikipedia.org/wiki/Stencil_codes#cite_note-Fey-2))
4. Complex Systems from the Perspective of Category
   Theory: I. Functioning of the Adjunction Concept [here](http://philsci-archive.pitt.edu/1236/1/Axiomath.pdf)

**Tags:** computability, terminology, ct.category-theory, machine-models, cellular-automata

> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2012-04-24. Score: 2

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.

> **Comments:**
> **username_0**: Could you clarify `"stencils are updated by a sweep across the grid"`? What is a `"sweep"`?  
> **username_0**: @RickyDemer: what is a `"monotone traversal"`? Monotonic function that traverse over the grid?  
> **username_0**: 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?  
> **username_2**: 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.  

---

### Answer by username_1 on 2012-04-25. Score: 2

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.](http://cs.ioc.ee/~tarmo/papers/jac10.pdf)
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.

> **Comments:**
> **username_3**: They use uniform spaces! I've been looking for an application of them to PL for some time now. Thanks!  
> **username_1**: Glad to be of assistance.  

---

