actually i wanted to figure out -considering a undirected graph(G) and a vertex from G (v) plus v's neighboring vertexes(Nv)- how could i map members of Nv to cells(or cell regions) of a two dimensional square grid?(like GoL world); in another word do you have any suggestion for a map function to encode a graph into a simple CA; i wanted to visualize dynamics of information cascade over a network represented with a graph with CA help(if it makes sense);
Can you elaborate more on what you mean? What are the inputs, outputs? Are you giving a graph then producing a cellular automaton (or the other way around)? What about the cellular automata are you trying to preserve (in terms of properties)? Trying to encode a cellular automaton that contains the description of a graph (like a correspondence)? What exactly about the graph are you modelling? Just vertices and edges? Keep in mind that a cellular automaton is a model of computation, a graph is a mathematical object. They may not "line up" exactly.
The question kind of confuses me because it is kind of like asking me if it is possible to model a graph as a Turing Machine. Turing Machines have final states, and a lot of properties that aren't necessarily what I would describe "only" for a graph (since graphs have vertices and edges, not transitions and final states). It is worth noting that many formal languages can be described in different automata. Many of these automata can be visualized or interpreted as "graph-like" objects though for a fixed formal language (but the edges are transitions, and may/may not operate the way you want them to). That may be "more" of what you are asking, but it is hard to tell.
If you were asking how to encode the graph into a cellular automaton, that seems to make a little more sense, but you may have good reasons to pursue what you are after, so I cannot judge.
These questions may help people answer your question.
Can you elaborate more on what you mean? What are the inputs, outputs? Are you giving a graph then producing a cellular automaton (or the other way around)? What about the cellular automata are you trying to preserve (in terms of properties)? Trying to encode a cellular automaton that contains the description of a graph (like a correspondence)? What exactly about the graph are you modelling? Just vertices and edges? Keep in mind that a cellular automaton is a model of computation, a graph is a mathematical object. They may not "line up" exactly.
The question kind of confuses me because it is kind of like asking me if it is possible to model a graph as a Turing Machine. Turing Machines have final states, and a lot of properties that aren't necessarily what I would describe "only" for a graph (since graphs have vertices and edges, not transitions and final states). It is worth noting that many formal languages can be described in different automata. Many of these automata can be visualized or interpreted as "graph-like" objects though for a fixed formal language (but the edges are transitions, and may/may not operate the way you want them to). That may be "more" of what you are asking, but it is hard to tell.
If you were asking how to encode the graph into a cellular automaton, that seems to make a little more sense, but you may have good reasons to pursue what you are after, so I cannot judge.
These questions may help people answer your question.
If you will present cellular automaton as a graph it will be similar to artificial neuron net with discrete neurons having fixed values of synapses (links) and unusual activation function. You will can to explore the functioning of this neuronet in time, but can't to train it (if the function and synapses is fixed).
sorry everyone; i guess you're right about this needing some elaboration; actually i wanted to figure out -considering a undirected graph(G) and a vertex from G (v) plus v's neighboring vertices(Nv)- how could i map members of Nv to cells(or cell regions) of a two dimensional square grid?(like GoL world); in another word do you have any suggestion for a map function to encode a graph into a simple CA; i wanted to visualize dynamics of information cascade over a network represented with a graph with CA help(if it makes sense); hope this helped
Of course you can do it provided that the graph you want to represent is a planar graph.
A touching polygon representation of a planar graph is a representation where each node is a (not necessarily convex) polygon and the borders of two polygons touch if and only if the corresponding nodes are adjacent in the graph (no overlaps between regions allowed). You can obtain a touching polygon representation with the algorithm described in: Hubert de Fraysseix, Patrice Ossona de Mendez, and Pierre Rosenstiehl. On triangle contact graphs. Combinatorics, Probability and Computing, 3(02):233–246, 1994.
Then you could: (1) approximate the polygons with a set of adjacent squares (as if they were pixels of a screen); (2) inscribe the drawing into a rectangle. If you don't want holes in your CA, then you should manage to fill the holes with some adjacent "color", which seems to be possible, although it may be tricky if you don't want to create extra-contacts among regions.
Yea, Its a good problem. I have found questions and answers related to this problem, while I was searching for the same. How can we explore the properties of (Let suppose one dimensional cellular auto-meta) by modelling it by graph and basis on the spectral properties of the corresponding graph.
- Badges
- Science topic
- Similar topics
- Philosophy Of Science
- Models